Misplaced Pages

#70929

48-695: LWE may denote: Learning with errors , a computational problem used in cryptography Lightweight Ethernet, a nickname for the IEC 61162-450 protocol Latin World Entertainment Left-wing extremism the ISO 639 code for the Lewo Eleng language the IATA code for Wonopito Airport Lincoln-Way East High School Topics referred to by

96-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

144-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

192-583: A converse to Minkowski's theorem and exploring its applications in joint works with his student Noah Stephens-Davidowitz and his former postdoc Daniel Dadush. In addition to his work on lattices, Regev has also done work in a large number of other areas in theoretical computer science and mathematics. These include quantum computing , communication complexity , hardness of approximation , online algorithms , combinatorics , probability , and dimension reduction . He has also recently become interested in topics in biology, and particularly RNA splicing . Regev

240-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 }}

288-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^{*}}

336-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

384-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

432-479: 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,

480-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

528-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}}

SECTION 10

#1732787415071

576-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

624-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

672-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

720-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

768-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

816-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

864-900: Is an associate editor in chief of the journal Theory of Computing , and is a co-founder and organizer of the TCS+ online seminar series. In August 2023 Regev published a preprint describing an algorithm to factor integers with ∼ O ( n 3 / 2 ) {\displaystyle \sim O(n^{3/2})} quantum gates which would be more efficient than Shor's algorithm which uses ∼ O ( n 2 ) {\displaystyle \sim O(n^{2})} , but would require more qubits ∼ O ( n 3 / 2 ) {\displaystyle \sim O(n^{3/2})} of quantum memory against Shor's ∼ O ( n )   {\displaystyle \sim O(n)\ } . A variant has been proposed that could reduce

912-409: Is best known for his work in lattice-based cryptography , and in particular for introducing the learning with errors problem. Oded Regev earned his B.Sc. in 1995, M.Sc. in 1997, and Ph.D. in 2001, all from Tel Aviv University . He completed his Ph.D. at the age of 21, advised by Yossi Azar, with a thesis titled "Scheduling and Load Balancing." He held faculty positions at Tel Aviv University and

960-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 + ⟨

1008-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 { (

SECTION 20

#1732787415071

1056-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

1104-505: Is different from Wikidata All article disambiguation pages All disambiguation pages Learning with errors More precisely, the LWE problem is defined as follows. Let Z q {\displaystyle \mathbb {Z} _{q}} denote the ring of integers modulo q {\displaystyle q} and let Z q n {\displaystyle \mathbb {Z} _{q}^{n}} denote

1152-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}

1200-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

1248-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 }}

1296-667: The École Normale Supérieure before joining the Courant institute. Regev has done extensive work on lattices . He is best known for introducing the learning with errors problem (LWE), for which he won the 2018 Gödel Prize . As the citation reads: Regev’s work has ushered in a revolution in cryptography, in both theory and practice. On the theoretical side, LWE has served as a simple and yet amazingly versatile foundation for nearly every kind of cryptographic object imaginable—along with many that were unimaginable until recently, and which still have no known constructions without LWE. Toward

1344-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

1392-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

1440-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

1488-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)

LWE - Misplaced Pages Continue

1536-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

1584-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

1632-498: 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. Oded Regev (computer scientist) Oded Regev (Hebrew: עודד רגב ;born 1980 or 1979) is an Israeli-American theoretical computer scientist and mathematician. He is a professor of computer science at the Courant institute at New York University . He

1680-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

1728-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

1776-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

1824-492: The practical end, LWE and its direct descendants are at the heart of several efficient real-world cryptosystems. Regev's most influential other work on lattices includes cryptanalysis of the GGH and NTRU signature schemes in joint work with Phong Q. Nguyen, for which they won a best paper award at Eurocrypt 2006; introducing the ring learning with errors problem in joint work with Chris Peikert and Vadim Lyubashevsky; and proving

1872-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

1920-403: The same term [REDACTED] This disambiguation page lists articles associated with the title LWE . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=LWE&oldid=1217012133 " Category : Disambiguation pages Hidden categories: Short description

1968-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

LWE - Misplaced Pages Continue

2016-400: 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 the input to the LWE problem is

2064-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

2112-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

2160-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

2208-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

2256-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} }

2304-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

#70929