Ce înseamnă lucrarea „An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Aproximation Factor”?

În Un algoritm cuantic eficient pentru problemele rețelei care realizează un factor de aproximare subexponențială, autorul susține că oferă un algoritm cuantic în timp polinomial pentru rezolvarea problemei de decodificare a distanței limitate cu un factor de aproximare subexponențial pe o clasă de rețele întregi. Ce înseamnă acest rezultat? Va implica insecuritatea criptografiei latice? Este la fel de important ca algoritm cuantic pentru factorizare de Peter Shor?

Nu există încă o lucrare publică disponibilă, așa că acest răspuns este preliminar și se bazează pe ceea ce a fost prezentat în discuție și discuția ulterioară. Nu se poate ajunge la o înțelegere completă până când nu există o lucrare pentru a verifica, evalua și compara cu munca anterioară și rezultatele cunoscute. Cu toate acestea, o bună înțelegere a situației pare să apară deja.

Tl;dr este: problema specială pe care o abordează autorii clasic ușor de rezolvat folosind algoritmi standard de rețea (nu este nevoie de cuantum), așa cum se arată în această notă. În plus, noul pas cuantic de bază poate fi implementat în mod clasic (și mult mai simplu și mai eficient). Așadar, lucrarea nu arată niciun avantaj cuantic față de ceea ce știam deja să facem clasic și nici nimic nou despre ceea ce putem face în mod clasic. Urmează detalii.

Clauza „pe o clasă de rețele întregi” este un calificativ foarte important. Problema BDD pe care o abordează autorii este una în care rețeaua este â$q$-aryâ și generate de un singur $n$-mod dimensional-$q$ vector (sau un număr mic dintre ele), modulul $q \gg 2^{\sqrt{n}}$, iar vectorul țintă este în a $\ll 2^{-\sqrt{n}}$ factorul distanței minime a rețelei. Această setare este departe de orice a fost folosit vreodată în criptografia cu zăbrele (din câte știu), astfel încât rezultatul nu ar avea niciun efect direct asupra sistemelor zăbrele propuse. Desigur, întrebarea mai largă este dacă tehnicile ar putea duce la rezultate mai puternice care afectează criptografiile latice.

Pe baza descrierii oferite în discuție, câțiva participanți experți cred că este foarte probabil ca problema specială a rețelei pe care o abordează autorii să fie deja ușor de rezolvat folosind clasic tehnici (nu este nevoie de cuantum). ACTUALIZAȚI: acest lucru s-a dovedit a fi cazul și este fundamentat în această notă. Cu alte cuvinte, forma particulară a problemei BDD o face ușor de rezolvat în moduri cunoscute și nesurprinzătoare. Algoritmul este doar secvența standard de reducere a bazei LLL, urmată de decodarea Babai în cel mai apropiat plan, dar arătarea că aceasta funcționează de fapt se bazează pe unele proprietăți mai profunde (dar cunoscute anterior) ale LLL decât cele care sunt de obicei invocate.

Cum rămâne cu întrebarea mai largă: ar putea tehnicile principale să conducă la rezultate mai puternice pe care nu le putem obține în prezent în mod clasic? Se pare că ceea ce realizează pasul cuantic de bază, transformarea „de la cel mai rău caz la caz mediu”, se poate face. clasic (și mai simplu și mai eficient) folosind o tehnică binecunoscută de randomizare, ceea ce se numește „auto-reducere LWE” sau „($q$-ary) reducerea BDD la LWE.â Vezi Secțiunea 5 și Teorema 5.3 din această hârtie și lucrările anterioare citate aici pentru detalii.

Mai precis, $n$-dimensională $q$-ary BDD pentru distanța relativă $\alpha$ (problema luată în considerare de autori) se reduce clasic la LWE cu rata de eroare $\alpha \cdot O(\sqrt{n})$. Deși această reducere pare inutilă pentru a rezolva problema BDD inițială în cauză, ea arată că noul pas cuantic de bază poate fi înlocuit cu ceva clasic care funcționează cel puțin la fel de bine (și probabil chiar mai bine în ceea ce privește parametrii). Acest lucru indică faptul că tehnica cuantică principală probabil nu deține nicio putere nouă sau surprinzătoare în acest context.

Am creat un site web pentru a aduna ceea ce se știe despre algoritmi pentru problemele de rețea în NP intersect CoNP:

https://latticealgorithms.xyz

Lucrarea noastră a apărut:

https://arxiv.org/abs/2201.13450

Pentru înregistrare, iată cronologia pe care am urmărit-o:

Până pe 17.08.21 am parcurs destul de bine literatura clasică. Un algoritm clasic ar fi fost, de asemenea, bine, astfel încât să-l putem alimenta înapoi în algoritmi cuantici. Dar, deoarece cazul de bază este un tip de cel mai rău caz al problemei numerelor ascunse bine studiate, părea rezonabil că nu se știe nimic.

8/17/21-9/21/21: Am întrebat o secvență de 5 experți ce se știe despre problemă. Într-un caz am indicat cea mai bună abordare clasică pe care am putut-o găsi. Nu am primit niciun răspuns cu informații noi.

21/09/21: S-a luat decizia de a merge cu cazul de bază special cu un vector în discuție pentru că (1) va ajuta oamenii să o rezolve și (2) este o discuție colocvială într-un seminar cuantic și, prin urmare, are nevoie pentru a fi accesibile unui public larg. O discuție doar cu zăbrele sau numai cuantică este deja o provocare, iar să le combinați pe amândouă, ei bine, încercați! 21.09.21: Discuție animată despre posibilități în timpul panelului, dar fără algoritmi.

22/09/21: Suntem contactați cu un nou algoritm clasic pentru cazul special și, după ce am clarificat ce pot face algoritmii noștri, o revizuire care descrie cum să obținem un caz mai general prin analizarea LLL.

31/01/22: Nu a fost primit încă un răspuns clasic pentru legătura noastră Schnorr.

Sean

S-ar putea da un răspuns mult mai lung la această întrebare (și m-ar interesa destul de mult să văd pe cineva ca perspectiva lui Chris), dar următoarele două puncte probabil sunt suficiente pentru un nespecialist.

Factori de aproximare: Principalul mod în care acest atac ar trebui să fie văzut ca amenințător (potențial) pentru criptografia bazată pe rețea este prin posibilitatea de îmbunătățiri viitoare. Factorul de aproximare vizat de acest lucru (care cred că este $2^{n^{1/2}}$) este suficient de mare încât chiar dacă LWE ar fi clasic slab în acest interval, se mai pot construi lucruri precum:

• PKE
• Semnături digitale
• FHE

De exemplu. cea mai mare parte a ceea ce ți-ar putea păsa ar mai exista. Așadar, atacul actual în sine nu afectează cu adevărat corpul principal al criptografiei „practice” bazate pe rețea, deși sunt posibile, desigur, îmbunătățiri viitoare ale atacului.

Posibilitatea decuantizării: Atacul are două părți:

1. O etapă (cuantică) de reducere a dimensionalității (de la $n\la \sqrt{n}$)
2. Utilizați tehnici clasice standard pentru a rezolva problema $\sqrt{n}$-instanță de dimensiune.

O serie de oameni au sugerat posibilitatea decuantizării primului pas, prin lucruri precum luarea de combinații liniare aleatoare (să zicem cu coeficienți gaussieni) ale vectorilor de bază. Dacă această reducere a dimensiunii funcționează, se obține BDD cu factor de aproximare $2^{n^{1/2}}$ în timp polinomial (cred).

În timp ce acest lucru ar face algoritmul în sine mai puternica, ar face, de asemenea, mai puțin îngrijorătoare într-un anumit sens. Acest lucru se datorează faptului că avem (în mod clasic) o idee destul de decentă despre cât de grele sunt problemele cu zăbrele. Prin aceasta, mă gândesc în special la lucruri precum:

1. Diferitele rezultate de duritate „cu granulație fină” care există (să zicem sub ipoteza timpului exponențial sau variante ale acesteia),
2. recent zăbrele cernerea limitelor inferioare, și
3. duritatea rezultă în prezența preprocesării (de exemplu, rezultă duritatea CVPP).

Desigur, acestea nu exclud toate atacurile posibile, dar ele ar trebui menționate ca un corp tot mai mare de dovezi formale pentru duritatea clasică a problemelor rețelei. Aceasta înseamnă că principalul lucru îngrijorător despre discuția legată este existența unui accelerare cuantică non-trivială --- dacă aceasta este decuantizată, ne întoarcem în contextul calculului clasic, unde înțelegerea noastră a problemelor de duritate a rețelei este mai bună.