ZKプロトコルは、代数的に単純な特別なハッシュ関数を使用します。 しかし、私たちの証明システムがルックアップテーブルをサポートしているなら、もっとうまくやれるでしょうか? Polocoloの紹介:Zellic Cryptographer @baaaaaarkingdogが共同執筆したPlonKup用の新しいZKフレンドリーなハッシュ関数。

ZKに適したハッシュ関数では、効率のために関数が代数的に単純です。 したがって、ZKに適したハッシュ関数に対する攻撃は、通常、連立方程式を解くことがZKに適したハッシュ関数に対する最も効果的な攻撃であるため、制約入力制約出力(CICO)問題に焦点を当てます。 設計者はこれらの攻撃ベクトルを念頭に置いて構造とパラメータを慎重に選択していますが、ZKに適したハッシュ関数が攻撃されることは依然として一般的です。

ZK証明システムが加算ゲートと乗算ゲートのみを許可する場合、代数的に表現できない演算は単に多数の制約を必要とします。 しかし、ZKプルーフシステムがルックアップゲートをサポートしている場合、必要なゲートの数は劇的に減少します。 したがって、ZKに適したハッシュ関数でルックアップゲートを使用する主な利点は、単純な代数的な方法で表現されないため、代数攻撃に対する耐性を提供できることです。

鉄筋コンクリートは、最初のルックアップベースのZKフレンドリーなハッシュ関数であり、レンガ、コンクリート、およびバーレイヤーで構成されています(これはルックアップテーブルが使用される場所です)。 ただし、主な欠点は、ZK 設定で Bars レイヤーを評価するコストが高いことです。鉄筋コンクリートの 15 のレイヤーのうち、1 つだけが Bars レイヤーです。 Bars レイヤーのコストを削減し、複数のラウンドで反復することでセキュリティが強化され、効率とセキュリティのトレードオフが可能になる可能性があるため、単純なレイヤーを複数のラウンドで反復することは望ましく、自然なことです。 これがポロコロのデザインのモチベーションになっています。

バー層の高コストに対処するために、電力残渣法と呼ばれる代替アプローチが提案されました。 Polocolo は、ルックアップベースの ZK に適したハッシュ関数で、設計上の根拠が異なります。 Polocoloという名前は、低コストのテーブル検索のための電力残渣に由来しています。

べき乗残基法は、大きな素数 p(≈2^256) の Fp 要素にルックアップ テーブルを効率的に適用します。 パワーリダレーション法で製作されたS-BOXは、PLONKゲートが14個しか必要としない高品位で、鉄筋コンクリートのバー機能に必要な94ゲートよりも大幅に少なくなっています。 このS-boxを使用して、新しいルックアップベースのZKフレンドリーなハッシュ関数であるPolocoloを提案します。

Polocoloは、KAIST CryptLabのメンバーであるZellic Cryptographer @baaaaaarkingdogと同じ研究室の同僚の研究者によって設計されました。 第2回では、Polocoloの詳細な仕様と暗号解読、他のZKフレンドリーなハッシュ関数とのパフォーマンス比較をご紹介します。