înregistrare Logare
Puncte:2
Sam Jaques avatar Crypto

Cum poate BDD să rezolve LWE dacă matricea A este de rang complet?

drapel us
Sam Jaques

Încerc să îmi dau seama exact cum rezolvarea diferitelor probleme generice de rețea poate rezolva LWE și, în special, BDD. Tot ce am găsit spune asta, deoarece un eșantion LWE este $(A,b=As+e\mod q$), apoi zăbrele $L_q(A)=\{v : \exists x:Ax=v\mod q\}$ conţine $Ca$, asa de $b$ este la distanță $\Vert e\Vert$ a acelui grilaj. Prin urmare, dacă un rezolvator BDD poate rezolva distanțe de până la $\Vert e\Vert $, la intrare $b$ ar trebui să se întoarcă $Ca$.

Cu toate acestea, dacă $A$ este o $n\ori n$ matrice (cum ar fi în Frodo), apoi cu mare probabilitate $A$ are rang complet peste $\mathbb{F}_q$. Astfel înseamnă toți vectorii în $\mathbb{F}_q^n$ sunt în intervalul de $A$, asa de $L_q(A)=\mathbb{Z}^n$. Apoi, de când $e$ este, de asemenea, un vector întreg, $b\în L_q(A)$, deci BDD este inutil: la intrarea de $b$, s-ar întoarce $b$.

Poate BDD să rezolve LWE aici? Este un rezolvator SVP aproximativ mai natural?

52
0 + 0
Chris Peikert avatar
drapel in
Chris Peikert
Pentru Frodo și altele asemenea, vectorul coeficient $x$ al punctului reticulat este âscurtâ, deci $Ax$ nu acoperă tot $\mathbb{Z}_q^n$. Vedeți modelarea transmisiei FrodoKEM a acestei „forme normale” LWE ca problemă BDD pentru o configurație adecvată a unei rețele și a vectorului BDD din apropiere.
0
Răspunde
Sam Jaques avatar
drapel us
Sam Jaques
Trimiterea FrodoKEM explică modul în care BDDwDGS se reduce la LWE, apoi dă atacuri bazate pe uSVP, dar nu pot găsi un atac bazat pe BDD direct (adică, o reducere de la LWE la BDD). Am găsit o reducere de la uSVP la BDD, deci se poate face LWE=>uSVP=>BDD, dar asta e tot?
0
Răspunde
Chris Peikert avatar
drapel in
Chris Peikert
Secțiunea 5.2.2 are reducerea LWE
0
Răspunde
Sam Jaques avatar
drapel us
Sam Jaques
Am văzut asta și mă uitam prin detalii (ultimul meu comentariu probabil are => înapoi). Deci uSVP poate rezolva destul de direct forma normală LWE, dar BDD trebuie să „trece prin” uSVP mai întâi pentru a rezolva LWE?
0
Răspunde
Chris Peikert avatar
drapel in
Chris Peikert
Nu sunt sigur ce vrei să spui prin âBDD are nevoie deâ¦â LWE este doar o problemă BDD de caz mediu. Rețineți că Secțiunea 5.2.3 acoperă un atac LWE/BDD care nu trece prin uSVP.
0
Răspunde
Sam Jaques avatar
drapel us
Sam Jaques
Întrebarea mea inițială este cum să văd LWE ca o problemă BDD de caz mediu, având în vedere că rețeaua naturală de utilizat ($L_q(A)$) conține eșantionul LWE $b$. Sec. 5.2.3 pare să folosească vectori de rețea scurti direct -- $(v,w)\in \hat{\Lambda}$. Întrebarea mea specifică este: Dacă am un solutor BDD și un eșantion LWE de formă normală $(A,b=As+e)$, ce rețea $L$ și ce vector apropiat $t$ dau solutorului BDD?
0
Răspunde
Chris Peikert avatar
drapel in
Chris Peikert
Bine. Rețeaua relevantă este â$q$ - rețeaua de verificare a paritățiiâ a vectorilor întregi $z$ astfel încât $[A \mid I]z = 0 \pmod{q}$. Ținta $b = As + e = [A \mid I] (s,e)$ este un âsindromâ care specifică setul de rețea obținut prin deplasarea ușoară a rețelei, de vectorul scurt $(s,e )$.(Aceasta este o concepție echivalentă a problemei BDD: având în vedere o rețea și un coset obținut printr-o deplasare mică, găsiți acea schimbare.) Un exercițiu bun este să scrieți o bază explicită pentru această rețea și să convertiți $b$ într-un vector țintă BDD explicit în spațiul ambiental al rețelei.
1
Răspunde
Sam Jaques avatar
drapel us
Sam Jaques
O, excelent! Exact despre asta întrebam, mulțumesc.
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

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.