Os protocolos ZK usam funções hash especiais que são algebricamente simples. Mas se nosso sistema de prova suportasse tabelas de pesquisa, poderíamos fazer melhor? Apresentando o Polocolo: uma nova função de hash compatível com ZK para PlonKup, de coautoria do Zellic Cryptographer @baaaaaarkingdog.

Em funções de hash compatíveis com ZK, as funções são algebricamente simples para eficiência. Portanto, um ataque contra uma função hash compatível com ZK se concentra no problema de entrada restrita (CICO), já que resolver o sistema de equações geralmente é o ataque mais eficaz contra funções hash compatíveis com ZK. Embora os designers escolham cuidadosamente suas estruturas e parâmetros com esses vetores de ataque em mente, ainda é comum que funções de hash compatíveis com ZK sejam atacadas.

Se o sistema de prova ZK permite apenas portas de adição e multiplicativas, as operações que não podem ser representadas algebricamente simplesmente requerem um grande número de restrições. Mas se o sistema de prova ZK suportar portas de pesquisa, o número necessário de portas será drasticamente reduzido. Portanto, a principal vantagem de usar portas de pesquisa em funções hash compatíveis com ZK é que elas não são expressas de maneira algébrica simples, o que pode fornecer resistência a ataques algébricos.

Concreto Armado é a primeira função de hash compatível com ZK baseada em pesquisa, que consiste em camadas de Tijolos, Concreto e Barras (é aqui que as tabelas de pesquisa são usadas). No entanto, uma desvantagem importante é o alto custo de avaliar a camada de barras em uma configuração ZK. Das 15 camadas em Concreto Armado, apenas uma é a camada de Barras. É desejável e natural iterar uma camada simples em várias rodadas, pois reduzir o custo da camada de barras e iterá-la em várias rodadas pode aumentar a segurança e permitir uma compensação entre eficiência e segurança. Isso motiva o design de Polocolo.

Para lidar com o alto custo na camada de Barras, uma abordagem alternativa foi proposta, apelidada de método do resíduo de energia. Polocolo é uma função de hash compatível com ZK baseada em pesquisa com uma lógica de design diferente. O nome Polocolo deriva de resíduo de energia para pesquisa de tabela de menor custo.

O método do resíduo de potência aplica eficientemente tabelas de pesquisa a elementos Fp para um primo grande: p(≈2^256). A caixa S construída usando o método de resíduo de energia é de alto grau que requer apenas 14 portas PLONK, o que é significativamente menos do que as 94 portas necessárias para a função Bar de concreto armado. Usando esta S-box, propomos o Polocolo, uma nova função hash compatível com ZK baseada em pesquisa.

O Polocolo foi projetado pelo criptógrafo Zellic @baaaaaarkingdog, membro do KAIST CryptLab, juntamente com outros pesquisadores do mesmo laboratório. Na Parte 2, apresentaremos as especificações detalhadas e a criptoanálise do Polocolo, juntamente com uma comparação de desempenho com outras funções de hash compatíveis com ZK.