🤴🏽 📨 🔖 Postquantenkryptographie. NewHope Key Generation Protocol

Schönen Tag!

In der modernen Welt gibt es immer mehr Aussagen über die potenzielle Bedrohung durch Quantencomputer in Bezug auf die verwendeten Kryptographieprotokolle. Der Quantencomputer ist bereits in der Lage, die Probleme des diskreten Logarithmus und der Faktorisierung einer Zahl zu lösen, wodurch alle darauf basierenden Protokolle gefährdet werden.

Heute werden wir das NewHope-Protokoll betrachten, das auf einer anderen schwierigen Aufgabe basiert - dem Problem des Lernens mit Fehlern in einem Ring (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 \ ca. 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 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 {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) \}$ . .