Mă întreb dacă se poate aplica algoritmul Grover pe un mecanism de încapsulare a cheii pentru a sparge cheia partajată.
Iată cum funcționează algoritmul lui Grover (simplificat): luați o funcție „fitness” (care presupune o ghicire a valorii pe care o căutați și evaluează la un „1” dacă presupunerea este corectă și „0” dacă nu este - pentru AES, funcția de fitness ar putea fi „utilizați ghicitul ca o cheie AES și criptați blocul de text simplu cunoscut și verificați dacă rezultatul este blocul de text cifrat cunoscut).
Apoi, luați această funcție de fitness (și alte operațiuni cuantice) și o repeți de un număr mare de ori - dacă o repeți de numărul corect de ori, atunci când măsurați rezultatul, este cu mare probabilitate o valoare pe care fitness-ul funcția este evaluată la 1.
Acum, dacă ar fi să luăm în considerare atacarea lui Frodo, există două moduri de a-l ataca. Se poate încerca să recupereze secretul partajat direct din partajările cheii publice; în acest caz, avem la dispoziție pentru funcția de fitness cheia publică partajată și presupunerea noastră la secretul partajat. Cu toate acestea, nu avem o modalitate eficientă de a verifica dacă această presupunere este corectă (pe baza partajelor de cheie publică) și, prin urmare, nu știm cum să construim această funcție de fitness (și astfel Grover nu pare să se aplice).
Pe de altă parte, putem încerca să recuperăm sămânța secretă pe care Frodo a folosit-o pentru a obține cheia publică [1] (sau, alternativ, în cadrul procesului de încapsulare Frodo). Pentru Frodo-640 (nivel 1 NIST), această sămânță secretă este de 128 de biți; întrucât s-ar putea defini o mapare între această valoare de 128 de biți (și datele publice, adică semințele publice) și cheia publică, am putea folosi aceasta pentru a genera funcția de fitness.
Acum, acest atac nu este inerent criptografiei postcuantice; funcționează nu atacând direct secretul partajat de 128 de biți, ci în loc de modul în care acest set de parametri ai Frodo își generează partajările de cheie, folosind o valoare aleatorie de 128 de biți ca „seed secret”. Ceea ce face Frodo este să ia acea sămânță secretă de 128 de biți și să o extindă folosind SHAKE pentru a genera vectori de partajare și de eroare mult mai lungi; designerii Frodo ar fi putut folosi o sămânță secretă mai lungă și să o extindă la SHAKE - acest lucru l-ar face pe Grover mult mai dificil (deoarece sămânța secretă de recuperat este mult mai lungă, iar încercarea de a recupera starea internă SHAKE sau secvența de ieșiri SHAKE ar fi de asemenea, durează prea mult). Designerii lui Frodo nu au făcut acest lucru, probabil pentru că de fapt nu ar îmbunătăți securitatea.
Pe de altă parte, în general facem ceva cu cheia partajată; putem introduce asta într-un KDF (poate împreună cu unele date publice, cum ar fi nonces), și apoi folosim acel rezultat ca o cheie AES. Putem construi o funcție de fitness bazată pe asta și, astfel, Grover s-ar aplica acelui sistem - cel mai probabil, această construcție KDF/AES ar fi mai simplu de implementat într-un computer cuantic decât procesul de cheie publică Frodo (sau de încapsulare); prin urmare, este probabil să fie mai ușor să ataci sistemul de acolo (fie doar printr-un factor constant).
Pe de o parte, este rezonabil să ne întrebăm dacă Grover este într-adevăr o amenințare împotriva unui secret pe 128 de biți - toate aceste evaluări ale funcțiilor de fitness sunt efectuate în serie și ar fi impractic să evaluăm orice funcție. $2^{64}$ ori la rând. Și, în timp ce ați putea încerca să ocoliți acest lucru, rulând Grover pe un număr mare de calculatoare cuantice, împărțind spațiul secret, pierdem o parte din avantajul lui Grover dacă facem asta și astfel ajungem să folosim un lot a calculatoarelor cuantice.
[1]: Rețineți că Frodo are două semințe; unul public care definește rețeaua care trebuie utilizată și unul care este secret și care este utilizat pentru a genera matricele de eșantion și de eroare; deoarece semințele publice se află în cheia publică, atacatorul nu trebuie să ghicească asta; tot ce trebuie să facă este să recupereze sămânța secretă.
