Antoine Douteau (Caen). Framework de preuves à divulgation nulle de connaissances, sans rejet, basé sur le problème Hint-MLWE

Les frameworks de preuves “Engager-et-prouver” sont une généralisation des protocoles à divulgation
nulle de connaissances. Ils permettent, en plus de prouver la connaissance d’un élément secret à un
tiers, de prouver certaines propriétés et relations. Par exemple, qu’un vecteur est de petite norme
ou encore qu’il est solution d’une relation quadratique publique. Un de ces frameworks (LNP,
Crypto22) base sa sécurité sur des problèmes cryptographiques reposant sur les réseaux euclidiens
structurés, ainsi que sur une technique appelée “échantillonnage par rejet” proposée par
Lyubashevsky (Asiacrypt09). Les principaux problèmes de l’échantillonnage par rejet est qu’il induit
une construction en temps non constant, dépendant du taux de rejet (ne permettant pas la
construction de certains schémas cryptographiques avancés (KLSS, Crypto23; HSS, Crypto24)). Un
second problème est son usage en boîte noire permettant des attaques par canaux auxiliaires (Zhao et
al. IEEE DATE26), coûteuses à protéger quand elles sont considérées (Coron, TCHES 2024).  Notre
contribution est une modification du framework existant, sans rejet permettant de prouver dès qu’un
secret est solution de relations linéaires et/ou quadratiques, en basant la sécurité sur l’hypothèse
Hint-MLWE (KLSS, Crypto23).