以下正文同步自 Hacker News 最新，版权归原站所有，已转换为易读排版。

In cryptography, learning with errors (LWE) is a mathematical problem that is widely used to create secure encryption algorithms.[1] 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.[2] In more technical terms, it refers to the computational problem of inferring a linear

{\displaystyle n}

-ary function

{\displaystyle f}

over a finite ring from given samples

= f (

)

{\displaystyle y_{i}=f(\mathbf {x} _{i})}

some of which may be erroneous. The LWE problem is conjectured to be hard to solve,[1] and thus to be useful in cryptography.

More precisely, the LWE problem is defined as follows. Let

{\displaystyle \mathbb {Z} _{q}}

denote the ring of integers modulo

{\displaystyle q}

and let

{\displaystyle \mathbb {Z} _{q}^{n}}

denote the set of

{\displaystyle n}

-vectors over

{\displaystyle \mathbb {Z} _{q}}

. There exists a certain unknown linear function

f :

→

{\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}}

, and the input to the LWE problem is a sample of pairs

(

, y )

{\displaystyle (\mathbf {x} ,y)}

, where

∈

{\displaystyle \mathbf {x} \in \mathbb {Z} _{q}^{n}}

and

y ∈

{\displaystyle y\in \mathbb {Z} _{q}}

, so that with high probability

y

f (

)

{\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

{\displaystyle f}

, or some close approximation thereof, with high probability.

The LWE problem was introduced by Oded Regev in 2005[3] (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,[3][4] such as the ring learning with errors key exchange by Peikert.[5]

Denote by

{\displaystyle \mathbb {T} =\mathbb {R} /\mathbb {Z} }

the additive group on reals modulo one. Let

∈

{\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}

be a fixed vector. Let

{\displaystyle \phi }

be a fixed probability distribution over

{\displaystyle \mathbb {T} }

. Denote by

, ϕ

{\displaystyle A_{\mathbf {s} ,\phi }}

the distribution on

{\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 }}

is to find

∈

{\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}

, given access to polynomially many samples of choice from

, ϕ

{\displaystyle A_{\mathbf {s} ,\phi }}

For every 0"}}'>0}">

{\displaystyle \alpha >0}

0}"/>, denote by

{\displaystyle D_{\alpha }}

the one-dimensional Gaussian with zero mean and variance

( 2 π )

{\displaystyle \alpha ^{2}/(2\pi )}

, that is, the density function is

( x )

{\displaystyle D_{\alpha }(x)=\rho _{\alpha }(x)/\alpha }

where

( x )

− π (

)

{\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}}

, and let

{\displaystyle \Psi _{\alpha }}

be the distribution on

{\displaystyle \mathbb {T} }

obtained by considering

{\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 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

{\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }

(practically, some discretized version of it). Regev[3] showed that the decision and search versions are equivalent when

{\displaystyle q}

is a prime bounded by some polynomial in

{\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

{ (

) } ⊂

{\displaystyle {(\mathbf {a} _{i},\mathbf {b} _{i})}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }

. If the solver returns a candidate

{\displaystyle \mathbf {s} }

, for all

{\displaystyle i}

, calculate

{ ⟨

⟩ −

}

{\displaystyle {\langle \mathbf {a} _{i},\mathbf {s} \rangle -\mathbf {b} _{i}}}

. If the samples are from an LWE distribution, then 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

{\displaystyle \mathbf {s} }

one coordinate at a time. To obtain the first coordinate,

{\displaystyle \mathbf {s} _{1}}

, make a guess

k ∈

{\displaystyle k\in \mathbb {Z} _{q}}

, and do the following. Choose a number

r ∈

{\displaystyle r\in \mathbb {Z} _{q}}

uniformly at random. Transform the given samples

{ (

) } ⊂

{\displaystyle {(\mathbf {a} _{i},\mathbf {b} _{i})}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }

as follows. Calculate

{ (

( r , 0 , … , 0 ) ,

( r k )

q ) }

{\displaystyle {(\mathbf {a} _{i}+(r,0,\ldots ,0),\mathbf {b} _{i}+(rk)/q)}}

. Send the transformed samples to the decision solver.

If the guess

{\displaystyle k}

was correct, the transformation takes the distribution

, χ

{\displaystyle A_{\mathbf {s} ,\chi }}

to itself, and otherwise, since

{\displaystyle q}

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

{\displaystyle q}

is bounded by some polynomial in

{\displaystyle n}

, it only takes polynomial time to guess every possible value for

{\displaystyle k}

and use the solver to see which one is correct.

After obtaining

{\displaystyle \mathbf {s} _{1}}

, we follow an analogous procedure for each other coordinate

{\displaystyle \mathbf {s} _{j}}

. Namely, we transform our

{\displaystyle \mathbf {b} _{i}}

samples the same way, and transform our

{\displaystyle \mathbf {a} _{i}}

samples by calculating

( 0 , … , r , … , 0 )

{\displaystyle \mathbf {a} _{i}+(0,\ldots ,r,\ldots ,0)}

, where the

{\displaystyle r}

is in the

{\displaystyle j^{\text{th}}}

coordinate.[3]

Peikert[4] showed that this reduction, with a small modification, works for any

{\displaystyle q}

that is a product of distinct, small (polynomial in

{\displaystyle n}

) primes. The main idea is if

q

⋯

{\displaystyle q=q_{1}q_{2}\cdots q_{t}}

, for each

ℓ

{\displaystyle q_{\ell }}

, guess and check to see if

{\displaystyle \mathbf {s} _{j}}

is congruent to

mod

ℓ

{\displaystyle 0\mod q_{\ell }}

, and then use the Chinese remainder theorem to recover

{\displaystyle \mathbf {s} _{j}}

Regev[3] showed the random self-reducibility of the LWE and DLWE problems for arbitrary

{\displaystyle q}

and

{\displaystyle \chi }

. Given samples

{ (

) }

{\displaystyle {(\mathbf {a} _{i},\mathbf {b} _{i})}}

from

, χ

{\displaystyle A_{\mathbf {s} ,\chi }}

, it is easy to see that

{ (

⟨

⟩ )

q }

{\displaystyle {(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q}}

are samples from

, χ

{\displaystyle A_{\mathbf {s} +\mathbf {t} ,\chi }}

So, suppose there was some set

⊂

{\displaystyle {\mathcal {S}}\subset \mathbb {Z} _{q}^{n}}

such that

= 1

poly ⁡ ( n )

{\displaystyle |{\mathcal {S}}|/|\mathbb {Z} _{q}^{n}|=1/\operatorname {poly} (n)}

, and for distributions

′

, χ

{\displaystyle A_{\mathbf {s} ',\chi }}

, with

′

←

{\displaystyle \mathbf {s} '\leftarrow {\mathcal {S}}}

, DLWE was easy.

Then there would be some distinguisher

{\displaystyle {\mathcal {A}}}

, who, given samples

{ (

) }

{\displaystyle {(\mathbf {a} _{i},\mathbf {b} _{i})}}

, could tell whether they were uniformly random or from

′

, χ

{\displaystyle A_{\mathbf {s} ',\chi }}

. If we need to distinguish uniformly random samples from

, χ

{\displaystyle A_{\mathbf {s} ,\chi }}

, where

{\displaystyle \mathbf {s} }

is chosen uniformly at random from

{\displaystyle \mathbb {Z} _{q}^{n}}

, we could simply try different values

{\displaystyle \mathbf {t} }

sampled uniformly at random from

{\displaystyle \mathbb {Z} _{q}^{n}}

, calculate

{ (

⟨

⟩ )

q }

{\displaystyle {(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q}}

and feed these samples to

{\displaystyle {\mathcal {A}}}

. Since

{\displaystyle {\mathcal {S}}}

comprises a large fraction of

{\displaystyle \mathbb {Z} _{q}^{n}}

, with high probability, if we choose a polynomial number of values for

{\displaystyle \mathbf {t} }

, we will find one such that

∈

{\displaystyle \mathbf {s} +\ma

正文由探How 从来源站点 RSS 同步，内容未经改写；遇到排版缺失或需要图片、视频时请以原文为准。

Learning with Errors

y

( x )

( x )

q