🤸 🔌 🏓 Cryptographie post-quantique. Présentation du protocole NewHope Key Generation ♊️ 🎏 🔒

Bonne journée!

Dans le monde moderne, il y a de plus en plus de déclarations sur la menace potentielle des ordinateurs quantiques en relation avec les protocoles de cryptographie utilisés. L'ordinateur quantique est déjà capable de résoudre les problèmes de logarithme discret et de factorisation d'un nombre, ce qui met en péril tous les protocoles basés sur eux.

Aujourd'hui, nous allons considérer le protocole NewHope, qui est basé sur une autre tâche difficile - le problème de l'apprentissage avec des erreurs dans un anneau (Ring-LWE).

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

1. SIS

SIS (Short integer solution problem) – .

, n q ( ):

$A = (\ overrightarrow {a_1}, \ overrightarrow {a_2}, \ dots, \ 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$ , Axe = 0 . , , .

$\ beta \ 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 ^ {\ theta (n)}$ , n - .

2. LWE ( Learning with errors)

n – ;

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

$\ chi$ , );

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

k, $\chi$ .

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

$a_1 \gets \mathbb{Z}^n_q ,\: b_1 \approx\: <s, a_1> \: mod \: q$ $a_2 \gets \mathbb{Z}^n_q ,\: b_2 \approx\: <s, a_2> \: mod \: q$ $\dots$

$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\right)\right)$

– .

, q. .

, , :

: $b^T\approx 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 {matrice} \ begin {matrice} \ vdots \\ a_i \\\ end {matrice} \\\ vdots \\\ end {matrice} \ right) \ widetilde {\ ast} \ left (\ begin {matrice} \ begin {matrice} \ vdots \\ s \\\ end {matrice} \\\ vdots \\\ end {matrice} \ right) + \ left (\ begin {matrice} \ begin {matrice} \ vdots \\ e_i \\\ end {matrice} \\\ vdots \\\ end {matrice} \ right) = \ left (\ begin {matrice} \ begin {matrice} \ vdots \\ b_i \\\ end {matrice} \\\ vdots \\\ end {matrice} \ right) \ in \ mathbb {Z} _q ^ n$

$\ widetilde {\ ast}$ ?

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

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

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

/? , 2 $O \ gauche (n \ logn \ droite)$ , $O \ gauche (n ^ 2 \ droite).$

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 , $\ gauche [0,1 \ droite)$ . ( ). $\ {\ gauche (0, \ 1 \ droite), \ gauche (1/2, \ 1/2 \ droite) \}$ . .