🤵🏾 🧕🏽 🖱️ Criptografía poscuántica. Descripción general del protocolo de generación de claves NewHope 🌟 🔜 🖖🏾

¡Buen día!

En el mundo moderno, hay cada vez más declaraciones sobre la amenaza potencial de las computadoras cuánticas en relación con los protocolos de criptografía utilizados. La computadora cuántica ya es capaz de resolver los problemas de logaritmo discreto y factorización de un número, lo que amenaza todos los protocolos basados en ellos.

Hoy consideraremos el protocolo NewHope, que se basa en otra tarea difícil: el problema del aprendizaje con errores en un anillo (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$ , Ax = 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 \ approx n ^ 2$ ;

$\ chi$ , );

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

k, $\ chi$ .

, $s \ in \ mathbb {Z} ^ n_q$ , s . ( 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$ $\ puntos$

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

– .

, q. .

, , :

: $b ^ T \ approx v ^ T = s ^ TA \ en 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 , $\ left [0,1 \ right)$ . ( ). $\ {\ left (0, \ 1 \ right), \ left (1/2, \ 1/2 \ right) \}$ . .