Los protocolos ZK utilizan funciones hash especiales que son algebraicamente simples. Pero si nuestro sistema de pruebas admitiera tablas de búsqueda, ¿podríamos hacerlo mejor? Presentamos Polocolo: una nueva función hash compatible con ZK para PlonKup, en coautoría con Zellic Cryptographer @baaaaaarkingdog.

En las funciones hash compatibles con ZK, las funciones son algebraicamente simples para mayor eficiencia. Por lo tanto, un ataque contra una función hash compatible con ZK se centra en el problema de entrada restringida y salida restringida (CICO), ya que resolver el sistema de ecuaciones suele ser el ataque más eficaz contra las funciones hash compatibles con ZK. Aunque los diseñadores eligen cuidadosamente sus estructuras y parámetros teniendo en cuenta estos vectores de ataque, sigue siendo común que se ataquen las funciones hash compatibles con ZK.

Si el sistema de prueba ZK solo permite puertas de suma y multiplicación, las operaciones que no se pueden representar algebraicamente simplemente requieren un gran número de restricciones. Pero si el sistema a prueba de ZK admite puertas de búsqueda, el número requerido de puertas se reduce drásticamente. Por lo tanto, la principal ventaja de usar puertas de búsqueda en funciones hash compatibles con ZK es que no se expresan de una manera algebraica simple, lo que puede proporcionar resistencia a los ataques algebraicos.

Hormigón armado es la primera función hash ZK basada en búsquedas, que consta de capas Bricks, Concrete y Bars (aquí es donde se utilizan las tablas de búsqueda). Sin embargo, un inconveniente clave es el alto costo de evaluar la capa Bars en una configuración ZK. De las 15 capas de hormigón armado, solo una es la capa de barras. Es deseable y natural iterar una capa simple en varias rondas, ya que reducir el costo de la capa Bars e iterarla en varias rondas puede mejorar la seguridad y permitir un equilibrio entre la eficiencia y la seguridad. Esto motiva el diseño de Polocolo.

Para abordar el alto costo en la capa de barras, se propuso un enfoque alternativo, denominado método de residuo de energía. Polocolo es una función hash ZK basada en búsquedas con una lógica de diseño diferente. El nombre Polocolo deriva de un residuo de energía para la búsqueda de tablas de menor costo.

El método de residuo de potencia aplica eficientemente tablas de búsqueda a elementos Fp para un número primo grande: p(≈2^256). La caja S construida con el método de residuo de energía es de un alto grado que requiere solo 14 puertas PLONK, que es significativamente menos que las 94 puertas requeridas para la función de barra de hormigón armado. Con este S-box, proponemos Polocolo, una nueva función hash ZK basada en búsquedas.

Polocolo fue diseñado por el criptógrafo Zellic @baaaaaarkingdog, miembro del KAIST CryptLab, junto con otros investigadores del mismo laboratorio. En la Parte 2, presentaremos las especificaciones detalladas y el criptoanálisis de Polocolo, junto con una comparación de rendimiento con otras funciones hash compatibles con ZK.