Fiat–Shamir変換

Fiat–Shamir変換とは？

Fiat–Shamir変換は、特定の対話型証明プロトコルを非対話型証明またはデジタル署名に変換する暗号技術です。

検証者が新たなランダムチャレンジを証明者へ直接送る必要をなくします。

その代わりに証明者は、プロトコルのトランスクリプト、公開ステートメント、コミットメント、メッセージ、その他必要なコンテキストをハッシュしてチャレンジを計算します。

こうして作られた証明は一度生成すれば、同じ公開情報を持つ誰もが後から検証できます。

暗号学的ハッシュ関数をランダムオラクルとしてモデル化することが通常安全性の前提となるため、この手法はFiat–Shamirヒューリスティックとも呼ばれます。

Amos FiatとAdi Shamirは、1986年の論文How to Prove Yourself: Practical Solutions to Identification and Signature Problemsでこの手法を提案しました。

ブロックチェーンシステムでは、すべての証明者と検証者の間で繰り返し非公開通信を行えないことがあるため、暗号資産分野でこの技術は重要です。

非対話型証明は、トランザクション、ブロック、スマートコントラクト呼び出し、ロールアップ証明、署名、クロスチェーンメッセージに含めることができます。

Fiat–Shamir変換が解決する課題

多くの知識証明プロトコルは、もともと証明者と検証者の対話として設計されていました。

まず証明者は、隠された乱数や秘密に関連する情報をコミットします。

その後、検証者は、証明者がコミットメントを作成する前に予測できなかったランダムチャレンジを送ります。

証明者は秘密の証拠値とチャレンジを使って応答します。

検証者は、コミットメント、チャレンジ、応答、公開ステートメントがプロトコルの式を満たすか確認します。

証明者と検証者が同時にオンラインになり、複数のメッセージをやりとりする必要があるため、この対話は分散型ネットワークでは不便な場合があります。

ブロックチェーントランザクションは、証明の作成時にその場にいなかった数千のノードによって、後から個別に検証される可能性があります。

Fiat–Shamir変換は、検証者がリアルタイムで送るランダムチャレンジを、すべての検証者が再計算できる決定論的なハッシュチャレンジに置き換えます。

これにより、元の証明者と通信せずに保存、送信、検証できる、持ち運び可能な証明トランスクリプトが作られます。

対話型証明の仕組み

一般的な3メッセージの対話型プロトコルは、コミットメント、チャレンジ、応答で構成されます。

証明者は、証拠値と呼ばれる秘密の値を知っています。

公開ステートメントは、証明者が何を知っていると主張するのか、またはどの計算が正しく完了したと主張するのかを示します。

最初のステップで、証明者は秘密の乱数を生成してコミットメントを作ります。

2つ目のステップで、検証者は予測できないランダムチャレンジを生成します。

3つ目のステップで、証明者は証拠値、秘密の乱数、チャレンジを組み合わせて応答を計算します。

応答がコミットメント、チャレンジ、公開ステートメントと整合する場合に限り、検証者は証明を受理します。

コミットメントの作成時点で、チャレンジを予測できないことが重要です。

そうでなければ、不正な証明者が、事前に選んだチャレンジにしか対応できないコミットメントを構築する可能性があります。

Fiat–Shamir変換の仕組み

この変換では、検証者の2つ目のメッセージをなくし、暗号学的ハッシュの計算に置き換えます。

まず証明者は、対話型プロトコルで使うものと同じコミットメントを作成します。

次に、公開ステートメント、コミットメント、メッセージ、プロトコル識別子、その他必要なトランスクリプトデータをハッシュします。

ハッシュ出力を、プロトコルで有効なチャレンジ空間の値に変換します。

証明者は、そのチャレンジと秘密の証拠値を使って応答を計算します。

最終的な非対話型証明には通常、コミットメントと応答が含まれ、検証者はチャレンジを再計算できます。

検証者はトランスクリプトを再構成し、同じハッシュチャレンジを計算して、元の検証式を実行します。

簡略化した変換は、次のように表せます。

入力値とエンコード規則は、安全性にとって極めて重要です。

Schnorrプロトコルの例

Schnorr識別プロトコルは、Fiat–Shamir変換を分かりやすく示す例です。

生成元

と位数を持つ巡回群を考えます。

証明者は秘密鍵

と公開鍵を持っています。

証明者は

を明かさずに、それを知っていることを示したいとします。

対話型プロトコルでは、証明者はランダム値

を選び、コミットメントを送信します。

検証者はランダムチャレンジ

を返します。

証明者は

を計算します。

検証者は

が成立するか確認します。

有効な応答は、予測できないチャレンジに対して証明者が式を満たせることを示します。

SchnorrプロトコルへのFiat–Shamir適用

非対話型の方式では、検証者が生成するチャレンジをハッシュで置き換えます。

証明者は、たとえば

のようにチャレンジを計算します。

続いて、

を計算します。

証明または署名には、コミットメント

と応答が含まれます。

検証者は同じ公開鍵、コミットメント、コンテキスト、メッセージからチャレンジを再計算します。

Schnorrの検証式が成立すると、検証者は証明を受理します。

RFC 8235は、Fiat–Shamir変換を通じて3パスのSchnorr識別方式から作られる、Schnorr非対話型ゼロ知識証明を規定しています。

変換によるデジタル署名の作成

識別証明は、公開された識別情報に関連する秘密を証明者が知っていることを示します。

デジタル署名を作成するには、チャレンジを特定のメッセージにも結び付けます。

メッセージが変わるとハッシュ出力が変わり、それに伴ってチャレンジも変わります。

あるトランザクションのために作成した証明を、通常、別のトランザクションに対する有効な署名として再利用することはできません。

署名者の応答は、秘密鍵を知っていることを示すと同時に、その知識を署名対象のメッセージに結び付けます。

識別プロトコルから署名を作るこの方式は、Fiat–Shamir変換の最も重要な用途の一つです。

Fiat–ShamirとBitcoinのSchnorr署名

BitcoinのBIP 340は、secp256k1楕円曲線のSchnorr署名を規定しています。

署名チャレンジは、ノンスのコミットメント、公開鍵、メッセージをハッシュして導出されます。

これは、Fiat–Shamir変換と関連する非対話型Schnorr署名の方式に従っています。

BIP 340では、ハッシュ計算を他のプロトコルでの利用と区別するため、タグ付きハッシュも使用しています。

タグ付きハッシュでは、プロトコル固有のラベルから導出した値を入力の先頭に付けます。

これにより、同じハッシュ関数と入力形式が、異なる2つの暗号操作として解釈されるリスクを抑えます。

BIP 340の署名は、BitcoinのTaprootトランザクション規則で使われています。

Fiat–Shamir変換はBitcoinだけに限らず、さまざまな証明システム、代数群、暗号学的仮定で利用できます。

ゼロ知識証明システムにおけるFiat–Shamir

現代のゼロ知識証明システムでは、証明者と検証者の対話として説明しやすいプロトコルから構成を始めることがよくあります。

証明者は、多項式コミットメント、Merkleルート、群の要素、その他のメッセージを送ります。

検証者は、ランダムな有限体要素や問い合わせ位置を返します。

Fiat–Shamirは、検証者とリアルタイムで通信する代わりに、トランスクリプトからチャレンジを導出します。

これにより、オフチェーンで生成した証明を、ブロックチェーンノードやスマートコントラクトが後から検証できます。

Fiat–Shamir変換は、プライベートトランザクション、妥当性証明、スケーラブルなロールアップ、検証可能計算、ブロックチェーン相互運用性を支えるシステムで使用されます。

Halo2におけるFiat–Shamir

Halo2では分析上、証明プロトコルを対話型として説明しますが、Fiat–Shamir変換により非対話型で実行します。

トランスクリプトには、コミットメントやその他の証明者のメッセージが含まれます。

暗号学的ハッシュ出力は、検証者のチャレンジに変換され、多項式評価や証明の検査に使われます。

Halo2のプロトコル文書では、検証者を暗号学的に強いハッシュ関数に置き換えることで、公開コイン型の対話型証明が非対話型になると説明されています。

Halo2では、証明者がトランスクリプトの状態を作成し、再訪できる能力を考慮した安全性の特性も分析されています。

これは、Fiat–Shamirを安全に適用するには、乱数生成器を1回のハッシュ呼び出しに置き換える以上の作業が必要であることを示しています。

STARK証明におけるFiat–Shamir

STARK証明システムでは、コミットメントと検証者のチャレンジを複数回やりとりします。

チャレンジは、ランダム係数、多項式の評価点、低次数テストの問い合わせ位置などを決めるために使われます。

Fiat–Shamirチャネルは、変化していく証明トランスクリプトから非対話型の乱数を導出します。

証明者は次のチャレンジを要求する前に、コミットメントをチャネルへ取り込みます。

検証者も同じトランスクリプト操作を繰り返し、同じチャレンジを取得します。

STARK証明者向けの文書では、証明の構築全体を通じて非対話型の乱数を生成するFiat–Shamirチャネルについて説明されています。

コミットメントや公開入力が変わると、それ以降のチャレンジも変わる必要があります。

ランダムオラクルモデルとは？

ランダムオラクルモデルは、ハッシュ関数を理想的な公開ランダム関数として扱う安全性モデルです。

一意の入力ごとに、互いに独立したランダム出力が割り当てられます。

同じ入力を再度使うと、常に同じ出力が返されます。

誰でもオラクルに問い合わせられますが、対応する問い合わせをしなければ、新しい出力を予測できません。

実際のハッシュ関数は、理想的なランダムオラクルではなく決定論的なアルゴリズムです。

ランダムオラクルモデルでのFiat–Shamirの安全性証明は、この理想化された仮定のもとで安全性を示します。

実装者は、プロトコルに対してモデルと十分似た振る舞いをすると考えられる実際の暗号学的ハッシュ関数をオラクルの代わりに使用します。

ランダムオラクルモデルは有用ですが、そのモデル上の証明は、あらゆるハッシュ実装に対する無条件の証明ではありません。

ハッシュにトランスクリプト全体を含める必要がある理由

各チャレンジは、その意味に影響する先行情報すべてと結び付ける必要があります。

これには、公開パラメーター、公開鍵、ステートメント、コミットメント、メッセージ、以前のチャレンジ、チェーンID、プロトコルのバージョンなどが含まれます。

重要な値を省くと、証明を別のコンテキストへ移せてしまう可能性があります。

本来は1つの公開鍵、アプリケーション、ブロックチェーンネットワーク、プロトコル段階に限って有効な証明が、複数の対象で有効になる場合があります。

複数ラウンドの証明では、各チャレンジは、そのチャレンジより前に蓄積されたトランスクリプトに依存する必要があります。

証明者は、導出されたチャレンジを知る前に先行データへコミットしなければなりません。

最終メッセージだけをハッシュすると、対話型プロトコルに必要な順序の保証が損なわれるおそれがあります。

ドメイン分離とは？

ドメイン分離は、同じハッシュ関数を使う別々のハッシュ操作が混同されないようにします。

プロトコル名、バージョン、ネットワーク、証明段階、操作種別などを示す一意のラベルを先頭に付けられます。

残りのデータが同じでも、ラベルによってハッシュ入力が変わります。

ドメイン分離がないと、あるプロトコルでチャレンジとして作られた値が、別のプロトコルではノンス、コミットメント、チャレンジとして解釈される可能性があります。

トランザクションID、署名、Merkleツリー、鍵導出、証明トランスクリプトに同じハッシュ関数を再利用する暗号資産ソフトウェアでは、ドメイン分離が特に重要です。

BIP 340のプロトコル固有のタグ付きハッシュは、この保護の実例です。

正規エンコードが重要な理由

証明者と検証者は、まったく同じバイト列をハッシュしなければなりません。

数学的な値に、複数の有効なバイト表現が存在する場合があります。

整数は、長さ、バイト順、先頭のゼロの有無が異なる形式でエンコードできます。

楕円曲線の点には、圧縮形式、非圧縮形式、無効な代替エンコードがあり得ます。

要素の長さや境界を明確にエンコードしないと、リストの内容が曖昧になる場合があります。

正規シリアライズは、有効なトランスクリプト値ごとに受理する表現を1つに定めます。

長さのプレフィックス、型ラベル、固定幅フィールド、厳格なデコード規則によって曖昧さを防げます。

別の検証者と異なる方法で値を正規化するのではなく、正規でない値を拒否する必要があります。

チャレンジの長さと健全性

チャレンジ空間は、有効な証拠値を知らない不正な証明者が成功する確率に影響します。

1ビットのチャレンジでは、1回のラウンドで不正な証明者が正しく推測できる確率が比較的高くなります。

プロトコルを繰り返すか、より大きなチャレンジを使えば、この健全性誤差を減らせます。

必要な安全性レベルを満たす十分なサイズのチャレンジに、ハッシュ出力を変換する必要があります。

チャレンジを過度に切り詰めると、証明が弱くなる可能性があります。

ハッシュ出力を有限体や群の位数に写像する際も、許容できない統計的偏りを避けなければなりません。

プロトコルでは、チャレンジを適切に導出するため、棄却サンプリング、広い範囲での剰余計算、その他の文書化された方法を使う場合があります。

Fiat–Shamirのグラインディングとは？

グラインディングとは、証明者が許容されるコミットメントの乱数を何度も変え、そのたびにトランスクリプトをハッシュして、有利なチャレンジが現れるまで試すことです。

検証者がリアルタイムで独立してチャレンジを生成するのではなく、証明者がローカルで生成するため、この探索が可能になります。

安全性の分析では、ハッシュへの問い合わせ回数とチャレンジ空間の大きさを考慮する必要があります。

チャレンジ空間が十分に大きければ、プロトコルの仮定のもとで有用なグラインディングを計算上困難にできます。

アプリケーションでは、グラインディングを安価にしたり偏りを生じさせたりする不要な証明者制御の値を、トランスクリプトに加えるべきではありません。

Fiat–Shamirを使う証明システムでは、証明者が正直に1回だけハッシュを計算すると想定せず、この動作を分析する必要があります。

リプレイとコンテキスト結合のリスク

非対話型証明は公開データであるため、コピーできます。

証明が時点に依存しない公開ステートメントだけを示す場合、コピー自体は問題になりません。

しかし、アプリケーションが証明を所持していることを、新しいアクションや最新の認可の証拠として誤って扱うと危険です。

トランスクリプトに、トランザクションID、受取人、ネットワーク、セッション値、コントラクトアドレス、有効期限、アプリケーション固有のノンスなどを含められます。

これにより、証明を意図したコンテキストに結び付けます。

検証者がその値を現在のリクエストと照合しなければ、コンテキスト値を追加しても役に立ちません。

鮮度の要件は証明の式だけでなく、アプリケーションプロトコル全体に関わります。

Fiat–Shamirは自動的にゼロ知識性を提供しますか？

いいえ。この変換によって、あらゆるプロトコルが自動的にゼロ知識になるわけではありません。

元の対話型プロトコルが、適切なゼロ知識性または正直な検証者に対するゼロ知識性を備えている必要があります。

変換後のプロトコルも、選択した安全性モデルのもとで分析しなければなりません。

証拠値が漏れないようにするには、コミットメントにブラインディング用の乱数が必要な場合があります。

チャレンジに特別な値が含まれると秘密情報が漏れる場合、使用できるチャレンジを制限する必要があります。

証明は非対話型でも、ゼロ知識とは限りません。

非対話型とは、証明者が検証者からリアルタイムのメッセージを受け取らずに証明を作成できることを意味します。

Fiat–Shamirは自動的に健全性を提供しますか？

いいえ。あるプロトコルを安全に変換できたからといって、類似するあらゆるプロトコルの安全性が証明されるわけではありません。

元の対話型プロトコルが、必要な健全性、特別な健全性、または知識証明の特性を備えている必要があります。

ハッシュ入力とチャレンジへの写像によって、コミットメントがチャレンジより先に行われるという順序を保たなければなりません。

変換後に、より強い仮定や特別な証明を必要とするプロトコルもあります。

古典的なランダムオラクルモデルでは安全でも、量子攻撃者に対する十分な証明がない構成もあります。

開発者は、新しいプロトコルにFiat–Shamirを非形式的に適用するのではなく、検証済みの構成と安全性証明に依拠してください。

Fiat–Shamirとポスト量子暗号

Fiat–Shamirの設計パターンは、ポスト量子署名の研究にも登場します。

格子ベース、符号ベース、多者計算ベースの識別方式では、ハッシュから導出したチャレンジを利用して署名を作成できます。

一部の格子署名では、Fiat–Shamir with abortsと呼ばれる変種が使われます。

中間応答から情報が漏れる可能性がある場合や、許容される分布から外れた場合に、署名者は署名処理の一部をやり直すことがあります。

NIST FIPS 204は、Dilithiumの設計を基にした、モジュール格子ベースのデジタル署名アルゴリズムML-DSAを標準化しています。

ポスト量子署名の標準が存在しても、古典的なFiat–Shamir証明がすべて量子コンピューターに対して安全だという意味にはなりません。

量子ランダムオラクルモデルにおけるFiat–Shamir

量子攻撃者は、多数の入力の重ね合わせ状態でモデル化されたランダムオラクルに問い合わせることがあります。

これは、一度に通常の問い合わせを1つずつ送る古典的な攻撃者とは異なります。

一般にQROMと略される量子ランダムオラクルモデルでは、古典的なランダムオラクル証明がそのまま有効とは限りません。

暗号研究者は、量子攻撃者に対するFiat–Shamir構成を分析するため、追加の証明手法やプロトコル条件を開発しています。

したがって、ポスト量子安全性を主張するには、QROMまたは適切な別の量子安全性モデルを対象とした分析が必要です。

古典的な群を格子問題に置き換えるだけでは不十分です。

Fiat–Shamirとしきい値署名

しきい値署名では、署名権限を複数の参加者に分けます。

所定数の参加者が協力して、秘密鍵全体を1か所に再構成せずに1つの有効な署名を作成します。

しきい値Schnorrプロトコルでは、ノンスのコミットメントとチャレンジの計算を慎重に調整する必要があります。

チャレンジは、統合された公開鍵、統合されたノンスコミットメント、メッセージ、参加者のコンテキスト、プロトコル規則に結び付けなければなりません。

トランスクリプトの構築を誤ると、ノンス操作、ローグキーの挙動、セッションをまたぐ攻撃が可能になる場合があります。

RFC 9591は、FROSTしきい値Schnorr署名プロトコルと、ハッシュベースの暗号スイート操作を規定しています。

Fiat–Shamir変換の利点

この変換により、対応する証明システムでは検証者とのリアルタイムのやりとりが不要になります。

証明を一度作成すれば、多数のブロックチェーンノードが個別に検証できます。

通信ラウンドを減らし、非同期検証を簡素化します。

証明をトランザクション、ブロック、スマートコントラクト、分散ストレージに含められます。

検証者に秘密の乱数を渡したり、対話セッションを維持したりせずに、同じ証明を検証できます。

識別プロトコルからデジタル署名方式を実用的に構築する手段にもなります。

参加者同士が直接通信するとは限らない分散型ネットワークでは、こうした特性が有用です。

Fiat–Shamir変換の限界

この変換は通常、ランダムオラクルモデルに依存します。

あらゆる対話型証明を安全に変換できるわけではありません。

トランスクリプトの情報欠落やエンコードの不一致は、深刻な脆弱性につながる可能性があります。

証明者はハッシュを繰り返し計算できるため、安全性分析ではグラインディングを考慮する必要があります。

アプリケーションが適切なコンテキストに証明を結び付けなければ、非対話型証明はリプレイされる可能性があります。

量子安全性には別途分析が必要です。

サイドチャネルによる情報漏えい、弱い乱数、メモリ破損、秘密鍵の盗難から実装を保護するものではありません。

対話をなくしても、証明の生成に多くの計算資源を要することがあります。

Fiat–Shamir変換と対話型証明の違い

対話型証明では、証明者と検証者の間でメッセージをやりとりします。

検証者は、対話中に新たなランダムチャレンジを送ります。

Fiat–Shamir証明では、トランスクリプトのハッシュからチャレンジを導出します。

非対話型証明は、配布や非同期での検証が容易です。

対話型プロトコルでは検証者が真の乱数を使えますが、変換後のプロトコルは、ハッシュ関数がランダムオラクルに近い挙動をするという前提に依存します。

Fiat–Shamir変換と非対話型ゼロ知識証明

Fiat–Shamir変換は、非対話型証明を構築する方法の一つです。

非対話型ゼロ知識証明（NIZK）は、検証者とのリアルタイムのやりとりが不要で、保護対象の証拠値情報を明かさない証明の、より広いカテゴリーです。

Fiat–Shamirを使うNIZKもありますが、共通参照文字列、信頼できるセットアップ、透明性のあるセットアップ、その他の暗号技術を使うものもあります。

証明が非対話型だと分かっても、その作成方法までは特定できません。

Fiat–Shamir変換とデジタル署名

デジタル署名は、秘密鍵と公開検証鍵を使ってメッセージを認証します。

Fiat–Shamir変換は、特定の識別プロトコルを署名方式に変える構成手法です。

すべてのデジタル署名がFiat–Shamirによって作られるわけではありません。

Fiat–Shamir証明のすべてが、デジタル署名として機能することを目的としているわけでもありません。

証明は、個人やウォレットを認証せずに、証拠値の知識や計算の正しさを示す場合があります。

Fiat–Shamir変換とHash-to-Curve

Hash-to-Curveは、任意の入力データを楕円曲線上の有効な点に変換します。

Fiat–Shamirは、トランスクリプトデータを検証者のチャレンジに変換します。

1つの証明システムで、両方の操作を使う場合があります。

チャレンジにはスカラーが使われる一方、プロトコルの別の構成要素にはハッシュから導出した曲線上の点が必要になる場合があります。

この2つの処理には、それぞれ別個のドメイン分離とエンコード規則が必要です。

Fiat–Shamir変換とコミット・リビール

コミット・リビールプロトコルでは、参加者はコミットメントを公開し、後から隠された値を明かします。

事前情報や共有乱数の操作を抑えるために使われる場合があります。

Fiat–Shamirでは、後から公開されるランダム性を待つことはありません。

既存のトランスクリプトから決定論的なチャレンジを生成します。

どちらも暗号学的コミットメントとハッシュを使いますが、コミット・リビールとFiat–Shamirは異なる調整上の課題を解決します。

実装のベストプラクティス

開発者は、安全性が公表され、検証されたFiat–Shamir分析を備える証明システムを使うべきです。

トランスクリプトには、ステートメントとコンテキストを定める公開値をすべて含めます。

各プロトコルと証明段階に、一意のドメイン分離を設定します。

すべての値を、型と長さの境界を明示した正規形式でシリアライズします。

依存するチャレンジを生成する前に、コミットメントを取り込む必要があります。

文書化された偏りのない方法で、チャレンジ出力を有限体または群に写像します。

無効な点、正規でないスカラー、禁止された有限体の値、不正な形式のトランスクリプトは拒否します。

証明者の乱数と署名ノンスは、安全に生成するか、承認済みの決定論的方法で導出しなければなりません。

ステートメント、コミットメント、メッセージ、ネットワーク識別子、プロトコルのバージョンを変更すると、導出されるチャレンジも変わることを実装でテストします。

テストベクトルでは、トランスクリプトの順序、エンコード、ドメインタグ、空の値、境界値、不正な証明を確認してください。

Fiat–Shamirの実装でよくある間違い

公開ステートメントをハッシュせず、コミットメントだけをハッシュするのは誤りです。

証明を署名として使う場合に、メッセージを含めないのも誤りです。

曖昧な連結を使うと、異なる2つのトランスクリプトが同じバイト列になる可能性があります。

無関係なプロトコルで同じドメインラベルを使うと、プロトコル間の混同につながるおそれがあります。

先行する証明者のメッセージをすべて取り込む前に後続のチャレンジを生成すると、トランスクリプトの順序が崩れます。

短いハッシュを大きな有限体へ直接剰余写像すると、チャレンジのエントロピーが弱くなる可能性があります。

正規でない曲線上の点やスカラーを受け入れると、実装ごとに異なる表現がハッシュされるおそれがあります。

Schnorrのようなプロトコルで証明者の乱数を再利用すると、秘密の証拠値が漏れる可能性があります。

古典的な証明が自動的にポスト量子安全性を備えると想定するのも、重大な誤りです。

Fiat–Shamir変換が暗号資産にとって重要な理由

暗号資産ネットワークでは、世界中の参加者が個別に検証できる証明が必要です。

ブロックチェーントランザクションは、将来それを検証するすべてのノードとの非公開の対話に依存できません。

Fiat–Shamirにより、対話型の暗号学的処理を静的な証明データにまとめられます。

これにより、簡潔な署名、プライバシーシステム、ゼロ知識ロールアップ、検証可能なスマートコントラクト実行、しきい値ウォレット、その他のブロックチェーンアプリケーションが支えられます。

この変換は、暗号資産の重要な設計原則も示しています。

ハッシュ関数はトランザクションIDを作るだけでなく、予測困難に見えるチャレンジを生成し、プロトコルのトランスクリプト全体を結び付けることもできます。

その能力を安全に利用するには、慎重な構成、正確なシリアライズ、強力なドメイン分離、適切な安全性証明が必要です。

よくある質問

Fiat–Shamir変換は何をしますか？

特定の対話型プロトコルにおいて、検証者のランダムチャレンジを、トランスクリプトの暗号学的ハッシュから導出されるチャレンジに置き換えます。

暗号資産でFiat–Shamirが役立つのはなぜですか？

証明者とリアルタイムで対話しなくても、ブロックチェーンノードが後から証明や署名を検証できるためです。

Fiat–Shamir変換を考案したのは誰ですか？

Amos FiatとAdi Shamirが、1986年に発表した研究でこの手法を提案しました。

Fiat–Shamir変換はハッシュ関数と同じものですか？

いいえ。検証者のチャレンジ生成にハッシュ関数を使う、プロトコルの変換手法です。

対話型証明とは何ですか？

証明者と検証者が、コミットメント、チャレンジ、応答をやりとりするプロトコルです。

公開コイン型プロトコルとは何ですか？

検証者のメッセージが、公開されるランダムチャレンジで構成される対話型プロトコルです。

Fiat–Shamirトランスクリプトとは何ですか？

証明で使われる公開パラメーター、ステートメント、コミットメント、チャレンジ、応答、メッセージ、コンテキストを順番に並べたものです。

ランダムオラクルモデルとは何ですか？

ハッシュ関数を、一貫した出力を返す公開ランダム関数として扱う理想化された安全性モデルです。

実際のハッシュ関数はランダムオラクルですか？

いいえ。実際のハッシュ関数は決定論的ですが、プロトコルの分析では理想的なランダムオラクルのように動作するとして扱うことがあります。

Fiat–Shamirによってゼロ知識性が自動的に得られますか？

いいえ。元のプロトコルと変換後の構成が、必要なゼロ知識の条件を満たす必要があります。

Fiat–Shamirでデジタル署名を作成できますか？

メッセージをチャレンジのハッシュに含めれば、特定の識別プロトコルを署名に変換できます。

BitcoinはFiat–Shamirのパターンを使っていますか？

BitcoinのBIP 340 Schnorr署名では、ノンスのコミットメント、公開鍵、メッセージを結び付けるハッシュ由来のチャレンジを使います。

ゼロ知識ロールアップでFiat–Shamirは使われていますか？

多くのロールアップ証明システムでは、対話型証明プロトコルを非対話型にするため、Fiat–Shamir方式のトランスクリプトチャレンジを使います。

STARKでFiat–Shamirは使われていますか？

はい。STARKの証明者と検証者は、コミットメントから非対話型チャレンジを導出するFiat–Shamirチャネルを使用できます。

Halo2でFiat–Shamirは使われていますか？

はい。Halo2ではFiat–Shamirを通じて、対話型の証明記述を非対話型の証明にします。

ドメイン分離とは何ですか？

ハッシュ入力にプロトコル固有のラベルを加え、異なる暗号操作の出力が混同されないようにする仕組みです。

公開鍵をハッシュする必要があるのはなぜですか？

公開鍵をハッシュすると、証明や署名を意図した識別情報に結び付けられ、鍵の置換や別の鍵へのすり替え攻撃を防げる場合があります。

メッセージをハッシュする必要があるのはなぜですか？

メッセージを含めることで、あるメッセージに対する署名を別のメッセージに再利用できないようにします。

チャレンジのグラインディングとは何ですか？

トランスクリプトのハッシュが証明者に有利なチャレンジを出すまで、コミットメントを繰り返し生成することです。

Fiat–Shamir証明はリプレイされる可能性がありますか？

公開証明はコピーできるため、最新性が必要なプロトコルでは、適切なセッションまたはトランザクションのコンテキストを含めて検証しなければなりません。

正規シリアライズとは何ですか？

各トランスクリプト値に対して、受け入れられるバイト表現を1つに定める方式です。

トランスクリプトの順序が重要なのはなぜですか？

各チャレンジは、それ以前のすべてのメッセージに依存しなければなりません。そうすることで、証明者がチャレンジを知った後にコミットメントを変更することを防げます。

Fiat–Shamirは楕円曲線でも使えますか？

はい。Schnorr証明や署名では、楕円曲線群に適用されることが一般的です。

Fiat–Shamirはポスト量子暗号でも使えますか？

はい。関連する構成がポスト量子署名に使われていますが、安全性には適切な量子分析が必要です。

量子ランダムオラクルモデルとは何ですか？

量子攻撃者が量子重ね合わせを使ってランダムオラクルに問い合わせられるモデルです。

古典的な安全性証明は量子攻撃者にも有効ですか？

必ずしも有効ではありません。量子オラクルへの問い合わせや量子抽出の限界を考慮していない場合があるためです。

Fiat–Shamir with abortsとは何ですか？

応答が必要な分布やサイズの条件を満たさない場合に、署名者が処理をやり直す変種です。

Fiat–Shamirは信頼できるセットアップですか？

いいえ。この変換自体に信頼できるセットアップは必要ありませんが、基礎となる証明システムに別途セットアップ要件がある場合はあります。

スマートコントラクトはFiat–Shamir証明を検証できますか？

はい。コントラクトがトランスクリプトのハッシュを再現し、証明の式を効率的に確認できる場合に検証できます。

実装上、最大のリスクは何ですか？

主なリスクには、トランスクリプト結合の不備、曖昧なエンコード、不十分なドメイン分離、弱いノンス生成、根拠のない安全性の仮定などがあります。

まとめ

Fiat–Shamir変換は、対応する公開コイン型の対話型プロトコルを、非対話型証明またはデジタル署名に変換します。

検証者がリアルタイムに生成する予測不能なチャレンジを、証明トランスクリプトの暗号学的ハッシュから導出するチャレンジに置き換えます。

これにより、証明を一度作成すれば、ブロックチェーンノード、ウォレット、スマートコントラクト、その他の暗号資産アプリケーションが個別に検証できます。

この変換は、Schnorr署名、ゼロ知識証明システム、STARK、Halo2形式のプロトコル、しきい値署名、ポスト量子署名の研究を支えています。

安全性は、元の対話型プロトコルの特性と、ハッシュ関数のモデル化に用いる仮定に依存します。

適切な実装では、ステートメント全体、コミットメント、メッセージ、公開パラメーター、コンテキスト、プロトコルのバージョンを、正規形式のトランスクリプトに結び付ける必要があります。

また、強力なドメイン分離、十分なチャレンジサイズ、安全なノンス生成、慎重に検証されたチャレンジへの写像規則も必要です。

Fiat–Shamir変換は、あらゆる証明プロトコルの安全性を自動的に高めるものではありません。

これは強力な構成手法ですが、安全性を確保するには、厳密なプロトコル設計、規律ある実装、古典・量子両方の攻撃者を対象とした安全性分析が欠かせません。