🎻 🥃 🤜🏻 Kriptografi pasca-kuantum. Ikhtisar Protokol Pembuatan Kunci NewHope 👣 👩🏻‍⚖️ 👩🏼‍⚕️

Selamat siang!

Di dunia modern, semakin banyak pernyataan tentang potensi ancaman dari komputer kuantum dalam kaitannya dengan protokol kriptografi yang digunakan. Komputer kuantum sudah mampu memecahkan masalah logaritma diskrit dan faktorisasi angka, yang mengancam semua protokol yang berbasis padanya.

Hari ini kita akan mempertimbangkan protokol NewHope, yang didasarkan pada tugas sulit lainnya - masalah pembelajaran dengan kesalahan dalam sebuah 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 \ dalam \ mathbb {Z} ^ m$ , Kapak = 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 \ sekitar 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 \ mendapat \ mathbb {Z} ^ n_q, \: b_1 \ approx \: <s, a_1> \: mod \: q$ $a_2 \ mendapat \ mathbb {Z} ^ n_q, \: b_2 \ approx \: <s, a_2> \: mod \: q$ $\ titik$

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

k_1 .

, (LWE on lattices).

$L \ kiri (A \ kanan) = \ {z \ in \ mathbb {Z} ^ m: z ^ T \ equiv s ^ TA \ mod \ q \} = q \ kiri (L ^ \ bot \ kiri (A \ benar, benar)$

– .

, 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 ${derajat (R} _q) <n$ c q.

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

/? , 2 $O \ kiri (n \ logn \ kanan)$ , $O \ kiri (n ^ 2 \ kanan).$

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