Misplaced Pages

#186813

64-605: The system is based on the module learning with errors (M-LWE) problem, in conjunction with cyclotomic rings . Recently, there has also been a tight formal mathematical security reduction of the ring-LWE problem to MLWE. Compared to competing PQ methods, it has typical advantages of lattice-based methods, e.g. in regard to runtime as well as the size of the ciphertexts and the key material. Variants with different security levels have been defined: Kyber512 ( NIST security level 1, ≈ AES 128), Kyber768 (NIST security level 3, ≈AES 192), and Kyber1024 (NIST security level 5, ≈AES 256). At

128-697: A i , b i ) } {\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}} from A s , χ {\displaystyle A_{\mathbf {s} ,\chi }} , it is easy to see that { ( a i , b i + ⟨ a i , t ⟩ ) / q } {\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q\}} are samples from A s + t , χ {\displaystyle A_{\mathbf {s} +\mathbf {t} ,\chi }} . So, suppose there

192-510: A i , t ⟩ ) / q } {\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q\}} and feed these samples to A {\displaystyle {\mathcal {A}}} . Since S {\displaystyle {\mathcal {S}}} comprises a large fraction of Z q n {\displaystyle \mathbb {Z} _{q}^{n}} , with high probability, if we choose

256-550: A factor of about 2.3 (1.5–7), an estimated 2.3-fold (1.4–3.1) increase in energy consumption, and have about 70 times (48–92) more data overhead . Internal hashing operations account for the majority of the runtime, which would thus potentially benefit greatly from corresponding hardware acceleration . Kyber is derived from a method published in 2005 by Oded Regev , developed by developers from Europe and North America, who are employed by various government universities or research institutions, or by private companies, with funding from

320-478: A finite ring from given samples y i = f ( x i ) {\displaystyle y_{i}=f(\mathbf {x} _{i})} some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus to be useful in cryptography. More precisely, the LWE problem is defined as follows. Let Z q {\displaystyle \mathbb {Z} _{q}} denote

384-608: A fixed vector. Let ϕ {\displaystyle \phi } be a fixed probability distribution over T {\displaystyle \mathbb {T} } . Denote by A s , ϕ {\displaystyle A_{\mathbf {s} ,\phi }} the distribution on Z q n × T {\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} } obtained as follows. The learning with errors problem L W E q , ϕ {\displaystyle \mathrm {LWE} _{q,\phi }}

448-676: A polynomial factor) as hard in the average case as they are in the worst case. For a n -dimensional lattice L {\displaystyle L} , let smoothing parameter η ε ( L ) {\displaystyle \eta _{\varepsilon }(L)} denote the smallest s {\displaystyle s} such that ρ 1 / s ( L ∗ ∖ { 0 } ) ≤ ε {\displaystyle \rho _{1/s}(L^{*}\setminus \{\mathbf {0} \})\leq \varepsilon } where L ∗ {\displaystyle L^{*}}

512-499: A polynomial number of values for t {\displaystyle \mathbf {t} } , we will find one such that s + t ∈ S {\displaystyle \mathbf {s} +\mathbf {t} \in {\mathcal {S}}} , and A {\displaystyle {\mathcal {A}}} will successfully distinguish the samples. Thus, no such S {\displaystyle {\mathcal {S}}} can exist, meaning LWE and DLWE are (up to

576-725: A polynomial-time solver for the decision problem that errs with very small probability, since q {\displaystyle q} is bounded by some polynomial in n {\displaystyle n} , it only takes polynomial time to guess every possible value for k {\displaystyle k} and use the solver to see which one is correct. After obtaining s 1 {\displaystyle \mathbf {s} _{1}} , we follow an analogous procedure for each other coordinate s j {\displaystyle \mathbf {s} _{j}} . Namely, we transform our b i {\displaystyle \mathbf {b} _{i}} samples

640-416: A quantum-safe Provider module for OpenSSL 3.x, and has integrated its code into BoringSSL and wolfSSL . There are a handful of implementations using various other programming languages from third-party developers, including JavaScript and Java. Various (free) optimized hardware implementations exist, including one that is resistant to side-channel attacks. The German Federal Office for Information Security

704-421: A similar result assuming only the classical hardness of the related problem G a p S V P ζ , γ {\displaystyle \mathrm {GapSVP} _{\zeta ,\gamma }} . The disadvantage of Peikert's result is that it bases itself on a non-standard version of an easier (when compared to SIVP) problem GapSVP. Regev proposed a public-key cryptosystem based on

SECTION 10

#1732780149187

768-532: A small modification, works for any q {\displaystyle q} that is a product of distinct, small (polynomial in n {\displaystyle n} ) primes. The main idea is if q = q 1 q 2 ⋯ q t {\displaystyle q=q_{1}q_{2}\cdots q_{t}} , for each q ℓ {\displaystyle q_{\ell }} , guess and check to see if s j {\displaystyle \mathbf {s} _{j}}

832-403: A time. To obtain the first coordinate, s 1 {\displaystyle \mathbf {s} _{1}} , make a guess k ∈ Z q {\displaystyle k\in \mathbb {Z} _{q}} , and do the following. Choose a number r ∈ Z q {\displaystyle r\in \mathbb {Z} _{q}} uniformly at random. Transform

896-621: A versatile problem used in construction of several cryptosystems. In 2005, Regev showed that the decision version of LWE is hard assuming quantum hardness of the lattice problems G a p S V P γ {\displaystyle \mathrm {GapSVP} _{\gamma }} (for γ {\displaystyle \gamma } as above) and S I V P t {\displaystyle \mathrm {SIVP} _{t}} with t = O ( n / α ) {\displaystyle t=O(n/\alpha )} ). In 2009, Peikert proved

960-506: Is The cryptosystem is then defined by: The proof of correctness follows from choice of parameters and some probability analysis. The proof of security is by reduction to the decision version of LWE : an algorithm for distinguishing between encryptions (with above parameters) of 0 {\displaystyle 0} and 1 {\displaystyle 1} can be used to distinguish between A s , χ {\displaystyle A_{s,\chi }} and

1024-468: Is a mathematical problem that is widely used to create secure encryption algorithms . It is based on the idea of representing secret information as a set of equations with errors. In other words, LWE is a way to hide the value of a secret by introducing noise to it. In more technical terms, it refers to the computational problem of inferring a linear n {\displaystyle n} -ary function f {\displaystyle f} over

1088-576: Is a prime bounded by some polynomial in n {\displaystyle n} . Intuitively, if we have a procedure for the search problem, the decision version can be solved easily: just feed the input samples for the decision problem to the solver for the search problem. Denote the given samples by { ( a i , b i ) } ⊂ Z q n × T {\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} } . If

1152-1252: Is a reduction from GapSVP 100 n γ ( n ) {\displaystyle \operatorname {GapSVP} _{100{\sqrt {n}}\gamma (n)}} to D G S n γ ( n ) / λ ( L ∗ ) {\displaystyle DGS_{{\sqrt {n}}\gamma (n)/\lambda (L^{*})}} for any function γ ( n ) ≥ 1 {\displaystyle \gamma (n)\geq 1} . Regev then shows that there exists an efficient quantum algorithm for D G S 2 n η ε ( L ) / α {\displaystyle DGS_{{\sqrt {2n}}\eta _{\varepsilon }(L)/\alpha }} given access to an oracle for L W E q , Ψ α {\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}} for integer q {\displaystyle q} and α ∈ ( 0 , 1 ) {\displaystyle \alpha \in (0,1)} such that α q > 2 n {\displaystyle \alpha q>2{\sqrt {n}}} . This implies

1216-611: Is aiming for implementation in Thunderbird , and in this context also an implementation in the Botan program library and corresponding adjustments to the OpenPGP standard. In 2023, the encrypted messaging service Signal implemented PQXDH , a Kyber-based post-quantum encryption algorithm, to their Signal Protocol which is used by WhatsApp and others. Learning with errors In cryptography , learning with errors ( LWE )

1280-590: Is also used. The "new hope" implementation selected for Google's post-quantum experiment, uses Peikert's scheme with variation in the error distribution. Main article: Ring learning with errors signature A RLWE version of the classic Feige–Fiat–Shamir Identification protocol was created and converted to a digital signature in 2011 by Lyubashevsky. The details of this signature were extended in 2012 by Gunesyu, Lyubashevsky, and Popplemann in 2012 and published in their paper "Practical Lattice Based Cryptography – A Signature Scheme for Embedded Systems." These papers laid

1344-443: Is chosen uniformly at random from Z q n {\displaystyle \mathbb {Z} _{q}^{n}} , we could simply try different values t {\displaystyle \mathbf {t} } sampled uniformly at random from Z q n {\displaystyle \mathbb {Z} _{q}^{n}} , calculate { ( a i , b i + ⟨

SECTION 20

#1732780149187

1408-602: Is conditional on the execution of various patent -related agreements, with NTRU being a fallback option. Currently, a fourth round of the standardization process is underway, with the goal of standardizing an additional KEM. In the second phase of the selection process, several parameters of the algorithm were adjusted and the compression of the public keys was dropped. Most recently, NIST paid particular attention to costs in terms of runtime and complexity for implementations that mask runtimes in order to prevent corresponding side-channel attacks (SCA). Kyber underwent changes during

1472-588: Is congruent to 0 mod q ℓ {\displaystyle 0\mod q_{\ell }} , and then use the Chinese remainder theorem to recover s j {\displaystyle \mathbf {s} _{j}} . Regev showed the random self-reducibility of the LWE and DLWE problems for arbitrary q {\displaystyle q} and χ {\displaystyle \chi } . Given samples { (

1536-500: Is defined as follows: An instance of D G S ϕ {\displaystyle DGS_{\phi }} is given by an n {\displaystyle n} -dimensional lattice L {\displaystyle L} and a number r ≥ ϕ ( L ) {\displaystyle r\geq \phi (L)} . The goal is to output a sample from D L , r {\displaystyle D_{L,r}} . Regev shows that there

1600-565: Is focused on IT security rather than being part of an organisation with a more general IT standards remit. BSI is separate from Germany's signals intelligence , which is part of the military and the foreign intelligence service ( BND ). The BSI's scope of duties is defined by the German Federal Office for Information Security (BSI Act). The aim of the BSI is the promotion of information and cyber security in order to enable and promote

1664-568: Is former business executive Claudia Plattner, who took over the presidency from Arne Schönbohm. BSI's predecessor was the cryptographic department of Germany's foreign intelligence agency ( BND ). BSI still designs cryptographic algorithms such as the Libelle cipher and initiated the development of the Gpg4win cryptographic suite. The BSI has a similar role as the Unlike those organizations, BSI

1728-411: Is free of charge and can be applied for by any German institution. The UP KRITIS (UP stands for implementation plan) is a public-private cooperation between operators of critical infrastructures (KRITIS), their various associations and the responsible governmental agencies such as the BSI. It addresses eight of the nine critical infrastructure sectors. The sector "state and administration" is covered by

1792-458: Is the search version of the problem. In the decision version ( DLWE ), the goal is to distinguish between noisy inner products and uniformly random samples from Z q n × T {\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} } (practically, some discretized version of it). Regev showed that the decision and search versions are equivalent when q {\displaystyle q}

1856-476: Is the dual of L {\displaystyle L} and ρ α ( x ) = e − π ( | x | / α ) 2 {\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}} is extended to sets by summing over function values at each element in the set. Let D L , r {\displaystyle D_{L,r}} denote

1920-470: Is to find s ∈ Z q n {\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}} , given access to polynomially many samples of choice from A s , ϕ {\displaystyle A_{\mathbf {s} ,\phi }} . For every α > 0 {\displaystyle \alpha >0} , denote by D α {\displaystyle D_{\alpha }}

1984-576: The European Commission , Switzerland, the Netherlands, and Germany. They also developed the related and complementary signature scheme Dilithium , as another component of their "Cryptographic Suite for Algebraic Lattices" (CRYSTALS). Like other PQC-KEM methods, Kyber makes extensive use of hashing internally. In Kyber's case, variants of Keccak ( SHA-3 /SHAKE) are used here, to generate pseudorandom numbers , among other things. In 2017

Kyber - Misplaced Pages Continue

2048-513: The German government . Its areas of expertise and responsibility include the security of computer applications, critical infrastructure protection , Internet security , cryptography , counter eavesdropping , certification of security products and the accreditation of security test laboratories. It is located in Bonn and as of 2024 has about 1,700 employees. Its current president, since 1 July 2023,

2112-469: The BSI include informing and sensitizing citizens to the safe use of information technology, mobile communication media and the Internet. The BSI therefore offers online content specially tailored to the needs of citizens ( BSI für Bürger ). The website covers topics and information on IT and Internet security in a way that is understandable even for technical laypersons. In addition to providing information,

2176-677: The German Association for Information Technology, Telecommunications and New Media (Bitkom). As a members-only association major players in the field of cyber security in Germany aim to provide up-to-date and valid information on threats in cyberspace and supports the exchange of information, experience and best practices between participants. More than 6,800 institutions as of 2023 belong to the Alliance for Cyber Security, including 180 partner companies and 110 multipliers. Participation

2240-703: The Green Book, ITSEC and the Common Criteria. The BSI is a national authority in the field of cryptography, which draws up recommendations and technical guidelines for cryptographic procedures and is involved in the development of international cryptographic standards. The IT Baseline Protection Catalog, or IT-Grundschutz , is a collection of enterprise security guidelines established by the office, which serve to identify and combat security-relevant vulnerabilities in IT environments. With introduction and catalogs,

2304-619: The IT systems and networks of the federal administration. Once a year, the BSI reports on this to the Committee on Internal Affairs of the German Bundestag. The tasks of the BSI include: The BSI is the central certification body for the security of IT systems in Germany (computer and data security, data protection). Testing and certification is possible with regard to the standards of the IT-Grundschutzhandbuch,

2368-458: The Kyber768 level, the secret keys are 2400 bytes in size, the public keys 1184, and the ciphertexts 1088. With an accordingly optimized implementation, 4 kilobytes of memory can be sufficient for the cryptographic operations. For a chat encryption scenario using liboqs, replacing the extremely efficient, non-quantum-safe ECDH key exchange using Curve25519 was found to increase runtime by

2432-564: The LWE problem is as hard to solve as several worst-case lattice problems . Subsequently, the LWE problem has been used as a hardness assumption to create public-key cryptosystems , such as the ring learning with errors key exchange by Peikert. Denote by T = R / Z {\displaystyle \mathbb {T} =\mathbb {R} /\mathbb {Z} } the additive group on reals modulo one . Let s ∈ Z q n {\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}} be

2496-568: The NIST standardization process. In particular, in the submission for round 2 (so called Kyber v2 ), the following features were changed: Submission to round 3 underwent further tweaks: The developers have released a reference implementation into the public domain (or under CC0 ), which is written in C . The program library liboqs of the Open Quantum Safe (OQS) project contains an implementation based on that. OQS also maintains

2560-584: The UP BUND and activities on state and municipal level. The goal of the UP KRITIS cooperation is to maintain the supply of critical infrastructure services in Germany. All organizations based in Germany that operate critical infrastructures in Germany, national professional and industry associations from the KRITIS sectors and the responsible authorities can participate in UP KRITIS upon application. The tasks of

2624-506: The associativity of matrix multiplications, and the errors are used to provide the security. The paper appeared in 2012 after a provisional patent application was filed in 2012. The security of the protocol is proven based on the hardness of solving the LWE problem. In 2014, Peikert presented a key-transport scheme following the same basic idea of Ding's, where the new idea of sending an additional 1-bit signal for rounding in Ding's construction

Kyber - Misplaced Pages Continue

2688-446: The collection comprises more than 4,800 pages and serves companies and authorities as a basis for obtaining certification according to IT-Grundschutz. By obtaining certification, a company demonstrates that it has taken appropriate measures to protect its IT systems against IT security threats. Nationales Cyber-Abwehrzentrum (National Cyber Defence Centre), Cyber-AZ is a cooperative institution of German authorities at federal level for

2752-617: The defense of electronic attacks on IT infrastructures of the Federal Republic of Germany and its economy. It was launched on April 1, 2011 and is located at the BSI. The center is a core element of the Cyber Security Strategy adopted by the German government in 2011. It aims to optimize operational cooperation and coordinate protection and defense measures. This is based on a holistic approach that brings together

2816-402: The deviation from the equality is according to some known noise model. The problem calls for finding the function f {\displaystyle f} , or some close approximation thereof, with high probability. The LWE problem was introduced by Oded Regev in 2005 (who won the 2018 Gödel Prize for this work); it is a generalization of the parity learning problem. Regev showed that

2880-573: The discrete Gaussian distribution on L {\displaystyle L} of width r {\displaystyle r} for a lattice L {\displaystyle L} and real r > 0 {\displaystyle r>0} . The probability of each x ∈ L {\displaystyle x\in L} is proportional to ρ r ( x ) {\displaystyle \rho _{r}(x)} . The discrete Gaussian sampling problem (DGS)

2944-437: The distribution on T {\displaystyle \mathbb {T} } obtained by considering D α {\displaystyle D_{\alpha }} modulo one. The version of LWE considered in most of the results would be L W E q , Ψ α {\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}} The LWE problem described above

3008-575: The given samples { ( a i , b i ) } ⊂ Z q n × T {\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} } as follows. Calculate { ( a i + ( r , 0 , … , 0 ) , b i + ( r k ) / q ) } {\displaystyle \{(\mathbf {a} _{i}+(r,0,\ldots ,0),\mathbf {b} _{i}+(rk)/q)\}} . Send

3072-474: The groundwork for a variety of recent signature algorithms some based directly on the ring learning with errors problem and some which are not tied to the same hard RLWE problems. Federal Office for Information Security The Federal Office for Information Security ( German : Bundesamt für Sicherheit in der Informationstechnik , abbreviated as BSI ) is the German upper-level federal agency in charge of managing computer and communication security for

3136-541: The hardness for LWE. Although the proof of this assertion works for any q {\displaystyle q} , for creating a cryptosystem, the modulus q {\displaystyle q} has to be polynomial in n {\displaystyle n} . Peikert proves that there is a probabilistic polynomial time reduction from the GapSVP ζ , γ {\displaystyle \operatorname {GapSVP} _{\zeta ,\gamma }} problem in

3200-442: The hardness of the LWE problem. The cryptosystem as well as the proof of security and correctness are completely classical. The system is characterized by m , q {\displaystyle m,q} and a probability distribution χ {\displaystyle \chi } on T {\displaystyle \mathbb {T} } . The setting of the parameters used in proofs of correctness and security

3264-511: The input to the LWE problem is a sample of pairs ( x , y ) {\displaystyle (\mathbf {x} ,y)} , where x ∈ Z q n {\displaystyle \mathbf {x} \in \mathbb {Z} _{q}^{n}} and y ∈ Z q {\displaystyle y\in \mathbb {Z} _{q}} , so that with high probability y = f ( x ) {\displaystyle y=f(\mathbf {x} )} . Furthermore,

SECTION 50

#1732780149187

3328-488: The method was submitted to the US National Institute of Standards and Technology (NIST) for its public selection process for a first standard for quantum-safe cryptographic primitives (NISTPQC). It is the only key encapsulation mechanism that has been selected for standardization at the end of the third round of the NIST standardization process. According to a footnote the report announcing the decision, it

3392-764: The one-dimensional Gaussian with zero mean and variance α 2 / ( 2 π ) {\displaystyle \alpha ^{2}/(2\pi )} , that is, the density function is D α ( x ) = ρ α ( x ) / α {\displaystyle D_{\alpha }(x)=\rho _{\alpha }(x)/\alpha } where ρ α ( x ) = e − π ( | x | / α ) 2 {\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}} , and let Ψ α {\displaystyle \Psi _{\alpha }} be

3456-417: The results of this calculation will be distributed according χ {\displaystyle \chi } , but if the samples are uniformly random, these quantities will be distributed uniformly as well. For the other direction, given a solver for the decision problem, the search version can be solved as follows: Recover s {\displaystyle \mathbf {s} } one coordinate at

3520-549: The ring of integers modulo q {\displaystyle q} and let Z q n {\displaystyle \mathbb {Z} _{q}^{n}} denote the set of n {\displaystyle n} - vectors over Z q {\displaystyle \mathbb {Z} _{q}} . There exists a certain unknown linear function f : Z q n → Z q {\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}} , and

3584-506: The same way, and transform our a i {\displaystyle \mathbf {a} _{i}} samples by calculating a i + ( 0 , … , r , … , 0 ) {\displaystyle \mathbf {a} _{i}+(0,\ldots ,r,\ldots ,0)} , where the r {\displaystyle r} is in the j th {\displaystyle j^{\text{th}}} coordinate. Peikert showed that this reduction, with

3648-422: The solver returns a candidate s {\displaystyle \mathbf {s} } , for all i {\displaystyle i} , calculate { ⟨ a i , s ⟩ − b i } {\displaystyle \{\langle \mathbf {a} _{i},\mathbf {s} \rangle -\mathbf {b} _{i}\}} . If the samples are from an LWE distribution, then

3712-404: The transformed samples to the decision solver. If the guess k {\displaystyle k} was correct, the transformation takes the distribution A s , χ {\displaystyle A_{\mathbf {s} ,\chi }} to itself, and otherwise, since q {\displaystyle q} is prime, it takes it to the uniform distribution. So, given

3776-462: The uniform distribution over Z q n × T {\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} } Peikert proposed a system that is secure even against any chosen-ciphertext attack . The idea of using LWE and Ring LWE for key exchange was proposed and filed at the University of Cincinnati in 2011 by Jintai Ding. The idea comes from

3840-411: The use of secure information and communication technology in government, business and society. For example, the BSI develops practice-oriented minimum standards and target group-specific recommendations for handling IT and Internet security. The BSI is also responsible for protecting the IT systems of the federal government. This involves defending against cyber attacks and other technical threats against

3904-440: The various threats in cyberspace: Cyber espionage, cyber spying, cyber terrorism and cyber crime. The goal is a rapid exchange of information, rapid assessments and concrete recommendations for action derived from these. The Alliance for Cyber Security, or Allianz für Cyber-Sicherheit , is an initiative of the German Federal Office for Information Security (BSI). It was launched 2012 in public–private partnership cooperation with

SECTION 60

#1732780149187

3968-973: The worst case to solving L W E q , Ψ α {\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}} using poly ⁡ ( n ) {\displaystyle \operatorname {poly} (n)} samples for parameters α ∈ ( 0 , 1 ) {\displaystyle \alpha \in (0,1)} , γ ( n ) ≥ n / ( α log ⁡ n ) {\displaystyle \gamma (n)\geq n/(\alpha {\sqrt {\log n}})} , ζ ( n ) ≥ γ ( n ) {\displaystyle \zeta (n)\geq \gamma (n)} and q ≥ ( ζ / n ) ω log ⁡ n ) {\displaystyle q\geq (\zeta /{\sqrt {n}})\omega {\sqrt {\log n}})} . The LWE problem serves as

4032-679: Was easy. Then there would be some distinguisher A {\displaystyle {\mathcal {A}}} , who, given samples { ( a i , b i ) } {\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}} , could tell whether they were uniformly random or from A s ′ , χ {\displaystyle A_{\mathbf {s} ',\chi }} . If we need to distinguish uniformly random samples from A s , χ {\displaystyle A_{\mathbf {s} ,\chi }} , where s {\displaystyle \mathbf {s} }

4096-695: Was some set S ⊂ Z q n {\displaystyle {\mathcal {S}}\subset \mathbb {Z} _{q}^{n}} such that | S | / | Z q n | = 1 / poly ⁡ ( n ) {\displaystyle |{\mathcal {S}}|/|\mathbb {Z} _{q}^{n}|=1/\operatorname {poly} (n)} , and for distributions A s ′ , χ {\displaystyle A_{\mathbf {s} ',\chi }} , with s ′ ← S {\displaystyle \mathbf {s} '\leftarrow {\mathcal {S}}} , DLWE

#186813