Learning with errors - Revision history

OAbot: Open access bot: url-access updated in citation with #oabot.

2025-05-24T20:37:26Z

Open access bot: url-access updated in citation with #oabot.

← Previous revision		Revision as of 20:37, 24 May 2025
Line 1:		Line 1:
	{{short description\|Mathematical problem in cryptography}}		{{short description\|Mathematical problem in cryptography}}
	{{technical\|date=October 2018}}		{{technical\|date=October 2018}}
	In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623\|arxiv = 2401.03703}}</ref> and thus to be useful in cryptography.		In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411\|url-access=subscription }}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623\|arxiv = 2401.03703}}</ref> and thus to be useful in cryptography.

	More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let		More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let

Kdlong152: /* growthexperiments-addlink-summary-summary:1|2|0 */

2025-04-20T21:42:00Z

Link suggestions feature: 1 link added.

← Previous revision		Revision as of 21:42, 20 April 2025
Line 93:		Line 93:
	{{Main\|Ring learning with errors signature}}		{{Main\|Ring learning with errors signature}}

	A RLWE version of the classic [[Feige–Fiat–Shamir identification scheme\|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 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.		A RLWE version of the classic [[Feige–Fiat–Shamir identification scheme\|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 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.

	== See also ==		== See also ==

Laura240406: /* Use in cryptography */ replaced with template

2025-03-18T20:25:07Z

Use in cryptography: replaced with template

← Previous revision		Revision as of 20:25, 18 March 2025
Line 91:		Line 91:

	=== Ring learning with errors signature (RLWE-SIG) ===		=== Ring learning with errors signature (RLWE-SIG) ===
	Main ~~article: [[~~Ring learning with errors signature]]		{{Main\|Ring learning with errors signature}}

	A RLWE version of the classic [[Feige–Fiat–Shamir identification scheme\|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 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.		A RLWE version of the classic [[Feige–Fiat–Shamir identification scheme\|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 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.

209.214.195.131: Changed the Z_q from which k is chosen to use blackboard style to match all other uses

2024-05-03T22:27:52Z

Changed the Z_q from which k is chosen to use blackboard style to match all other uses

← Previous revision		Revision as of 22:27, 3 May 2024
Line 31:		Line 31:

	=== Solving search assuming decision ===		=== Solving search assuming decision ===
	For the other direction, given a solver for the decision problem, the search version can be solved as follows: Recover <math>\mathbf{s}</math> one coordinate at a time. To obtain the first coordinate, <math>\mathbf{s}_1</math>, make a guess <math>k \in ~~Z_q~~</math>, and do the following. Choose a number <math>r \in \mathbb{Z}_q</math> uniformly at random. Transform the given samples <math>\{(\mathbf{a}_i,\mathbf{b}_i)\} \subset \mathbb{Z}^n_q \times \mathbb{T}</math> as follows. Calculate <math>\{(\mathbf{a}_i+(r,0,\ldots,0), \mathbf{b}_i + (r k)/q)\}</math>. Send the transformed samples to the decision solver.		For the other direction, given a solver for the decision problem, the search version can be solved as follows: Recover <math>\mathbf{s}</math> one coordinate at a time. To obtain the first coordinate, <math>\mathbf{s}_1</math>, make a guess <math>k \in \mathbb{Z}_q</math>, and do the following. Choose a number <math>r \in \mathbb{Z}_q</math> uniformly at random. Transform the given samples <math>\{(\mathbf{a}_i,\mathbf{b}_i)\} \subset \mathbb{Z}^n_q \times \mathbb{T}</math> as follows. Calculate <math>\{(\mathbf{a}_i+(r,0,\ldots,0), \mathbf{b}_i + (r k)/q)\}</math>. Send the transformed samples to the decision solver.

	If the guess <math>k</math> was correct, the transformation takes the distribution <math>A_{\mathbf{s},\chi}</math> to itself, and otherwise, since <math>q</math> is prime, it takes it to the uniform distribution. So, given a polynomial-time solver for the decision problem that errs with very small probability, since <math>q</math> is bounded by some polynomial in <math>n</math>, it only takes polynomial time to guess every possible value for <math>k</math> and use the solver to see which one is correct.		If the guess <math>k</math> was correct, the transformation takes the distribution <math>A_{\mathbf{s},\chi}</math> to itself, and otherwise, since <math>q</math> is prime, it takes it to the uniform distribution. So, given a polynomial-time solver for the decision problem that errs with very small probability, since <math>q</math> is bounded by some polynomial in <math>n</math>, it only takes polynomial time to guess every possible value for <math>k</math> and use the solver to see which one is correct.

BetaMuKappa: Fixed typo #article-select-source-editor

2024-04-11T03:09:00Z

Fixed typo #article-select-source-editor

← Previous revision		Revision as of 03:09, 11 April 2024
Line 6:		Line 6:
	<math>\mathbb{Z}_q^n </math> denote the set of <math>n</math>-[[Vector (mathematics and physics)\|vectors]] over <math>\mathbb{Z}_q </math>. There exists a certain unknown linear function <math>f:\mathbb{Z}_q^n \rightarrow \mathbb{Z}_q</math>, and the input to the LWE problem is a sample of pairs <math>(\mathbf{x},y)</math>, where <math>\mathbf{x}\in \mathbb{Z}_q^n</math> and <math>y \in \mathbb{Z}_q</math>, so that with high probability <math>y=f(\mathbf{x})</math>. Furthermore, the deviation from the equality is according to some known noise model. The problem calls for finding the function <math>f</math>, or some close approximation thereof, with high probability.		<math>\mathbb{Z}_q^n </math> denote the set of <math>n</math>-[[Vector (mathematics and physics)\|vectors]] over <math>\mathbb{Z}_q </math>. There exists a certain unknown linear function <math>f:\mathbb{Z}_q^n \rightarrow \mathbb{Z}_q</math>, and the input to the LWE problem is a sample of pairs <math>(\mathbf{x},y)</math>, where <math>\mathbf{x}\in \mathbb{Z}_q^n</math> and <math>y \in \mathbb{Z}_q</math>, so that with high probability <math>y=f(\mathbf{x})</math>. Furthermore, the deviation from the equality is according to some known noise model. The problem calls for finding the function <math>f</math>, or some close approximation thereof, with high probability.

	The LWE problem was introduced by [[Oded Regev (computer scientist)\|Oded Regev]] in 2005<ref name="regev05"/> (who won the 2018 [[Gödel Prize]] for this work), it is a generalization of the [[parity learning]] problem. Regev showed that the LWE problem is as hard to solve as several worst-case [[lattice problems]]. Subsequently, the LWE problem has been used as a [[Computational hardness assumption\|hardness assumption]] to create [[Public-key cryptography\|public-key cryptosystems]],<ref name="regev05">Oded Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84–93, http://portal.acm.org/citation.cfm?id=1060590.1060603.</ref><ref name="peikert09">Chris Peikert, “Public-key cryptosystems from the worst-case shortest vector problem: extended abstract,” in Proceedings of the 41st annual ACM symposium on Theory of computing (Bethesda, MD, USA: ACM, 2009), 333–342, http://portal.acm.org/citation.cfm?id=1536414.1536461.</ref> such as the [[ring learning with errors key exchange]] by Peikert.<ref>{{Cite book\|publisher = Springer International Publishing\|date = 2014-10-01\|isbn = 978-3-319-11658-7\|pages = 197–219\|series = Lecture Notes in Computer Science\|first = Chris\|last = Peikert\|editor-first = Michele\|editor-last = Mosca\|doi = 10.1007/978-3-319-11659-4_12\|title = Post-Quantum Cryptography\|volume = 8772\|chapter = Lattice Cryptography for the Internet\|citeseerx = 10.1.1.800.4743\| s2cid=8123895 }}</ref>		The LWE problem was introduced by [[Oded Regev (computer scientist)\|Oded Regev]] in 2005<ref name="regev05"/> (who won the 2018 [[Gödel Prize]] for this work); it is a generalization of the [[parity learning]] problem. Regev showed that the LWE problem is as hard to solve as several worst-case [[lattice problems]]. Subsequently, the LWE problem has been used as a [[Computational hardness assumption\|hardness assumption]] to create [[Public-key cryptography\|public-key cryptosystems]],<ref name="regev05">Oded Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84–93, http://portal.acm.org/citation.cfm?id=1060590.1060603.</ref><ref name="peikert09">Chris Peikert, “Public-key cryptosystems from the worst-case shortest vector problem: extended abstract,” in Proceedings of the 41st annual ACM symposium on Theory of computing (Bethesda, MD, USA: ACM, 2009), 333–342, http://portal.acm.org/citation.cfm?id=1536414.1536461.</ref> such as the [[ring learning with errors key exchange]] by Peikert.<ref>{{Cite book\|publisher = Springer International Publishing\|date = 2014-10-01\|isbn = 978-3-319-11658-7\|pages = 197–219\|series = Lecture Notes in Computer Science\|first = Chris\|last = Peikert\|editor-first = Michele\|editor-last = Mosca\|doi = 10.1007/978-3-319-11659-4_12\|title = Post-Quantum Cryptography\|volume = 8772\|chapter = Lattice Cryptography for the Internet\|citeseerx = 10.1.1.800.4743\| s2cid=8123895 }}</ref>

	== Definition ==		== Definition ==

Wikain: RLWE signature

2024-02-19T16:36:40Z

RLWE signature

← Previous revision		Revision as of 16:36, 19 February 2024
Line 89:		Line 89:

	The security of the protocol is proven based on the hardness of solving the LWE problem. In 2014, Peikert presented a key-transport scheme<ref>{{Cite journal\|last=Peikert\|first=Chris\|date=2014-01-01\|title=Lattice Cryptography for the Internet\|journal=Cryptology ePrint Archive \|url=https://eprint.iacr.org/2014/070}}</ref> 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 is also used. The "new hope" implementation<ref>{{Cite journal\|last1=Alkim\|first1=Erdem\|last2=Ducas\|first2=Léo\|last3=Pöppelmann\|first3=Thomas\|last4=Schwabe\|first4=Peter\|date=2015-01-01\|title=Post-quantum key exchange - a new hope\|journal=Cryptology ePrint Archive \|url=https://eprint.iacr.org/2015/1092}}</ref> selected for Google's post-quantum experiment,<ref>{{Cite news\|url=https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html\|title=Experimenting with Post-Quantum Cryptography\|newspaper=Google Online Security Blog\|access-date=2017-02-08\|language=en-US}}</ref> uses Peikert's scheme with variation in the error distribution.		The security of the protocol is proven based on the hardness of solving the LWE problem. In 2014, Peikert presented a key-transport scheme<ref>{{Cite journal\|last=Peikert\|first=Chris\|date=2014-01-01\|title=Lattice Cryptography for the Internet\|journal=Cryptology ePrint Archive \|url=https://eprint.iacr.org/2014/070}}</ref> 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 is also used. The "new hope" implementation<ref>{{Cite journal\|last1=Alkim\|first1=Erdem\|last2=Ducas\|first2=Léo\|last3=Pöppelmann\|first3=Thomas\|last4=Schwabe\|first4=Peter\|date=2015-01-01\|title=Post-quantum key exchange - a new hope\|journal=Cryptology ePrint Archive \|url=https://eprint.iacr.org/2015/1092}}</ref> selected for Google's post-quantum experiment,<ref>{{Cite news\|url=https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html\|title=Experimenting with Post-Quantum Cryptography\|newspaper=Google Online Security Blog\|access-date=2017-02-08\|language=en-US}}</ref> uses Peikert's scheme with variation in the error distribution.

			=== Ring learning with errors signature (RLWE-SIG) ===
			Main article: [[Ring learning with errors signature]]

			A RLWE version of the classic [[Feige–Fiat–Shamir identification scheme\|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 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.

	== See also ==		== See also ==
	*[[Post-quantum cryptography]]		*[[Post-quantum cryptography]]
			*[[Ring learning with errors]]
	*[[Lattice-based cryptography]]		*[[Lattice-based cryptography]]
	*[[Ring learning with errors key exchange]]		*[[Ring learning with errors key exchange]]

OAbot: Open access bot: arxiv updated in citation with #oabot.

2024-01-15T05:48:53Z

Open access bot: arxiv updated in citation with #oabot.

← Previous revision		Revision as of 05:48, 15 January 2024
Line 1:		Line 1:
	{{short description\|Mathematical problem in cryptography}}		{{short description\|Mathematical problem in cryptography}}
	{{technical\|date=October 2018}}		{{technical\|date=October 2018}}
	In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623}}</ref> and thus to be useful in cryptography.		In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623\|arxiv = 2401.03703}}</ref> and thus to be useful in cryptography.

	More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let		More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let

2602:243:2007:9330:ED46:51B7:EEBA:4178: /* See also */Link key encapsulation protocol that uses this

2024-01-10T13:29:36Z

See also: Link key encapsulation protocol that uses this

← Previous revision		Revision as of 13:29, 10 January 2024
Line 95:		Line 95:
	*[[Ring learning with errors key exchange]]		*[[Ring learning with errors key exchange]]
	*[[Short integer solution problem\|Short integer solution (SIS) problem]]		*[[Short integer solution problem\|Short integer solution (SIS) problem]]
			* [[Kyber]]

	==References==		==References==

Razziabuissa: Remove redundant "in cryptography"

2023-12-20T21:05:21Z

Remove redundant "in cryptography"

← Previous revision		Revision as of 21:05, 20 December 2023
Line 1:		Line 1:
	{{short description\|Mathematical problem in cryptography}}		{{short description\|Mathematical problem in cryptography}}
	{{technical\|date=October 2018}}		{{technical\|date=October 2018}}
	In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used ~~in cryptography~~ to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623}}</ref> and thus to be useful in cryptography.		In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623}}</ref> and thus to be useful in cryptography.

	More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let		More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let

Me, Myself, and I are Here: /* top */ cap

2023-12-20T19:41:16Z

top: cap

← Previous revision		Revision as of 19:41, 20 December 2023
Line 1:		Line 1:
	{{short description\|Mathematical problem in cryptography}}		{{short description\|Mathematical problem in cryptography}}
	{{technical\|date=October 2018}}		{{technical\|date=October 2018}}
	In [[cryptography]], '''~~Learning~~ with errors''' ('''LWE''') is a mathematical problem that is widely used in cryptography to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623}}</ref> and thus to be useful in cryptography.		In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used in cryptography to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623}}</ref> and thus to be useful in cryptography.

	More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let		More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let

← Previous revision		Revision as of 20:37, 24 May 2025
Line 1:		Line 1:
	{{short description\|Mathematical problem in cryptography}}		{{short description\|Mathematical problem in cryptography}}
	{{technical\|date=October 2018}}		{{technical\|date=October 2018}}
	In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623\|arxiv = 2401.03703}}</ref> and thus to be useful in cryptography.		In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411\|url-access=subscription }}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623\|arxiv = 2401.03703}}</ref> and thus to be useful in cryptography.

	More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let		More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let

← Previous revision		Revision as of 05:48, 15 January 2024
Line 1:		Line 1:
	{{short description\|Mathematical problem in cryptography}}		{{short description\|Mathematical problem in cryptography}}
	{{technical\|date=October 2018}}		{{technical\|date=October 2018}}
	In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623}}</ref> and thus to be useful in cryptography.		In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623\|arxiv = 2401.03703}}</ref> and thus to be useful in cryptography.

	More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let		More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let

← Previous revision		Revision as of 21:05, 20 December 2023
Line 1:		Line 1:
	{{short description\|Mathematical problem in cryptography}}		{{short description\|Mathematical problem in cryptography}}
	{{technical\|date=October 2018}}		{{technical\|date=October 2018}}
	In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used ~~in cryptography~~ to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623}}</ref> and thus to be useful in cryptography.		In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623}}</ref> and thus to be useful in cryptography.

	More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let		More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let

← Previous revision		Revision as of 19:41, 20 December 2023
Line 1:		Line 1:
	{{short description\|Mathematical problem in cryptography}}		{{short description\|Mathematical problem in cryptography}}
	{{technical\|date=October 2018}}		{{technical\|date=October 2018}}
	In [[cryptography]], '''~~Learning~~ with errors''' ('''LWE''') is a mathematical problem that is widely used in cryptography to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623}}</ref> and thus to be useful in cryptography.		In [[cryptography]], '''learning with errors''' ('''LWE''') is a mathematical problem that is widely used in cryptography to create secure [[encryption algorithms]].<ref name=":0" /> 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.<ref>{{Cite journal \|last1=Lyubashevsky \|first1=Vadim \|last2=Peikert \|first2=Chris \|last3=Regev \|first3=Oded \|date=November 2013 \|title=On Ideal Lattices and Learning with Errors over Rings \|url=https://dl.acm.org/doi/10.1145/2535925 \|journal=Journal of the ACM \|language=en \|volume=60 \|issue=6 \|pages=1–35 \|doi=10.1145/2535925 \|s2cid=1606347 \|issn=0004-5411}}</ref> In more technical terms, it refers to the [[computational problem]] of inferring a linear <math>n</math>-ary function <math>f</math> over a finite [[Ring (mathematics)\|ring]] from given samples <math>y_i = f(\mathbf{x}_i)</math> some of which may be erroneous. The LWE problem is conjectured to be hard to solve,<ref name=":0">{{Cite journal \|doi = 10.1145/1568318.1568324\|title = On lattices, learning with errors, random linear codes, and cryptography\|journal = Journal of the ACM\|volume = 56\|issue = 6\|pages = 1–40\|year = 2009\|last1 = Regev\|first1 = Oded\|s2cid = 207156623}}</ref> and thus to be useful in cryptography.

	More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let		More precisely, the LWE problem is defined as follows. Let <math>\mathbb{Z}_q </math> denote the ring of integers [[Modular arithmetic\|modulo]] <math>q</math> and let