Qu'est-ce que le problème de la grille dure ? Un fil 🧵

La cryptographie basée sur les réseaux repose sur un défi central : trouver une solution de vecteur court s à un système d'équations linéaires modulo un entier q (généralement un nombre premier ou une puissance de premier). Cela s'appelle le problème SIS (Short Integer Solution), simple en forme mais considéré comme difficile face aux attaques quantiques/classiques.

Il existe deux versions principales : la forme inhomogène utilisée comme fonction unidirectionnelle f_A(s) = A * s mod q dans les schémas d'engagement, où nous résolvons A * s = t (mod q) étant donné A et la cible t...

...et le problème homogène SIS, demandant de trouver un court s tel que A * s = 0 (mod q) pour une matrice A aléatoire.

Le schéma d'engagement est garanti comme étant contraignant par la difficulté de SIS. Si A * s = t = A * s', alors A * (s - s') = 0, ce qui signifie que trouver un s' différent résout le problème homogène difficile de SIS.

La brièveté de s (norme petite) est essentielle. Sans bornes sur s, les solutions sont triviales en utilisant l'algèbre linéaire classique. Cette restriction de norme sous-tend la nature difficile à résoudre de SIS, même face aux ordinateurs quantiques.

Le résultat d'Ajtai de 1996 a relié la difficulté du problème SIS à la résolution des problèmes de réseau dans le pire des cas, formant une base pour les hypothèses de cryptographie post-quantique.

Le problème SIS permet de compresser un grand vecteur secret s (dimension M) en un engagement plus court t. La matrice A a des dimensions N x M, où N est généralement lié au paramètre de sécurité, ce qui la rend attrayante pour les preuves à divulgation nulle de connaissance nécessitant de la concision.

Dans l'ensemble, le SIS est facile à énoncer mais extrêmement difficile à résoudre, jouant un rôle fondamental dans les engagements, les preuves à divulgation nulle de connaissance et la sécurité post-quantique plus large.