👩🏿‍🤝‍👨🏾 🕴🏾 😿 تشفير ما بعد الكم. نظرة عامة على بروتوكول NewHope Key Generation Protocol 👨🏽‍🏭 📡 🛌🏾

يوم جيد!

في العالم الحديث ، هناك المزيد والمزيد من البيانات حول التهديد المحتمل من أجهزة الكمبيوتر الكمومية فيما يتعلق ببروتوكولات التشفير المستخدمة. الكمبيوتر الكمومي قادر بالفعل على حل مشاكل اللوغاريتم المنفصل وعوامل الرقم ، مما يعرض للخطر جميع البروتوكولات القائمة عليها.

سننظر اليوم في بروتوكول NewHope ، الذي يعتمد على مهمة صعبة أخرى - مشكلة التعلم مع وجود أخطاء في الحلقة (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$ , الفأس = 0 . , , .

$\ بيتا \ ليرة لبنانية ف$ , z, $|| z || \ leq \ بيتا \ ll q$ . z ( q). , , . , .

? , ( ).

$ر \ ليرة لبنانية ت$ - . z.

$L_u ^ {\ perp} (A) = \ {z: Az = u \} = t + L ^ {\ perp} (A)$

, z A .

, $2 ^ {\ ثيتا (n)}$ , n - .

2. LWE ( Learning with errors)

n – ;

q – , . n, $ف \ تقريبا n ^ 2$ ;

$\ تشي$ , );

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

k, $\ تشي$ .

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

$a_1 \ يحصل \ mathbb {Z} ^ n_q، \: b_1 \ تقريبًا \: <s، a_1> \: mod \: q$ $a_2 \ يحصل \ mathbb {Z} ^ n_q، \: b_2 \ تقريبًا \: <s، a_2> \: mod \: q$ $\ نقطة$

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

ك_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 \ صحيح صحيح)$

– .

, q. .

, , :

: $ب ^ T \ تقريبا v ^ T = s ^ TA في L (A) \$ الخامس .

3.

LWE, - SIS:

Public key encryption (LWE):

, . – .

, $e ^ \ prime-ex \ ll \ frac {q} {2}.$

0, 0, $\ فارك {q} {2}$ 1.

? (أ ، ش) (ب ، ب ') . , , 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 $\ فارك {q} {2}$ . , .
. : . q , $\ يسار [0،1 \ يمين)$ . ( ). $\ {\ left (0، \ 1 \ right)، \ left (1/2، \ 1/2 \ right) \}$ . .