🎰 👨🏿‍🔧 🎚️ ポスト量子暗号。NewHopeキー生成プロトコルの概要 🏮 🐒 🛀🏽

良い一日！

現代の世界では、使用されている暗号化プロトコルに関連して、量子コンピューターからの潜在的な脅威についての声明がますます増えています。量子コンピューターは、離散対数と数値の因数分解の問題をすでに解決することができ、それらに基づくすべてのプロトコルを危険にさらします。

今日は、もう1つの難しいタスクであるリング内のエラーによる学習の問題（Ring-LWE）に基づくNewHopeプロトコルについて検討します。

NewHope – , , . , SIS, LWE Ring-LWE:

1. SIS

SIS (Short integer solution problem) – .

, n q ( ):

$A =（\ overrightarrow {a_1}、\ overrightarrow {a_2}、\ dot、\ overrightarrow {a_m}）\ in \ mathbb {Z} ^ {n \ times m} _q$

$L ^ {\ perp}$ A:

$L ^ {\ perp}（A）= \ {z \ in \ mathbb {Z} ^ m：Az = 0 \}$

( ) , .

, $x \ in \ mathbb {Z} ^ m$ , Ax = 0 . , , .

$\ベータ版\ ll q$ , z, $|| z || \ leq \ beta \ ll q$ . z ( q). , , . , .

? , ( ).

$t \ ll T$ - . z.

$L_u ^ {\ perp}（A）= \ {z：Az = u \} = t + L ^ {\ perp}（A）$

, z A .

, $2 ^ {\シータ（n）}$ , n - .

2. LWE ( Learning with errors)

n – ;

q – , . n, $q \約n ^ 2$ ;

$\カイ$ , );

$A \ in \ mathbb {Z} ^ {n \ times m} _q$ $a_i \ in \ mathbb {Z} ^ n_q$ ;

k, $\カイ$ .

, $s \ in \ mathbb {Z} ^ n_q$ , s a_i . ( q):

$a_1 \ get \ mathbb {Z} ^ n_q、\：b_1 \約\：<s、a_1> \：mod \：q$ $a_2 \は\ mathbb {Z} ^ n_q、\：b_2 \約\：<s、a_2> \：mod \：qを取得します$ $\ドット$

$b_1 = <s、a_1> + k_1 \ in \ mathbb {Z} _q$

k_1 .

, (LWE on lattices).

$L \ left（A \ right）= \ {z \ in \ mathbb {Z} ^ m：z ^ T \ equiv s ^ TA \ mod \ q \} = q \ left（L ^ \ bot \ left（A \そうそう）$

– .

, q. .

, , :

: $b ^ T \約v ^ T = s ^ TA \ in L（A）\$ .

3.

LWE, - SIS:

Public key encryption (LWE):

, . – .

, $e ^ \ prime-ex \ ll \ \ frac {q} {2}。$

0, 0, $\ frac {q} {2}$ 1.

? （A、u）（b、b '） . , , 4 , .

One-way function (SIS):

- -:

https://www.di.ens.fr/chloe.hebant/presentation/SISproblem.pdf

, . . (IV).

, , H(m) .

- (One-way function):

, :

$n \in \mathbb{N}$ q = poly(n) m = m(n) .

H_n - $\{f_A\}_{A\in Z^{n\times m}}$ $f_A:\{0,1\}^m\rightarrow Z_n^m$

$e\in{\{0,1\}}^n$ :

$f_A\left(e\right)=A \times e\>\ mod\>\ q$

SIS.

? , SIS .

4.

. $640 \times 8$ 15 :

: https://summerschool-croatia.cs.ru.nl/2018/

2) / O(n^2) , .

5. Ring-LWE

? , LWE . , n ?

$\left(\begin{matrix}\begin{matrix}\vdots\\a_i\\\end{matrix}\\\vdots\\\end{matrix}\right)\widetilde{\ast}\left(\begin{matrix}\begin{matrix}\vdots\\s\\\end{matrix}\\\vdots\\\end{matrix}\right)+\left(\begin{matrix}\begin{matrix}\vdots\\e_i\\\end{matrix}\\\vdots\\\end{matrix}\right)=\left(\begin{matrix}\begin{matrix}\vdots\\b_i\\\end{matrix}\\\vdots\\\end{matrix}\right)\in \mathbb{Z}_q^n$

$\widetilde{\ast}$ ?

– R_q=R/qR , $R = \mathbb{Z}_q\left[X\right]/\left(X^n+1\right)$ , n – .

R_q ${deg(R}_q)<n$ c q.

? . , , : $x\ \rightarrow\ -x\ mod\ q$ . .

/? , 2 $O\left(n\ logn\right)$ , $O\left(n^2\right).$

LWE , a_i、s、k , .

6. NewHope

, NewHope , Bos, Castello, Naehrig Stebila. TLS Ring-LWE.

, NewHope.

, .

, .

n = 1024, q = 12289 ( , $q \ equiv1 \ mod \ 2n$ ). NTT ( ), n – , q – , .
a. : seed – 256 , SHAKE-128 ( SHA3). , 1024 a. : , TLS ( 2 ), NewHope , a. , backdoor , “” .
– , . - , ( ). seed /dev/urandom 16- . s e.
( b, seed).
a, s’, e’, e”, u.
v, , . . , , , . , – , 0 $\ frac {q} {2}$ . , .
. : . q , $\左[0,1 \右）$ . ( ). $\ {\左（0、\ 1 \右）、\左（1/2、\ 1/2 \右）\}$ . .