У протоколах ZK використовуються спеціальні хеш-функції, які є алгебраїчно простими. Але якби наша система доведення підтримувала таблиці пошуку, чи могли б ми зробити краще? Представляємо Polocolo: нову ZK-дружню хеш-функцію для PlonKup, співавтором якої є Zellic Cryptographer @baaaaaarkingdog.

У хеш-функціях, дружніх до ZK, функції алгебраїчно прості для ефективності. Таким чином, атака на ZK-дружню хеш-функцію фокусується на проблемі обмеженого виходу з обмеженим входом (CICO), оскільки розв'язання системи рівнянь зазвичай є найефективнішою атакою проти дружніх до ZK хеш-функцій. Незважаючи на те, що дизайнери ретельно вибирають свої структури та параметри з урахуванням цих векторів атак, все ще часто атакують хеш-функції, дружні до ZK.

Якщо система доведення ZK допускає лише додавання та мультиплікативні вентилі, то операції, які не можуть бути представлені алгебраїчно, просто вимагають великої кількості обмежень. Але якщо система захисту ZK підтримує вентилі пошуку, необхідна кількість воріт різко зменшується. Таким чином, основна перевага використання вентилів пошуку в дружніх до ZK хеш-функціях полягає в тому, що вони не виражаються простим алгебраїчним способом, що може забезпечити стійкість до алгебраїчних атак.

Залізобетон — це перша хеш-функція, дружня до ZK на основі пошуку, яка складається з шарів Bricks, Concrete та Bars (саме тут використовуються таблиці пошуку). Однак ключовим недоліком є висока вартість оцінки шару Bars в умовах ZK. З 15 шарів у залізобетоні лише один є шаром брусів. Бажано і природно повторювати простий шар протягом кількох раундів, оскільки зниження вартості шару Bars і його повторення протягом кількох раундів може підвищити безпеку та дозволити компроміс між ефективністю та безпекою. Це мотивує дизайн Polocolo.

Щоб вирішити проблему високої вартості в шарі Барса, був запропонований альтернативний підхід, який отримав назву метод залишків потужності. Polocolo — це хеш-функція, дружня до ZK, на основі пошуку, з іншим обґрунтуванням дизайну. Назва Polocolo походить від залишку електроенергії для пошуку в таблиці нижчої вартості.

Метод залишків степеня ефективно застосовує таблиці пошуку до елементів Fp для великого простого числа: p(≈2^256). S-box, побудований за методом залишків потужності, має високий ступінь, який вимагає всього 14 воріт PLONK, що значно менше, ніж 94 затвори, необхідних для роботи бару із залізобетону. Використовуючи цей S-box, ми пропонуємо Polocolo, нову хеш-функцію на основі пошуку, дружню до ZK.

Polocolo був розроблений Зелліком Криптографом @baaaaaarkingdog, членом KAIST CryptLab, разом з колегами-дослідниками з тієї ж лабораторії. У Частині 2 ми представимо детальні специфікації та криптоаналіз Polocolo, а також порівняння продуктивності з іншими хеш-функціями, дружніми до ZK.