Qual è il Problema della Reticolazione Dura? Un thread 🧵

La crittografia basata su reticoli si basa su una sfida centrale: trovare una soluzione a vettore corto s per un sistema di equazioni lineari modulo un intero q (di solito un primo o una potenza di primo). Questo è chiamato problema SIS (Short Integer Solution), semplice nella forma ma ritenuto difficile contro attacchi quantistici/classici.

Ci sono due versioni principali: la forma inomogenea utilizzata come funzione unidirezionale f_A(s) = A * s mod q negli schemi di impegno, dove risolviamo A * s = t (mod q) dato A e il target t...

...e il problema omogeneo SIS, che chiede di trovare un breve s tale che A * s = 0 (mod q) per una matrice A casuale.

Il sistema di impegno è garantito essere vincolante dalla difficoltà del SIS. Se A * s = t = A * s', allora A * (s - s') = 0, il che significa che trovare un diverso s' risolve il difficile problema omogeneo del SIS.

La brevità di s (norma piccola) è essenziale. Senza limitare s, le soluzioni sono banali utilizzando l'algebra lineare classica. Questa restrizione della norma sostiene la natura difficile da risolvere di SIS, anche contro i computer quantistici.

Il risultato di Ajtai del 1996 ha collegato la difficoltà del problema SIS alla risoluzione dei problemi di reticolo nel caso peggiore, formando una base per le assunzioni sulla crittografia post-quantistica.

Il problema SIS consente la compressione da un grande vettore segreto s (dimensione M) a un impegno più breve t. La matrice A ha dimensioni N x M, dove N è tipicamente legato al parametro di sicurezza, rendendola attraente per le prove a conoscenza zero che necessitano di sintesi.

Nel complesso, SIS è facile da enunciare ma estremamente difficile da risolvere, giocando un ruolo fondamentale negli impegni, nelle prove a conoscenza zero e nella più ampia sicurezza post-quantistica.