تعلم بالأخطاء

(تم التحويل من Learning with errors)

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 خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -ary function خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} over a finite ring from given samples خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\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 خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_q } denote the ring of integers modulo and let خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_q^n } denote the set of خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -vectors over خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_q } . There exists a certain unknown linear function خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle f:\mathbb{Z}_q^n \rightarrow \mathbb{Z}_q} , and the input to the LWE problem is a sample of pairs خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathbf{x},y)} , where خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{x}\in \mathbb{Z}_q^n} and خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle y \in \mathbb{Z}_q} , so that with high probability خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\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 خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\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]

Definition

Denote by خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{T}=\mathbb{R}/\mathbb{Z}} the additive group on reals modulo one. Let خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s} \in \mathbb{Z}_q^n} be a fixed vector. Let خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} be a fixed probability distribution over خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{T}} . Denote by خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{\mathbf{s},\phi}} the distribution on خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_q^n \times \mathbb{T}} obtained as follows.

  1. Pick a vector خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{a}\in \mathbb{Z}_q^n} from the uniform distribution over خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_q^n} ,
  2. Pick a number خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle e\in\mathbb{T}} from the distribution خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} ,
  3. Evaluate خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle t=\langle \mathbf{a},\mathbf{s} \rangle /q + e} , where خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \langle \mathbf{a},\mathbf{s} \rangle = \sum_{i=1}^n a_i s_i} is the standard inner product in خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_q^n} , the division is done in the field of reals (or more formally, this "division by خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} " is notation for the group homomorphism خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_q \longrightarrow \mathbb{T}} mapping خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 \in \mathbb{Z}_q } to خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/q + \mathbb{Z} \in \mathbb{T}} ), and the final addition is in خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{T}} .
  4. Output the pair خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathbf{a},t)} .

The learning with errors problem خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{LWE}_{q,\phi}} is to find خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s} \in \mathbb{Z}_q^n} , given access to polynomially many samples of choice from خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{\mathbf{s},\phi}} .

For every خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha > 0} , denote by خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_\alpha} the one-dimensional Gaussian with zero mean and variance خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha^2/(2\pi)} , that is, the density function is خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_\alpha(x)=\rho_\alpha(x)/\alpha} where خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho_\alpha(x)=e^{-\pi(|x|/\alpha)^2}} , and let خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Psi_\alpha} be the distribution on خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{T}} obtained by considering خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_\alpha} modulo one. The version of LWE considered in most of the results would be خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{LWE}_{q,\Psi_\alpha}}

Decision version

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 خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\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 خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} is a prime bounded by some polynomial in خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .

Solving decision assuming search

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 خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{(\mathbf{a}_i,\mathbf{b}_i)\} \subset \mathbb{Z}^n_q \times \mathbb{T}} . If the solver returns a candidate خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s}} , for all خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} , calculate خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\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 خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \chi} , but if the samples are uniformly random, these quantities will be distributed uniformly as well.

Solving search assuming decision

For the other direction, given a solver for the decision problem, the search version can be solved as follows: Recover خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s}} one coordinate at a time. To obtain the first coordinate, خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s}_1} , make a guess خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \in \mathbb{Z}_q} , and do the following. Choose a number خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle r \in \mathbb{Z}_q} uniformly at random. Transform the given samples خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{(\mathbf{a}_i,\mathbf{b}_i)\} \subset \mathbb{Z}^n_q \times \mathbb{T}} as follows. Calculate خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{(\mathbf{a}_i+(r,0,\ldots,0), \mathbf{b}_i + (r k)/q)\}} . Send the transformed samples to the decision solver.

If the guess خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} was correct, the transformation takes the distribution خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{\mathbf{s},\chi}} to itself, and otherwise, since خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\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 خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} is bounded by some polynomial in خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , it only takes polynomial time to guess every possible value for خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} and use the solver to see which one is correct.

After obtaining خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s}_1} , we follow an analogous procedure for each other coordinate خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s}_j} . Namely, we transform our خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{b}_i} samples the same way, and transform our خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{a}_i} samples by calculating خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{a}_i + (0, \ldots, r, \ldots, 0)} , where the خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} is in the خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle j^\text{th}} coordinate.[3]

Peikert[4] showed that this reduction, with a small modification, works for any خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} that is a product of distinct, small (polynomial in خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} ) primes. The main idea is if خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q = q_1 q_2 \cdots q_t} , for each خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_{\ell}} , guess and check to see if خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s}_j} is congruent to خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \mod q_{\ell}} , and then use the Chinese remainder theorem to recover خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s}_j} .

Average case hardness

Regev[3] showed the random self-reducibility of the LWE and DLWE problems for arbitrary خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} and خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \chi} . Given samples خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{(\mathbf{a}_i,\mathbf{b}_i)\}} from خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{\mathbf{s},\chi}} , it is easy to see that خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{(\mathbf{a}_i,\mathbf{b}_i + \langle \mathbf{a}_i, \mathbf{t} \rangle)/q\}} are samples from خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{\mathbf{s} + \mathbf{t},\chi}} .

So, suppose there was some set خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{S} \subset \mathbb{Z}_q^n} such that خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathcal{S}|/|\mathbb{Z}_q^n| = 1/\operatorname{poly}(n)} , and for distributions خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{\mathbf{s}',\chi}} , with خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s}' \leftarrow \mathcal{S}} , DLWE was easy.

Then there would be some distinguisher خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} , who, given samples خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{(\mathbf{a}_i,\mathbf{b}_i) \}} , could tell whether they were uniformly random or from خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{\mathbf{s}',\chi}} . If we need to distinguish uniformly random samples from خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{\mathbf{s},\chi}} , where خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s}} is chosen uniformly at random from خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_q^n} , we could simply try different values خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{t} } sampled uniformly at random from خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_q^n} , calculate خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{(\mathbf{a}_i,\mathbf{b}_i + \langle \mathbf{a}_i, \mathbf{t} \rangle)/q\}} and feed these samples to خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} . Since خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{S}} comprises a large fraction of خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_q^n} , with high probability, if we choose a polynomial number of values for خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{t}} , we will find one such that خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s} + \mathbf{t} \in \mathcal{S}} , and خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} will successfully distinguish the samples.

Thus, no such خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{S}} can exist, meaning LWE and DLWE are (up to a polynomial factor) as hard in the average case as they are in the worst case.

Hardness results

Regev's result

For a n-dimensional lattice خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} , let smoothing parameter خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta_\varepsilon(L)} denote the smallest خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} such that خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho_{1/s}(L^*\setminus \{\mathbf{0}\}) \leq \varepsilon } where خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle L^*} is the dual of خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} and خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\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 خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_{L,r}} denote the discrete Gaussian distribution on خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} of width خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} for a lattice خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} and real خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle r>0} . The probability of each خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in L} is proportional to خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho_r(x)} .

The discrete Gaussian sampling problem(DGS) is defined as follows: An instance of خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle DGS_\phi} is given by an خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -dimensional lattice خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} and a number خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle r \geq \phi(L)} . The goal is to output a sample from خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_{L,r}} . Regev shows that there is a reduction from خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{GapSVP}_{100\sqrt{n}\gamma(n)}} to خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle DGS_{\sqrt{n}\gamma(n)/\lambda(L^*)}} for any function خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma(n) \ge 1} .

Regev then shows that there exists an efficient quantum algorithm for خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle DGS_{\sqrt{2n}\eta_\varepsilon(L)/\alpha}} given access to an oracle for خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{LWE}_{q,\Psi_\alpha}} for integer خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} and خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha \in (0,1)} such that خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha q > 2\sqrt{n}} . This implies the hardness for LWE. Although the proof of this assertion works for any خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} , for creating a cryptosystem, the modulus خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} has to be polynomial in خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .

Peikert's result

Peikert proves[4] that there is a probabilistic polynomial time reduction from the خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{GapSVP}_{\zeta,\gamma}} problem in the worst case to solving خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{LWE}_{q,\Psi_\alpha}} using خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{poly}(n)} samples for parameters خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha \in (0,1)} , خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma(n)\geq n/(\alpha \sqrt{\log n})} , خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \zeta(n) \geq \gamma(n)} and خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q \geq (\zeta/\sqrt{n}) \omega \sqrt{\log n})} .

Use in cryptography

The LWE problem serves as a versatile problem used in construction of several[3][4][6][7] cryptosystems. In 2005, Regev[3] showed that the decision version of LWE is hard assuming quantum hardness of the lattice problems خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{GapSVP}_\gamma} (for خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} as above) and خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{SIVP}_t} with خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle t=O(n/\alpha) } ). In 2009, Peikert[4] proved a similar result assuming only the classical hardness of the related problem خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\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.

Public-key cryptosystem

Regev[3] proposed a public-key cryptosystem based on 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 خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle m,q} and a probability distribution خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \chi} on خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{T}} . The setting of the parameters used in proofs of correctness and security is

  • خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle q \geq 2 } , usually a prime number between خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2} and خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2n^2} .
  • خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle m=(1+\varepsilon)(n+1) \log q} for an arbitrary constant خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon}
  • خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \chi=\Psi_{\alpha(n)}} for خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha(n) \in o(1/\sqrt{n}\log n)} , where خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Psi_\beta} is a probability distribution obtained by sampling a normal variable with mean خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} and standard variation خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{\beta}{\sqrt{2\pi}}} and reducing the result modulo خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} .

The cryptosystem is then defined by:

  • Private key: Private key is an خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{s}\in \mathbb{Z}^n_q} chosen uniformly at random.
  • Public key: Choose خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} vectors خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{a}_1,\ldots,\mathbf{a}_m \in \mathbb{Z}^n_q} uniformly and independently. Choose error offsets خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_1,\ldots,e_m \in \mathbb{T}} independently according to خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \chi} . The public key consists of خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathbf{a}_i,b_i=\langle \mathbf{a}_i,\mathbf{s} \rangle/q + e_i)^m_{i=1}}
  • Encryption: The encryption of a bit خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in \{0,1\}} is done by choosing a random subset خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} of خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle [m]} and then defining خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{Enc}(x)} as
خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\sum_{i \in S} \mathbf{a}_i, \frac x 2 + \sum_{i \in S} b_i\right)}
  • Decryption: The decryption of خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathbf{a},b)} is خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} if خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle b-\langle \mathbf{a}, \mathbf{s} \rangle/q} is closer to خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} than to خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{2}} , and خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} otherwise.

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 خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} and خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} can be used to distinguish between خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{s,\chi}} and the uniform distribution over خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}^n_q \times \mathbb{T}}

CCA-secure cryptosystem

Peikert[4] proposed a system that is secure even against any chosen-ciphertext attack.

Key exchange

المقالة الرئيسية: Ring learning with errors key exchange

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 the associativity of matrix multiplications, and the errors are used to provide the security. The paper[8] 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[9] 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[10] selected for Google's post-quantum experiment,[11] uses Peikert's scheme with variation in the error distribution.

Ring learning with errors signature (RLWE-SIG)

المقالة الرئيسية: 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 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.

انظر أيضاً

References

  1. ^ أ ب Regev, Oded (2009). "On lattices, learning with errors, random linear codes, and cryptography". Journal of the ACM. 56 (6): 1–40. arXiv:2401.03703. doi:10.1145/1568318.1568324. S2CID 207156623.
  2. ^ Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (November 2013). "On Ideal Lattices and Learning with Errors over Rings". Journal of the ACM (in الإنجليزية). 60 (6): 1–35. doi:10.1145/2535925. ISSN 0004-5411. S2CID 1606347.
  3. ^ أ ب ت ث ج ح خ د 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.
  4. ^ أ ب ت ث ج ح 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.
  5. ^ Peikert, Chris (2014-10-01). "Lattice Cryptography for the Internet". In Mosca, Michele (ed.). Post-Quantum Cryptography. Lecture Notes in Computer Science. Vol. 8772. Springer International Publishing. pp. 197–219. CiteSeerX 10.1.1.800.4743. doi:10.1007/978-3-319-11659-4_12. ISBN 978-3-319-11658-7. S2CID 8123895.
  6. ^ Chris Peikert and Brent Waters, “Lossy trapdoor functions and their applications,” in Proceedings of the 40th annual ACM symposium on Theory of computing (Victoria, British Columbia, Canada: ACM, 2008), 187-196, http://portal.acm.org/citation.cfm?id=1374406.
  7. ^ Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan, “Trapdoors for hard lattices and new cryptographic constructions,” in Proceedings of the 40th annual ACM symposium on Theory of computing (Victoria, British Columbia, Canada: ACM, 2008), 197-206, http://portal.acm.org/citation.cfm?id=1374407.
  8. ^ Lin, Jintai Ding, Xiang Xie, Xiaodong (2012-01-01). "A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem". Cryptology ePrint Archive.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  9. ^ Peikert, Chris (2014-01-01). "Lattice Cryptography for the Internet". Cryptology ePrint Archive.
  10. ^ Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015-01-01). "Post-quantum key exchange - a new hope". Cryptology ePrint Archive.
  11. ^ "Experimenting with Post-Quantum Cryptography". Google Online Security Blog (in الإنجليزية الأمريكية). Retrieved 2017-02-08.

قالب:Computational hardness assumptions

?
تمّ الاسترجاع من "https://www.marefa.org/w/index.php?title=تعلم_بالأخطاء&oldid=4174819"