Protokol ZK menggunakan fungsi hash khusus yang sederhana secara aljabar. Tetapi jika sistem bukti kami mendukung tabel pencarian, dapatkah kami melakukan yang lebih baik? Memperkenalkan Polocolo: fungsi hash ramah ZK baru untuk PlonKup, yang ditulis bersama oleh Zellic Cryptographer @baaaaaarkingdog.

Dalam fungsi hash yang ramah ZK, fungsinya secara aljabar sederhana untuk efisiensi. Jadi serangan terhadap fungsi hash yang ramah ZK berfokus pada masalah output terbatas input terbatas (CICO), karena memecahkan sistem persamaan biasanya merupakan serangan paling efektif terhadap fungsi hash yang ramah ZK. Meskipun desainer dengan hati-hati memilih struktur dan parameter mereka dengan mempertimbangkan vektor serangan ini, masih umum untuk fungsi hash yang ramah ZK diserang.

Jika sistem bukti ZK hanya mengizinkan gerbang penjumlahan dan perkalian, operasi yang tidak dapat direpresentasikan secara aljabar hanya membutuhkan sejumlah besar kendala. Tetapi jika sistem bukti ZK mendukung gerbang pencarian, jumlah gerbang yang diperlukan berkurang secara dramatis. Jadi keuntungan utama menggunakan gerbang pencarian dalam fungsi hash yang ramah ZK adalah tidak diekspresikan dengan cara aljabar sederhana, yang dapat memberikan ketahanan terhadap serangan aljabar.

Beton Bertulang adalah fungsi hash ramah ZK berbasis pencarian pertama, yang terdiri dari lapisan Batu Bata, Beton, dan Batang (di sinilah tabel pencarian digunakan). Namun, kelemahan utama adalah tingginya biaya untuk mengevaluasi lapisan Bar dalam pengaturan ZK. Dari 15 lapisan Beton Bertetulang, hanya satu lapisan Bar. Sangat diinginkan dan wajar untuk mengulangi lapisan sederhana selama beberapa putaran karena mengurangi biaya lapisan Bar dan mengulanginya selama beberapa putaran dapat meningkatkan keamanan dan memungkinkan pertukaran antara efisiensi dan keamanan. Ini memotivasi desain Polocolo.

Untuk mengatasi biaya tinggi di lapisan Bar, pendekatan alternatif diusulkan, yang dijuluki metode residu daya. Polocolo adalah fungsi hash ramah ZK berbasis pencarian dengan alasan desain yang berbeda. Nama Polocolo berasal dari residu daya untuk pencarian tabel berbiaya lebih rendah.

Metode residu daya secara efisien menerapkan tabel pencarian ke elemen Fp untuk bilangan prima besar: p(≈2^256). S-box yang dibangun menggunakan metode residu daya memiliki tingkat tinggi yang hanya membutuhkan 14 gerbang PLONK, yang secara signifikan lebih sedikit daripada 94 gerbang yang diperlukan untuk fungsi Bar dari Beton Bertetulang. Dengan menggunakan S-box ini, kami mengusulkan Polocolo, fungsi hash ramah ZK berbasis pencarian baru.

Polocolo dirancang oleh Zellic Cryptographer @baaaaaarkingdog, anggota KAIST CryptLab, bersama dengan sesama peneliti dari laboratorium yang sama. Di Bagian 2, kami akan memperkenalkan spesifikasi terperinci dan kriptanalisis Polocolo, bersama dengan perbandingan kinerja dengan fungsi hash ramah ZK lainnya.