Rejection-free framework of Zero-Knowledge Proof

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, ainsi que sur une technique appellée “échantillonage par rejet” proposée par Lyubashevesky (Asiacrypt09). Les principaux problèmes de l’échantillonage 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ées (KLSS, Crypto23; HSS, Crypto24)). Un second problème est son usage en boîte noire permettant des attaques par canaux auxiliaires, coûteuses à protéger quand elles sont considérées.

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).