오류와 함께 학습

이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 제거하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2018년 10월) (이 템플릿 메시지 제거 방법 및 시기 학습)

오류가 있는 학습(LWE)은 주어진 샘플 ${\displaystyle {yi}_{}}$= f${\displaystyle }$( ${\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ )${\displaystyle y_{i}=f(\mathbf {x} _{i})$에서 유한 링에 대해$$ $선형{\displaystyle }$ n ${\$$displaystyf f}$을(를$)$ 유추하는 계산 문제인데, 이 중 일부는 오류가$$ 있을 수 있다.LWE 문제는 해결이 어려울 것으로 추측되며,^[1] 따라서 암호 해독에 유용하다.

보다 정확히 말하면, LWE 문제는 다음과 같이 정의된다.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 ${\displaystyle f}$${\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}}$, and the input to the LWE problem is a sample of pairs ${\displaystyle (\mathbf {x} ,y)}$, where ${\displaystyle \mathbf {x} \in \mathbb {Z} _{q}^{n}}$ and ${\displaystyle y\in \mathbb {Z}$$_{q$ 높은 $확률$의 ${\displaystyle y}$= ${\displaystyle f\mathbf{}}$( x$){\displaystyle y=f(\mathbf {x}$ $)\}.$ 더욱이 동등성으로부터의 편차는 알려진 소음 모델에 따른다.문제는 높은 확률로 기능 $f{\displaystyle }$ ${\displaystyle f}$ 또는$$그 근사치를 찾아야 한다.

LWE 문제는 2005년^[2] 오데드 레게브(이 작품으로 2018년 괴델상을 수상한 사람)가 도입한 것으로 패리티 학습 문제의 일반화다.Regev는 LWE 문제가 몇몇 최악의 경우 격자 문제만큼 해결하기 어렵다는 것을 보여주었다.그 후, LWE 문제는 Peikert의 오류 키 교환이 있는 링 학습과 같은 공개 ^[2][3]키 암호 시스템을 만들기 위한 경도 가정으로 사용되어 왔다.^[4]

정의

$T{\displaystyle \mathbb{}}$= ${\displaystyle R\mathbb{}}$/ ${\displaystyle Z\mathbb{}}$ ${\$ reals modulo 1에 대한 가법 그룹 $}.$${\displaystyle \in }$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$ {$Z} _{q}^{n}}}}}}$을 고정 벡터가 되게$$ 한다.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.

1. $Z{\displaystyle {\mathbb{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ {\$displaybbb$ {$a} \mathb {Z} _{q}^{n}$에서 벡터 a${\displaystyle {\mathbb{}}_{}^{}}$ Z$$ $q{\displaystyle \mathbf{}}$ {${\displaystyle {}_{}^{}}$}을(를) 선택하십시오$.$ {\$displaystyle \mathb {Z} _{q}^{n}}},$
2. $distribution{\displaystyle }$ ${\$$displaystyle \\in \mathb {T}$ 분포에서$$ 숫자 $e{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle T\mathbb{}}$ ${\$$displaystyle \pi }$을(를) 선택하십시오$.$
3. Evaluate ${\displaystyle t=\langle \mathbf {a} ,\mathbf {s} \rangle /q+e}$, where ${\displaystyle \textstyle \langle \mathbf {a} ,\mathbf {s} \rangle =\sum _{i=1}^{n}a_{i}s_{i}}$ is the standard inner product in ${\displaystyle \mathbb {Z} _$${q}^{n}}$, the division is done in the field of reals (or more formally, this "division by ${\displaystyle q}$" is notation for the group homomorphism ${\displaystyle \mathbb {Z} _{q}\longrightarrow \mathbb {T} }$ mapping ${\displaystyle 1\in \mathbb {Z} _{q}}$ to ${\displa$$ystyle 1/q+\mathb {Z} \in \mathb {T})$에서 최종 $추가$는 T ${\${$T}$에 있다$.$
4. ${\displaystyle 페어\mathbf{}(,}$ ${\displaystyle t}$) ${\displaystyle(\mathbf {a},t)}$을(를) 출력하십시오$.$

The learning with errors problem ${\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 }}$.

모든 α<>를 사용하여 들어 0{\displaystyle \alpha>0}, D로 표시한다.({\displaystyle D_{\alpha}}제로 평균과 가변성 α 2/(2π){\displaystyle \alpha ^{2}(2\pi)을 1차원 Gaussian}, 밀도 기능은 D(()))ρ α())/α{\displaystyle D_{\alpha}())=\rho_{\alph.는}())$/\alpha }$ where ${\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.대부분의 결과에서 고려된 LWE 버전은 $L{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathrm{W}}_{}}$ ${\displaystyle {}_{}}$ ,${\displaystyle {{\alpha }_{}}_{}}$ ${\$ {$LWE} _{q,\PSI _{\alpha }}}$일 것이다.

의사 결정 버전

위에서 설명한 LWE 문제는 문제의 검색 버전이다.결정판(DLWE)에서 목표는 소음이 많은 내부 제품과 균일하게 무작위 $샘플$을 ${\displaystyle {}_{}^{}}$ n${\displaystyle {}_{}^{}}$× ${\displaystyle T\mathbb{}}$ ${\$에서 구별하는 것이다($$실제로, 일부 검증되지 않은 버전).Regev는^[2] 결정 $및{\displaystyle }$ 검색 버전이$q$ {\$displaystyle$q}이$(가)$ n {\$displaystyle$ n}의 일부 다항식 경계인 경우 동등하다는 것을 보여주었다$.$

검색을 가정하여 의사 결정 해결

직관적으로, 만약 우리가 검색 문제에 대한 절차를 가지고 있다면, 의사결정 버전은 쉽게 풀릴 수 있다: 단지 결정 문제에 대한 입력 샘플을 검색 문제에 대한 해결사에게 제공하는 것이다.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 \{⟨{\mathbf{a}}_i,\mathbf{s}⟩-{\mathbf{b}}_{}}$${\displaystyle i_{}}$ ${\displaystyle \{\langle \mathbf {a} _{i}\mathbf {s} \rangele -\mathbf {b} _{i$ 샘플이 LWE 분포에서 가져온 것이라면 이 계산 결과는 $distributed{\displaystyle }$ ${\displaystylement \chi$}에 따라 분산되지만, 이러한 수량도 균일하게 된다$.$

결정을 가정하여 검색 해결

다른 방향의 경우, 의사결정 문제의 해결사가 주어지면, 검색 버전은 다음과 같이 해결할 수 있다.$한{\displaystyle \mathbf{}}$ 번에 한 좌표씩$$$${\$displaystyle \mathbf${s$}$을(를 복구하십시오.첫 번째 좌표를 구하려면 s ${\displaystyle {\mathrm{}}_{}}$ ${\$$k{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {}_{}}$ ${\displaystyle q_{}}$ ${\$를 추측하고 다음을 수행하십시오.숫자 $r{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\$를 랜덤으로 균일하게$$ 선택하십시오.지정된 샘플${\displaystyle }${${\displaystyle }$(${\displaystyle {}_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle \}}$ ${\displaystyle \subset }$ Z ${\displaystyle q\mathbb{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ T ${\$을 다음과 같이$$ 변환하십시오.$\{{\displaystyle }$( ${\displaystyle {}_{}}$+ (${\displaystyle r,}$ ${\displaystyle 0,}$…,${\displaystyle 0}$)${\displaystyle }$, ${\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$+${\displaystyle }$( r ${\displaystyle k}$)${\displaystyle }$/ ${\displaystyle q}$ ${\displaystyle )}$} ${\displaystyle$\{(\$mathbf {a} _{i}+(r,0,\ldots,0),\mathbf$ {$b} _{i}+(rk)/q$을 계산한다.

$추측{\displaystyle }$ k$${\$displaystyle k}$이(가) 정확하다면 변환은 분포 $A{\displaystyle {}_{}}$ ${\displaystyle {s,}_{}}$ ${\displaystyle {\chi }_{}}$ ${\$을(를) 스스로 가져가고, 그렇지 $않으면{\displaystyle }$ q ${\displaysty q}$이(가 프라임)이므로$$ 균일한 분포로 가져간다.따라서 $q{\displaystyle }$ ${\displaystyle q}$은(는) $n{\displaystyle }$ ${\displaystyle n}$의 일부 다항식으로 제한되므로$,$ $k{\displaystyle }$ ${\displaystyle k}$에 대해 가능한 모든 값을 추측하고$$ 어느 것이 올바른지 확인하는 데 다항식 시간만 소요된다.

$s{\displaystyle {\mathbf{}}_{}}$ ${\$}를 얻은$$후 서로 좌표 $s{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ ${\$에 대해 유사한 절차를 따른다$.$ 즉, b ${\displaystyle {}_{}}$ ${\$ $\mathbf$${b}$ $_{$$i}}$ 샘플을$$ 동일한 방법으로 변환하고 ${\displaystyle {}_{}}$ ${\$ $sam$$}}}}}}}}}}}$$r{\displaystyle }$ ${\displaystyle \{\backslash }$$displaystyle r}$이(가)^[2] j ${\displaystyle {\text{th}}^{}}$ ${\$ 좌표$$ 안에 있는$$ i + (${\displaystyle 0,}$… $,$ …,${\displaystyle 0}$) ${\displaystyle \mathbf {a} _{i}$_${$$dotes$을 계산하여 ples.

Peikert는^[3] 이러한 감소는 작은 수정으로 구별되고 작은($n{\displaystyle }$ ${\displaystyle n$의 polynomial) 프라임의 산물인$$ 모든 $Q{\displaystyle }$ ${\displaystyle q}$에 적용된다는 것을 보여주었다.The main idea is if ${\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 ${\displaystyle 0\mod q_{\ell }}$, and then use the Chinese remainder theorem to$s{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ ${\$을(를) 복구하십시오$.$

평균 케이스 경도

Regev[2]임의의 q{\displaystyle q}과χ{\displaystyle \chi}.}, 그 쉽게 알 수 있는 LWE과 DLWE 문제의 임의 self-reducibility s로부터 샘플({\displaystyle\와 같이{(\mathbf{}_{나는},\mathbf{b}_{나는})\}},χ{\displaystyle A_{\mathbf{s},\chi}을 보여 주었다.t${\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 ${\displaystyle {\mathcal {S}} / \mathbb {Z} _{q}^{n} =1/\operatorname {poly} (n)}$, and for distributions ${\displaystyle A_{\ma$$thbf {s},\chi },$${\displaystyle s\mathcal{}}$ ′${\displaystyle }${$$S {\$displaystyle \mathbf$ {$s} '\왼쪽$ 화살표 ${\mathcal {S}},$DLWE는 쉬웠다.

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}}_{}^{}}$${\displaystyle \mathbb {Z} _{q}^{n}}$, calculate ${\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} +\mathbf {t} \in {\mathcal {S}}}$, and ${\displaysty$$le {\mathcal{A}}$이(가) 검체를 성공적으로 구별할 것이다$$.

따라서 그러한 $S{\displaystyle \mathcal{}}$ ${\$은(는) 존재할$$ 수 없으며, 이는 LWE와 DLWE가 (다항식 인자까지) 최악의 경우처럼 일반 사례에서처럼 단단하다는 것을 의미한다.

경도 결과

레게프의 결과

For a n-dimensional lattice ${\displaystyle L}$, let smoothing parameter ${\displaystyle \eta _{\varepsilon }(L)}$ denote the smallest ${\displaystyle s}$ such that ${\displaystyle \rho _{1/s}(L^{*}\setminus \{\mathbf {0} \})\leq \varepsilon }$ where ${\d$$isplaystyle L^{*}$는 $L{\displaystyle }$ ${\displaystyle L}$의 이중으로, $\alpha {\displaystyle {}_{}(x}$) =${\displaystyle {}^{}}$ - ${\displaystyle {\alpha (x}^{}}$ ${\displaystyle {/}^{}}$ ${\displaystyle {\alpha {}^{}}^{}}$) ${\displaystyle {{2\mathrm{}}^{}}^{}}${\$displaystyle \rho_{\alpha }}}(x)=e^{-\pi(x$/\$alpha )^{2}}}}$는 세트까지 확장된다$$.Let $D{\displaystyle {}_{}}$ ${\displaystyle L_{}}$, ${\displaystyle r_{}}$ ${\$은 $격자{\displaystyle }$ L ${\displaystyle L}$ 및 실제$$ r > ${\displaystyle$ r$>0}$에 대한$$$$ $폭{\displaystyle }$ $r{\displaystyle }$ ${\$$displaystyle$ l$}$의 L ${\$displaystystyle L$}$에 대한 이산 가우스 분포를 나타낸다$$각 $x{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle L}$ ${\displaystyle$ x$\in L}$의 확률은 ${\displaystyle {\rho }_{}}$ r${\displaystyle {}_{}}$( ${\displaystyle x}$) ${\displaystyle \rho _{r}(x)}$에 비례한다$.$

이산 가우스 샘플링 문제(DGS)는 다음과 같이 정의된다.An instance of ${\displaystyle DGS_{\phi }}$ is given by an ${\displaystyle n}$-dimensional lattice ${\displaystyle L}$ and a number ${\displaystyle r\geq \phi (L)}$. The goal is to output a sample from ${\displaystyle D_{L,r}}$. Regev shows that there is a reduction from ${\displaystyle G_{}}$${\displaystyle \operatorname {GapSVP} _{100{\sqrt {n}}\gamma (n)}}$ to ${\displaystyle DGS_{{\sqrt {n}}\gamma (n)/\lambda (L^{*})}}$ for any function ${\displaystyle \gamma (n)}$.

Regev then shows that there exists an efficient quantum algorithm for ${\displaystyle DGS_{{\sqrt {2n}}\eta _{\varepsilon }(L)/\alpha }}$ given access to an oracle for ${\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}$ for integer ${\displaystyle q}$ and ${\displaystyle \alpha \in (0}$${\displaystyle ,}$ ${\displaystyle 1}$) ${\displaystyle \alpha \in (0,1$)},$$ > ${\$ \ \$\alpha }{\sqrt{n$이것은 LWE에 대한 경도를 의미한다.이 어설션의 증거가 암호 시스템을 생성하기 위해 모든$$$q{\displaystyle }$ ${\displaystyle q}$에 대해 작동하지만, $q{\displaystyle }$ ${\displaystyle q}$은(는) $n{\displaystyle }$ ${\displaystyle$ n$}$의 다항식이어야 한다$$$.$

페이커트 결과

Peikert은 GapSVP ζ에서 LWEq,Ψα{\displaystyle \mathrm{LWE}_{q,\Psi_{\alpha}를 해결하는 것은 최악의 경우에 대비한 확률론적 다항 시간 감소,γ{\displaystyle \operatorname{GapSVP}_{\zeta ,\gamma}}문제는}}}폴리 ⁡(n){\displaystyle \operatorname{폴리에스테르 섬유}(n)를 사용하여 proves[3].samples for parameters ${\displaystyle \alpha \in (0,1)}$, ${\displaystyle \gamma (n)\geq n/(\alpha {\sqrt {\log n}})}$, ${\displaystyle \zeta (n)\geq \gamma (n)}$ and ${\displaystyle q\geq (\zeta /{\sqrt {n}})\omega {\sqrt {$$\log$ n$\}\}\}.$

암호화에 사용

LWE 문제는 여러 개의^[2][3][5][6] 암호 시스템을 구축하는 데 사용되는 다용도 문제의 역할을 한다.2005년, Regev[2]이 LWE의 결정 버전 열심히가 G는 pSVPγ{\displaystyle \mathrm{GapSVP}_{\gamma}}(γ을{\displaystyle \gamma}위와 같이)과 S1세 VPt{\displaystyle \mathrm{SIVP}_{t}}은 격자의 문제를 양자 경도 가정이 XO{\displaystyle t=O(n.(n/α)을 보였다/\$alpha )}$ ).$$2009년, Peikert는^[3] 관련 문제 G $a{\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {\mathrm{p}}_{}}$ ${\displaystyle {\mathrm{V}}_{}}$ ${\displaystyle {\mathrm{P}}_{}}$ ${\displaystyle {}_{}}$ ,${\displaystyle {\gamma }_{}}$ ${\${GapSVP}$_{\\zeta ,\gama }}}$의 고전적인 경도만을 가정하여 유사한 결과를 입증했다$.$페이커트 결과의 단점은 비표준 버전의 SIVP(SIVP와 비교했을 때) 문제 GapSVP에 기반을 둔다는 것이다.

공개 키 암호 시스템

레게프는^[2] LWE 문제의 경도를 바탕으로 한 공개키 암호체계를 제안했다.보안과 정확성의 증명은 물론 암호체계도 완전히 고전적이다.$시스템$은 T ${\$에 $,$ 확률$$ 분포 $\chi {\displaystyle }$ ${\displaystyle \chi }$이(가) 특징$.$ 정확성 및 보안 증명에 사용되는 파라미터의 설정은

• ${\displaystyle q\ge }$ ${\displaystyle 2}$ ${\displaystyle q\geq$ 2$\},$ 보통 n ${\displaystyle {2\mathrm{}}^{}}$ ${\$과 ${\displaystyle {2n}^{}}$ 2 ${\$ 사이의$$소수.
• ${\displaystyle m}$= (${\displaystyle 1}$+ ${\displaystyle \epsilon }$)${\displaystyle }$( ${\displaystyle \mathrm{n}}$+ 1${\displaystyle }$) ${\displaystyle \mathrm{로그}}$ ${\displaystyle q}$ ${\displaystyle m=(1+\varepsilon )(n+1)\log q}$ 임의$$ 상수 $\epsilon {\displaystyle }$ ${\displaystyle \varepsilon$}
• ${\displaystyle \chi =\Psi _{\alpha (n)}}$ for ${\displaystyle \alpha (n)\in o(1/{\sqrt {n}}\log n)}$, where ${\displaystyle \Psi _{\beta }}$ is a probability distribution obtained by sampling a normal variable with mean ${\displaystyle 0}$ and standard variation $\beta {\displaystyle \frac{}{}}$ ${\displaystyle \frac{\sqrt{2\mathrm{}}}{}}$ ${\$ 결과$$ modulo $1{\displaystyle \mathrm{}}$ ${\displaystyle 1$

암호 시스템은 다음으로 정의된다.

• 개인 키: 개인 키는 $s{\displaystyle \mathbf{}}$ $∈$ ${\displaystyle {}_{}^{}}$ q {\$displaystyle \mathbf {s} \in \mathb {Z} _{q}^{n}}}}}}}}$ 랜덤으로 균일하게 선택한$$ 것이다.
• 공개 키:${\displaystyle {\mathbf{}}_{}}$ ${\displaystyle m}$ 벡터$$ ${\displaystyle {\mathrm{}}_{}}$ $1{\displaystyle {\mathbf{}}_{}}$,${\displaystyle }$… ,${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ Z ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$를 균일하고$$ 독립적으로 선택하십시오.Choose error offsets ${\displaystyle e_{1},\ldots ,e_{m}\in \mathbb {T} }$ independently according to ${\displaystyle \chi }$. The public key consists of ${\displaystyle (\mathbf {a} _{i},b_{i}=\langle \mathbf {a} _{i},\mathbf$${s} \rangele /q+e_{i}_{i=1}^{m}}}$
• 암호화:${\displaystyle \mathrm{비트}}$ $x{\displaystyle \in \{0}$, ${\displaystyle 1}$ ${\displaystyle \}}$ ${\displaystyle x\in \{$$0,$$1\}$의 임의$$${\displaystyle }$서브셋 $S{\displaystyle }$ ${\displaystyle S}$를 선택한 다음$$ ${\displaystyle \mathrm{Enc}}$ ${\displaystyle }$ (${\displaystyle x}$ ${\displaystyle )}${\$displaysty \operatorname {Enc}(x)$을(x$)$로 정의하여 암호화한다$$.

${\displaystyle \left(\sum _{i\in S}\mathbf {a} _{i}}{\frac {x}{2}}+\sum _{i\in S}b_{i}\오른쪽)}}$

• 암호 해독:The decryption of ${\displaystyle (\mathbf {a} ,b)}$ is ${\displaystyle 0}$ if ${\displaystyle b-\langle \mathbf {a} ,\mathbf {s} \rangle /q}$ is closer to ${\displaystyle 0}$ than to ${\displaystyle {\frac {1}{2}}}$, and ${\displaystyle 1}$ otherwise.

정확성의 증명은 매개변수의 선택과 일부 확률 분석에서 나타난다.보안의 증명은 LWE의 의사결정 버전으로 축소된다: $0{\displaystyle \mathrm{}}$ ${\displaystyle 0}$과 1 ${\$$displaystyle 1}$의 암호화(상기 매개변수 포함$)$를 구별하기 위한 알고리즘을 사용하여 A s, for {\$displaystyle A_{s,\chi$ }와 ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle T}$를 통한 균일한 분포를 구별할 수 있다$$.${\displaystyle \mathb {Z} _{q}^{n}\times \mathb {T}}}$

CCA 보안 암호 시스템

이 구간은 확장이 필요하다.덧셈으로 도와줘도 된다.(2009년 12월)

페이커트는^[3] 어떤 선택된 암호문 공격에도 안전한 시스템을 제안했다.

키 교환

키 교환에 LWE와 링 LWE를 이용하자는 아이디어가 진타이딩에 의해 2011년 신시내티 대학에 제안되어 접수되었다.그 아이디어는 매트릭스 승수의 연관성에서 나왔고, 그 오류들은 보안을 제공하기 위해 사용된다.논문은^[7] 2012년 잠정 특허출원이 접수된 뒤 2012년 나왔다.

LWE 문제 해결의 경도를 바탕으로 프로토콜의 보안성이 입증된다.2014년 파이커트는 딩스(Ding's)와 같은 기본 아이디어에 따라 키 전송 방식을^[8] 제시했는데, 딩스(Ding) 건설에서 라운딩을 위한 추가 1비트 신호를 보내는 새로운 아이디어도 활용된다.구글의 사후 쿼럼 실험에 선택된 "새로운 희망" 구현은^[9] 오류 분포의 다양성과 함께 페이커트의 계획을 이용한다.^[10]

참고 항목

• 사후 수량 암호화
• 격자 기반 암호법
• 오류가 있는 링 학습 키 교환
• 짧은 정수 솔루션(SIS) 문제

참조