🦐 ☺️ 👨🏼‍🔬 Criptografia pós-quântica. Visão geral do protocolo de geração de chave NewHope 🤲 🏴 👩🏼‍🎨

Dia bom!

No mundo moderno, há cada vez mais declarações sobre a ameaça potencial dos computadores quânticos em relação aos protocolos de criptografia usados. O computador quântico já é capaz de resolver os problemas de logaritmo discreto e fatoração de um número, o que compromete todos os protocolos neles baseados.

Hoje vamos considerar o protocolo NewHope, que se baseia em outra tarefa difícil - o problema de aprendizagem com erros em um anel (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 \ aprox n ^ 2$ ;

$\ chi$ , );

$A \ in \ mathbb {Z} ^ {n \ vezes 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 \ certo, certo)$

– .

, 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{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) \}$ . .