Care este problema rețelei dure? Un fir de ață 🧵

Criptografia bazată pe rețea se bazează pe o provocare centrală: găsirea unei soluții vectoriale scurte s pentru un sistem de ecuații liniare modulo un întreg q (de obicei o putere primă sau primă). Aceasta se numește problema SIS (Short Integer Solution), simplă ca formă, dar considerată puternic împotriva atacurilor cuantice/clasice.

Există două versiuni principale: forma neomogenă folosită ca funcție unidirecțională f_A(s) = A * s mod q în schemele de angajament, unde rezolvăm A * s = t (mod q) dat A și ținta t...

... și problema SIS omogenă, care cere să găsești un scurt s astfel încât A * s = 0 (mod q) pentru o matrice aleatoare A.

Schema de angajamente este garantată a fi obligatorie prin duritatea SIS. Dacă A * s = t = A * s', atunci A * (s - s') = 0, ceea ce înseamnă că găsirea unui alt s' rezolvă problema SIS omogenă dificilă.

Scurtitudinea lui s (norma mică) este esențială. Fără limitarea lui s, soluțiile sunt triviale folosind algebra liniară clasică. Această restricție de normă stă la baza naturii greu de rezolvat a SIS, chiar și împotriva calculatoarelor cuantice.

Rezultatul lui Ajtai din 1996 a legat dificultatea problemei SIS de rezolvarea problemelor de rețea în cel mai rău caz, formând o bază pentru presupunerile criptografiei post-cuantice.

Problema SIS permite compresia de la un vector secret mare s (dimensiune M) la un angajament mai scurt t. Matricea A are dimensiuni N x M, unde N este de obicei legat de parametrul de securitate, ceea ce o face atractivă pentru demonstrațiile de cunoaștere zero care necesită concizie.

Luate împreună, SIS este ușor de enunțat, dar extrem de greu de rezolvat, jucând un rol fundamental în angajamente, demonstrații zero-knowledge și securitate post-cuantică mai largă.