Protokoly ZK používají speciální hashovací funkce, které jsou algebraicky jednoduché. Ale pokud by náš důkazový systém podporoval vyhledávací tabulky, mohli bychom to udělat lépe? Představujeme Polocolo: novou hashovací funkci pro PlonKup, jejímž spoluautorem je Zellic Cryptographer @baaaaaarkingdog.

V hashovacích funkcích přátelských k ZK jsou funkce algebraicky jednoduché kvůli efektivitě. Útok proti hašovací funkci přátelské k ZK se tedy zaměřuje na problém CICO (constrained-input constrained-output), protože řešení soustavy rovnic je obvykle nejúčinnějším útokem proti hašovacím funkcím přátelským k ZK. Přestože návrháři pečlivě vybírají své struktury a parametry s ohledem na tyto vektory útoku, je stále běžné, že hashovací funkce přátelské k ZK jsou napadány.

Pokud důkazový systém ZK umožňuje pouze sčítání a násobení hradel, operace, které nemohou být reprezentovány algebraicky, jednoduše vyžadují velký počet omezení. Pokud však systém ZK proof podporuje vyhledávací brány, požadovaný počet hradel se dramaticky sníží. Hlavní výhodou použití vyhledávacích bran v hašovacích funkcích vhodných pro ZK je tedy to, že nejsou vyjádřeny jednoduchým algebraickým způsobem, což může poskytnout odolnost proti algebraickým útokům.

Železobeton je první vyhledávací hašovací funkce založená na ZK, která se skládá z vrstev Cihly, Beton a Pruty (zde se používají vyhledávací tabulky). Klíčovou nevýhodou jsou však vysoké náklady na vyhodnocení vrstvy Bars v nastavení ZK. Z 15 vrstev železobetonu je pouze jedna vrstvou Pruty. Je žádoucí a přirozené iterovat jednoduchou vrstvu ve více kolech, protože snížení nákladů na vrstvu Bars a její iterace ve více kolech může zvýšit bezpečnost a umožnit kompromis mezi efektivitou a bezpečností. To motivuje design Polocolo.

Aby bylo možné řešit vysoké náklady ve vrstvě Bars, byl navržen alternativní přístup, nazvaný metoda zbytků energie. Polocolo je hashovací funkce založená na vyhledávání vhodná pro ZK s odlišným designovým zdůvodněním. Název Polocolo je odvozen od zbytků energie pro levnější vyhledávání v tabulkách.

Metoda power residue efektivně aplikuje vyhledávací tabulky na prvky Fp pro velké prvočíslo: p(≈2^256). S-box postavený pomocí metody zbytků energie má vysoký stupeň, který vyžaduje pouze 14 hradel PLONK, což je výrazně méně než 94 hradel požadovaných pro funkci tyče ze železobetonu. Pomocí tohoto S-boxu navrhujeme Polocolo, novou hashovací funkci založenou na ZK.

Polocolo navrhl Zellic Cryptographer @baaaaaarkingdog, člen KAIST CryptLab, spolu s dalšími výzkumníky ze stejné laboratoře. V části 2 představíme podrobné specifikace a kryptoanalýzu Polocola spolu s porovnáním výkonu s dalšími hashovacími funkcemi vhodnými pro ZK.