ZK-protocollen gebruiken speciale hashfuncties die algebraïsch eenvoudig zijn. Maar als ons bewijs systeem opzoektabellen ondersteunde, zouden we het dan beter kunnen doen? Introductie van Polocolo: een nieuwe ZK-vriendelijke hashfunctie voor PlonKup, mede geschreven door Zellic Cryptograaf @baaaaaarkingdog.

In ZK-vriendelijke hashfuncties zijn de functies algebraïsch eenvoudig voor efficiëntie. Een aanval op een ZK-vriendelijke hashfunctie richt zich op het constrained-input constrained-output (CICO) probleem, aangezien het oplossen van het systeem van vergelijkingen meestal de meest effectieve aanval is op ZK-vriendelijke hashfuncties. Hoewel ontwerpers hun structuren en parameters zorgvuldig kiezen met deze aanvalsvectoren in gedachten, is het nog steeds gebruikelijk dat ZK-vriendelijke hashfuncties worden aangevallen.

Als het ZK-bewijs systeem alleen optel- en vermenigvuldigingspoorten toestaat, vereisen bewerkingen die niet algebraïsch kunnen worden weergegeven simpelweg een groot aantal beperkingen. Maar als het ZK-bewijs systeem opzoekpoorten ondersteunt, wordt het vereiste aantal poorten dramatisch verminderd. Dus het belangrijkste voordeel van het gebruik van opzoekpoorten in ZK-vriendelijke hashfuncties is dat ze niet op een eenvoudige algebraïsche manier worden uitgedrukt, wat weerstand kan bieden tegen algebraïsche aanvallen.

Versterkt Beton is de eerste op lookup gebaseerde ZK-vriendelijke hashfunctie, die bestaat uit lagen van Bakstenen, Beton en Staven (hier worden lookup-tabellen gebruikt). Een belangrijk nadeel is echter de hoge kosten van het evalueren van de Stavenlaag in een ZK-instelling. Van de 15 lagen in Versterkt Beton is er maar één de Stavenlaag. Het is wenselijk en natuurlijk om een eenvoudige laag over meerdere rondes te itereren, aangezien het verlagen van de kosten van de Stavenlaag en het itereren ervan over meerdere rondes de beveiliging kan verbeteren en een afweging tussen efficiëntie en beveiliging mogelijk maakt. Dit motiveert het ontwerp van Polocolo.

Om de hoge kosten in de Bars-laag aan te pakken, werd een alternatieve benadering voorgesteld, de power residue-methode genoemd. Polocolo is een op lookup gebaseerde ZK-vriendelijke hashfunctie met een andere ontwerprichtlijn. De naam Polocolo is afgeleid van power residue voor goedkopere tabelopzoekingen.

De krachtresidu methode past efficiënt opzoektabellen toe op Fp-elementen voor een grote priem: p(≈2^256). De S-box die is gebouwd met behulp van de krachtresidu methode heeft een hoge graad die slechts 14 PLONK-poorten vereist, wat aanzienlijk minder is dan de 94 poorten die nodig zijn voor de Bar-functie van Gewapend Beton. Met deze S-box stellen we Polocolo voor, een nieuwe op lookup gebaseerde ZK-vriendelijke hashfunctie.

Polocolo is ontworpen door Zellic Cryptographer @baaaaaarkingdog, een lid van het KAIST CryptLab, samen met medewetenschappers van hetzelfde lab. In Deel 2 zullen we de gedetailleerde specificaties en cryptanalyse van Polocolo introduceren, samen met een prestatievergelijking met andere ZK-vriendelijke hashfuncties.