Les protocoles ZK utilisent des fonctions de hachage spéciales qui sont algébriquement simples. Mais si notre système de preuve supportait des tables de recherche, pourrions-nous faire mieux ? Présentation de Polocolo : une nouvelle fonction de hachage compatible avec ZK pour PlonKup, coécrite par le cryptographe de Zellic @baaaaaarkingdog.

Dans les fonctions de hachage compatibles avec ZK, les fonctions sont algébriquement simples pour plus d'efficacité. Ainsi, une attaque contre une fonction de hachage compatible avec ZK se concentre sur le problème d'entrée contraint-sortie contrainte (CICO), car résoudre le système d'équations est généralement l'attaque la plus efficace contre les fonctions de hachage compatibles avec ZK. Bien que les concepteurs choisissent soigneusement leurs structures et paramètres en tenant compte de ces vecteurs d'attaque, il est encore courant que les fonctions de hachage compatibles avec ZK soient attaquées.

Si le système de preuve ZK ne permet que des portes d'addition et de multiplication, les opérations qui ne peuvent pas être représentées algébriquement nécessitent simplement un grand nombre de contraintes. Mais si le système de preuve ZK prend en charge des portes de recherche, le nombre de portes requis est considérablement réduit. Ainsi, le principal avantage d'utiliser des portes de recherche dans les fonctions de hachage compatibles avec ZK est qu'elles ne sont pas exprimées de manière algébrique simple, ce qui peut offrir une résistance aux attaques algébriques.

Le Béton Armé est la première fonction de hachage ZK-friendly basée sur des recherches, qui se compose de couches de Briques, de Béton et de Barres (c'est ici que des tables de recherche sont utilisées). Cependant, un inconvénient majeur est le coût élevé de l'évaluation de la couche Barres dans un environnement ZK. Sur les 15 couches du Béton Armé, une seule est la couche Barres. Il est souhaitable et naturel d'itérer une couche simple sur plusieurs tours, car réduire le coût de la couche Barres et l'itérer sur plusieurs tours peut améliorer la sécurité et permettre un compromis entre efficacité et sécurité. Cela motive la conception de Polocolo.

Pour répondre au coût élevé dans la couche Bars, une approche alternative a été proposée, appelée la méthode des résidus de puissance. Polocolo est une fonction de hachage compatible avec ZK basée sur une recherche, avec une logique de conception différente. Le nom Polocolo dérive de résidu de puissance pour une recherche de table à moindre coût.

La méthode des résidus de puissance applique efficacement des tables de recherche aux éléments Fp pour un grand premier : p(≈2^256). La S-box construite en utilisant la méthode des résidus de puissance est d'un degré élevé qui nécessite seulement 14 portes PLONK, ce qui est significativement moins que les 94 portes requises pour la fonction Bar de Reinforced Concrete. En utilisant cette S-box, nous proposons Polocolo, une nouvelle fonction de hachage basée sur des tables de recherche et compatible avec les ZK.

Polocolo a été conçu par le cryptographe Zellic @baaaaaarkingdog, membre du KAIST CryptLab, avec d'autres chercheurs du même laboratoire. Dans la Partie 2, nous présenterons les spécifications détaillées et l'analyse cryptographique de Polocolo, ainsi qu'une comparaison de performance avec d'autres fonctions de hachage compatibles avec ZK.