Puncte:3

Corectitudinea decriptării criptării bazate pe RLWE

drapel br
zbo

Sunt blocat în dovada corectitudinii decriptării în Cryptosystem bazat pe RLWE. Pentru a spune unde sunt , permiteți-mi să arăt mai întâi schema completă. Imaginea este din capitolul 3.2 din această hârtie. introduceți descrierea imaginii aici

Și dovada corectitudinii decriptării a schemei urmează introduceți descrierea imaginii aici

În această dovadă, pot obține a doua ultima ecuație în procedura de decriptare, i.e. $$\mathbf{m} + (t/q)(\mathbf{v}-\epsilon \cdot \mathbf{m}) + t\cdot \mathbf{r} $$

Dar pentru ultima ecuație nu știu de ce. $$(t/q)||\mathbf{v}-\epsilon \cdot \mathbf{m}|| \lt 1/2 $$

Am niste indicii. Noi deja avem $||\mathbf{v}|| \le 2\cdot \delta_R \cdot B^2 + B$, apoi pentru $2\cdot \delta_R \cdot B^2 + B \lt \Delta / 2$, avem $||\mathbf{v}|| \lt \frac{q}{2t}$ de cand $\Delta = \lfloor q/t \rfloor \le q/t$. Prin urmare $(t/q)||\mathbf{v}|| \lt \frac{1}{2}$. Acest lucru este foarte asemănător cu ceea ce ne dorim, adică $(t/q)||\mathbf{v}-\epsilon \cdot \mathbf{m}|| \lt 1/2 $.
Presupun că există o relație între $||\mathbf{v}||$ și $||\mathbf{v}-\epsilon \cdot \mathbf{m}||$ , dar nu știu cum să construiesc relația dintre ei. Dovada din lucrare are o scurtă explicație „Din moment ce $\mathbf{m} \in R_t$„, dar nu pot să înțeleg. Oricine oferă un indiciu ar fi de ajutor.

În plus, norma din această lucrare în norma infinitului.

Editare20220601:
Adăugați câteva explicații mai sus.

  1. $\delta_R $ se numește factor de expansiune al unui inel $R$. Și $\delta_R = \max{\frac{||a\cdot b||}{||a||\cdot ||b||}},a\in R, b\in R$.
  2. În cele de mai sus, avem $\mathbf{v} = \mathbf{e}\cdot \mathbf{u}+ \mathbf{e}_1 +\mathbf{e}_2\cdot \mathbf{s}$, de cand $\mathbf{e},\mathbf{u},\mathbf{e}_2,\mathbf{s} \in \chi$,deci norma lor infinită toate s-au legat $B$, atunci $||\mathbf{e}\cdot \mathbf{u}||= \frac{||\mathbf{e}\cdot \mathbf{u}||}{||\mathbf{e}||\cdot ||\mathbf{u}||}\cdot ||\mathbf{e}||\cdot ||\mathbf{u}|| \le \delta_R \cdot B^2$, la fel, $||\mathbf{e}_2 \cdot \mathbf{s}|| \le \delta_R \cdot B^2$, deci avem $||\mathbf{v}|| \le 2\cdot \delta_R \cdot B^2 + B$
kelalaka avatar
drapel in
[Postarea încrucișată nu este o etică bună în SO](https://meta.stackexchange.com/questions/64068/is-cross-posting-a-question-on-multiple-stack-exchange-sites-permitted-if -the-qu). Ați putea șterge copia matematică?
zbo avatar
drapel br
zbo
@kelalaka Îmi pare rău, nu mi-am dat seama. Îl voi șterge chiar acum.
Mark avatar
drapel ng
Există vreo relație presupusă între $t$ și $q$? Este simplu să obțineți limita $(t/q)\lVert \epsilon\vec m\rVert_\infty \leq t^2/2q$. Cu o ipoteză suficient de puternică pe $t, q$, aceasta este suficientă pentru a obține aproape limita (veți pierde un factor constant care ar trebui să poată fi ignorat în această setare).
zbo avatar
drapel br
zbo
Nu se vorbește despre relația dintre $t$ și $q$ în preliminariile lucrării. Dar într-o bibliotecă homomorfă precum SEAL, de obicei avem parametri precum $t$ este $4096$ și $q$ este un număr de biți de dimensiune $109$. $(t/q)||\mathbf{v} -\epsilon \cdot \mathbf{m}|| \le (t/q)(||\mathbf{v}||+\epsilon||\mathbf{m}|| ) \le (t/q)(\Delta/2)+ (t/q)( \epsilon \cdot (t/2)) \le (t/q)\cdot (q/2t)+(t/q)(\epsilon \cdot (t/2) ) = 1/2 + \frac{\ epsilon \cdot t^2}{2q}$
zbo avatar
drapel br
zbo
@Mark În setarea parametrilor , $\frac{\epsilon \cdot t^2}{2q}$ este mic, poate neglijabil, dar totuși nu pot să fie strict mai mic de $\frac{1}{2}$
Mark avatar
drapel ng
Nu am timp să mă uit prin hârtie acum, dar poate că merită menționat că dacă $t\mid q$, este simplu să arătăm că $\epsilon =0$ și toată această problemă dispare. Aceasta este cea mai comună setare (atât practic, cât și teoretic), deși nu vă rezolvă pe deplin întrebarea.
zbo avatar
drapel br
zbo
@Mark Mulțumesc, am rămas blocat în această dovadă și nu am continuat să citesc următoarea lucrare, se pare că parametrii fac lucrurile atât de mult diferit.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.