Wikipedia Article of the Day
Randomly selected articles from my personal browsing history
In cryptography, learning with errors (LWE) 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 a finite ring from given samples yi=f(xi){\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 Zq{\displaystyle \mathbb {Z} _{q}} denote the ring of integers modulo q{\displaystyle q} and let Zqn{\displaystyle \mathbb {Z} _{q}^{n}} denote the set of n{\displaystyle n}-vectors over Zq{\displaystyle \mathbb {Z} _{q}}. There exists a certain unknown linear function f:Zqn→Zq{\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}}, and the input to the LWE problem is a sample of pairs (x,y){\displaystyle (\mathbf {x} ,y)}, where x∈Zqn{\displaystyle \mathbf {x} \in \mathbb {Z} _{q}^{n}} and y∈Zq{\displaystyle y\in \mathbb {Z} _{q}}, so that with high probability y=f(x){\displaystyle y=f(\mathbf {x} )}. Furthermore, 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 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.
History
May 26
Bluesky (social network)
May 25
Zero-crossing rate
May 24
Fowler–Noll–Vo hash function
May 23
Fourier inversion theorem
May 22
Pantone
May 21
DigiCert
May 20
Little Boy Blue
May 19
Kim Bauer
May 18
Snowflake ID
May 17
Go (programming language)
May 16
Criticism of C++
May 15
Assembly language
May 14
Pitch detection algorithm
May 13
Ethyl acetate
May 12
Zigbee
May 11
AutoCAD DXF
May 10
Convex function
May 9
Raised-cosine filter
May 8
Boy or girl paradox
May 7
netcat
May 6
Idiot plot
May 5
Blackboard bold
May 4
Zero crossing
May 3
ASCII
May 2
Inverse trigonometric functions
May 1
RAID
Apr 30
Arccos
Apr 29
Real-time operating system
Apr 28
Unidirectional network
Apr 27
SD card