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 amigable con ZK para PlonKup, coescrita por el criptógrafo de Zellic @baaaaaarkingdog.

En las funciones hash amigables con ZK, las funciones son algebraicamente simples para mayor eficiencia. Por lo tanto, un ataque contra una función hash amigable con ZK se centra en el problema de entrada y salida restringida (CICO), ya que resolver el sistema de ecuaciones suele ser el ataque más efectivo contra las funciones hash amigables 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 las funciones hash amigables con ZK sean atacadas.

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

El Hormigón Armado es la primera función hash amigable con ZK basada en búsqueda, que consiste en capas de Ladrillos, Hormigón y Barras (aquí es donde se utilizan las tablas de búsqueda). Sin embargo, un inconveniente clave es el alto costo de evaluar la capa de Barras en un entorno ZK. De las 15 capas en Hormigón Armado, solo una es la capa de Barras. Es deseable y natural iterar una capa simple a lo largo de múltiples rondas, ya que reducir el costo de la capa de Barras e iterarla a lo largo de múltiples rondas puede mejorar la seguridad y permitir un equilibrio entre eficiencia y 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 potencia. Polocolo es una función hash amigable con ZK basada en búsqueda, con una lógica de diseño diferente. El nombre Polocolo deriva de residuo de potencia para una búsqueda en tabla de menor costo.

El método de residuos de potencia aplica de manera eficiente tablas de búsqueda a elementos de Fp para un gran primo: p(≈2^256). La S-box construida utilizando el método de residuos de potencia es de un alto grado que requiere solo 14 puertas PLONK, lo que es significativamente menos que las 94 puertas requeridas para la función Bar de Reinforced Concrete. Usando esta S-box, proponemos Polocolo, una nueva función hash amigable con ZK basada en tablas de búsqueda.

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