Protokóły ZK używają specjalnych funkcji haszujących, które są algebraicznie proste. Ale jeśli nasz system dowodowy wspierałby tabele wyszukiwania, czy moglibyśmy zrobić lepiej? Przedstawiamy Polocolo: nową funkcję haszującą przyjazną dla ZK dla PlonKup, współautorstwa kryptografa Zellic @baaaaaarkingdog.

W funkcjach haszujących przyjaznych dla ZK, funkcje są algebraicznie proste dla efektywności. Zatem atak na funkcję haszującą przyjazną dla ZK koncentruje się na problemie ograniczonego wejścia i ograniczonego wyjścia (CICO), ponieważ rozwiązanie układu równań jest zazwyczaj najskuteczniejszym atakiem na funkcje haszujące przyjazne dla ZK. Chociaż projektanci starannie wybierają swoje struktury i parametry z myślą o tych wektorach ataku, nadal powszechne jest, że funkcje haszujące przyjazne dla ZK są atakowane.

Jeśli system dowodów ZK pozwala tylko na bramki dodawania i mnożenia, operacje, które nie mogą być reprezentowane algebraicznie, wymagają po prostu dużej liczby ograniczeń. Jednak jeśli system dowodów ZK obsługuje bramki wyszukiwania, wymagana liczba bramek jest dramatycznie zmniejszona. Główną zaletą używania bramek wyszukiwania w funkcjach haszujących przyjaznych dla ZK jest to, że nie są one wyrażane w prosty sposób algebraicznym, co może zapewnić odporność na ataki algebraiczne.

Beton zbrojony to pierwsza funkcja haszująca przyjazna ZK oparta na wyszukiwaniach, która składa się z warstw Cegieł, Betonu i Prętów (to tutaj używane są tabele wyszukiwania). Jednak kluczową wadą jest wysoki koszt oceny warstwy Prętów w ustawieniu ZK. Spośród 15 warstw w Betonie zbrojonym, tylko jedna to warstwa Prętów. Pożądane i naturalne jest iterowanie prostej warstwy przez wiele rund, ponieważ zmniejszenie kosztu warstwy Prętów i iterowanie jej przez wiele rund może zwiększyć bezpieczeństwo i pozwolić na kompromis między wydajnością a bezpieczeństwem. To motywuje projekt Polocolo.

Aby rozwiązać problem wysokich kosztów w warstwie Bars, zaproponowano alternatywne podejście, nazwane metodą reszty potęgowej. Polocolo to funkcja haszująca przyjazna ZK oparta na wyszukiwaniach, z inną koncepcją projektową. Nazwa Polocolo pochodzi od reszty potęgowej, co pozwala na tańsze wyszukiwanie w tabeli.

Metoda reszty potęgowej efektywnie stosuje tabele wyszukiwania do elementów Fp dla dużej liczby pierwszej: p(≈2^256). S-box zbudowany przy użyciu metody reszty potęgowej ma wysoki stopień, który wymaga tylko 14 bramek PLONK, co jest znacznie mniejszą liczbą niż 94 bramki wymagane dla funkcji Bar z Reinforced Concrete. Korzystając z tego S-boxa, proponujemy Polocolo, nową funkcję haszującą przyjazną dla ZK opartą na wyszukiwaniu.

Polocolo został zaprojektowany przez kryptografa Zellic @baaaaaarkingdog, członka KAIST CryptLab, wraz z innymi badaczami z tej samej laboratorium. W Części 2 przedstawimy szczegółowe specyfikacje i kryptanalizę Polocolo, a także porównanie wydajności z innymi funkcjami haszującymi przyjaznymi dla ZK.