Schnorrの非対話型ゼロ知識証明（NIZKP）について定義しているrfc8235を読んでみた

Schnorrにおいて、ある離散対数の知識を知っていることをゼロ知識で証明するプロトコル（Schnorr NIZK proof）が2017年に~~rfc2835~~rfc8235として登録されていたので読んでみた。

RFC 8235: Schnorr Non-interactive Zero-Knowledge Proof

簡単に概要を説明すると、

証明者と検証者がいる中で、証明者がもつ離散対数の知識を検証者にその知識を明かすことなく証明するプロトコルがゼロ知識証明で、二者間で↓のようなやりとりをする。

通常は証明者が自身が証明したい離散対数に対応した公開鍵と、それとは別にランダムに選択した離散対数に対応する公開鍵を検証者に公開する。
検証者はチャレンジを生成し、それを証明者に送る。
証明者が2つの離散対数とそのチャレンジを使ってある計算をし、その計算結果を検証者に送る。
検証者はその値がと証明者から送られた公開鍵を使って証明者が離散対数の知識を知っていることを確認する。

↑は検証者が生成したチャレンジをベースに計算するので対話的な証明プロセスになってるけど、このチャレンジの生成を決定論的に行うことで（Fiat-Shamir変換）、2,3の対話が不要になり非対話型にできる。

Schnorrベースでこの非対話型のゼロ知識証明のプロトコル仕様を定義してるのがrfc2835で、有限体および楕円曲線を利用した定義がそれぞれされている↓
（でもこれSchnorr限定というものではなく、使われてる計算はそのままECDSAでも成立するよね。）

以下RFCの定義内容の意訳。

1. イントロダクション

堅牢な公開鍵プロトコルを設計するためのよく知られている法則は

「チェックが出来ない場合、受け取ったメッセージが特定の形式（例えば既知のrに対するg^rのように）を持っていると仮定しないこと。」

これはCrypto '95でRoss AndersonとRoger Needhamによって定義された８つの原則の６つめの原則で、「sixth principle」として知られている。過去３０年の間に、多くの公開鍵プロトコルが、この原則に違反によって、攻撃を防ぐことができなかった。

「sixth principle」を満たすのにいくつか方法があるが、ここでは値を明らかにすることなく、その離散対数の知識を知っていことを証明する１つの技法について説明する。この技法はSchnorr NIZK proofと呼ばれ、three-pass Schnorr identification schemeを非対話型に変形したものだ。安全な暗号学的ハッシュ関数が存在する仮定のもと、オリジナルのSchnorr identification schemeはFiat-Shamir変換によって非対話型になる。

Schnorr NIZK proofは有限体もしくは楕円曲線で実装できる。基底の巡回群が異なることを除いて、技術仕様は基本的に同じだ。完全性を期すため、この文書では有限体と楕円曲線両方のSchnorr NIZK proofについて説明する。

2. 有限体上のSchnorr NIZK proof

2.1 グループパラメータ

有限体上で実装された場合、Schnorr NIZK proofはDSAと同じグループ設定を使用できる。pとqを2つの大きな素数とする（q | p - 1）。Gqを素位数qのZqの部分群とし、gを部分群の生成元とする。異なるセキュリティレベルを提供する(p, q, r)の値については、NIST Cryptographic Toolkitのサンプルを参照。128 bit以上のセキュリティレベルが推奨される。ここではDSAグループは例としてのみ使用されている。離散対数問題（DLP）が扱いにくい他の乗法群もSchnorr NIZK proofの実装に適している。

2.2 Schnorr Identification Scheme

Schnorr identification schemeのルールはアリス（証明者）とボブ（検証者）の間で対話的に実行される。スキームのセットアップにおいて、アリスは自身の公開鍵A = g^a mod pを公開する。ここでaは[0, q-1]からランダムに一様に選択された秘密鍵。

プロトコルは以下の3つをパスすることで動作する。

アリスは[1, q-1]の中からランダムに一様にvを選択し、V = g^v mod pを計算する。そして計算したVをボブに送る。
ボブは[1, t-1]からランダムに一様にチャレンジcを選択する。ここでtはチャレンジのビット長（例えば t = 160）。ボブは選択したcをアリスに送る。
アリスはr = v - c * a mod nを計算し、結果をボブに送る。

ボブはプロトコルに最後に以下のチェックを行う。いずれかのチェックが失敗すると、同定は失敗する。

Aが[1, p-1]内にあり、A^q = 1 mod pであることを検証する。
V = g^r * A^c mod pを検証する。

最初のチェックは、Aが有効な公開鍵であることを保証するので、基底gに対するAの離散対数は実在する。一部のアプリケーションでは、アイデンティティ要素を有効な公開鍵として明確に除外することがある点については注意する価値がある。その場合、Aが[1, p-1]内にあるかの代わりに[2, p-1]内にあるかチェックする必要がある。

プロセスは以下の図のようにまとめられる。

2.3 非対話型ゼロ知識証明

Schnorr NIZK proofは、Fiat-Shamir変換を介して非対話型のSchnorr identification schemeが得られる。この変換には、チャレンジを発行する代わりに安全な暗号学的ハッシュ関数の使用が含まれる。より具体的には、チャレンジはc = H(g || V || A || UserID || OtherInfo)として再定義される。ここでUserIDは証明者の一意の識別子でOtherInfoはOPTIONALデータである。ここでハッシュ関数HはSHA-256、SHA-384、SHA-512、SHA3-256、SHA3-384、またはSHA3-512などの安全な暗号ハッシュ関数とする。ハッシュのアウトプットのビット長は少なくともサブグループの位数qのビット長と同じでなければならない。

OtherInfoは、Schnorr NIZK proofにコンテキスト情報を柔軟に含めることができるよう定義されているため、このドキュメントで定義されている手法は一般的に有用だ。例えば、 Schnorr NIZK proof上に構築されたいくつかのプロトコルの中には、プロトコル名やタイムスタンプなどより多くのコンテキスト情報を含めるものもある。OtherInfoの正確な項目は、定義する特定のプロトコルに任されなければならない。ただし、特定のプロトコルにおいてOtherinfoは固定され、プロトコルで明示的に定義されていなければならない。

ハッシュ関数内では、連結される2つの項目の間に明確な境界が存在する必要がある。その項目のバイト長を表す4バイトの整数を常に項目の先頭に付与することが推奨される。OtherInfoには複数の副項目が含まれる場合がある。その場合、隣接する副項目間の明確な境界を保証するため同じルールが適用されるものとする。

2.4 計算コスト

要約すると、A = g^aの指数の知識を証明するため、アリスは{UserID, OtherInfo, V = g^v mod p, r = v - a*c mod q}を含むSchnorr NIZK proofを生成する。ここでcはc = H(g || V || A || UserID || OtherInfo)。

Schnorr NIZK proofを計算するコストは、およそ1つのモジュロ累乗、すなわちg^v mod pの計算だ。実際には、この冪乗は効率を最適化するためオフラインで事前にされてもいい。残りの演算（乱数生成、剰余乗算、ハッシュ計算）コストは冪乗剰余と比較して無視できる。

Schnorr NIZK proofを検証するコストは、およそ2つの累乗で、1つはA^q mod pの計算で、もう1つはg^r * A^c mod pの計算。

3. 楕円曲線を利用したSchnorr NIZK proof

3.1 グループパラメータ

楕円曲線上に実装すると、Schnorr NIZK proofはECDSAと同じ楕円曲線の設定を使うことがある。説明目的のため、プライムフィールド上の曲線のみ（NIST P-256など）をここで説明する。Schnorr NIZK proofの実装には、ECDSAに適したバイナリフィールド以外の曲線を使うことも可能だ。E(Fp)を有限体Fp上で定義される楕円曲線とする。ここでpは巨大な素数。続いてGを素数位数nのE(Fp)に対する部分群のジェネレータとして機能する曲線上の基点とする。部分群の余因子（cofactor）はhで示され、通常は４以下の小さな値。加算やマイナス、スカラ乗算などの楕円曲線の演算の詳細については、Handbook of Applied Cryptographyを参照。 elliptic-curve-point-to-octet-stringを含むデータ型の変換は、SEC1の2.3節参照。ここではNISTの曲線を一例として使う。楕円曲線の離散対数問題が簡単に解けない限り、Curve25519などの他の安全な曲線も実装に適している。

3.2 Schnorr Identification Scheme

スキームのセットアップにあたり、アリスは秘密鍵aを[1, n-1]の中からランダムに選択し、公開鍵A = G × [a]を公開する。

プロトコルは以下の３つのやりとりで動作する。

アリスは[1, n-1]の中からランダムな数値vを選択し、V = G × [v]を計算し、Vをボブに送る。
ボブはチャレンジcを[1, t-1]からランダムに選択する。ここでtはチャレンジのビット長（例えば t = 80）。ボブは選択したcをアリスに送る。
アリスはr = v - c * a mod nを計算し、結果をボブに送る。

プロトコルの最後に、ボブは以下のチェックを行う。いずれかのチェックに失敗した場合、検証は失敗する。

Aが楕円曲線上の有効な点であり、A × [h]が無限遠点でないことを検証する。
V = G x [r] + A x [c]が成立するか検証する。

最初のチェックは、基底Gに対するAの離散対数が実際に存在することの確認＝Aが有効な公開鍵であることを保証する。ECDSAのような設定は、公開鍵の検証に完全な冪剰余が必要なDSAのようなグループ設定と異なり、公開鍵の検証コストは余因子が小さいため（1,２もしくは４など）ほとんど無視できる。

プロセスをまとめると以下のようになる。

3.2 非対話型ゼロ知識証明

これまでと同様、チャレンジを発行する代わりに安全な暗号学的ハッシュ関数を使用することで、Fiat-Shamir変換により非対話型になる。チャレンジcはc = H(G || V || A || UserID || OtherInfo)として定義され、UserIDは証明者の一意な識別子で、OtherInfoは前述したようにOPTIONALデータである。

3.3 計算コスト

まとめると、楕円曲線上の基底Gにに関してA = G × [a]の離散対数の知識を証明するため、アリスは{UserID, OtherInfo, V = G x [v], r = v - a*c mod n}を含むSchnorr NIZK proofを生成する。cはc = H(G || V || A || UserID || OtherInfo)。

Schnorr NIZK proofを生成するためのコストは、１つのスカラ乗算G x [v]をするコストになる。

楕円曲線の設定でSchnorr NIZK proofの検証をするコストは、楕円曲線に対して１つの乗算、つまりG x [r] + A x [c]を計算するコストになる。楕円曲線の設定において、公開鍵検証のコストは本質的にフリーだ。

4. Schnorr NIZK proofのバリエーション

有限体の設定では、証明者は（UserIDとOtherInfoと一緒に）(V, r)を送信し、検証者は最初にcを計算し、続いてV = g^r * A^c mod pをチェックする。これは2048〜3072 bitのサイズのZpの要素Vと、224〜256 bitのサイズのZpの要素rの伝送を必要とする。以下のように、Zpの２つの要素に送信するデータを以下のように削減することができる。

修正版は、証明者が(V, r)の代わりに(c, r)を送信すること以外は同じように動作する。検証者はV = g^r * A^c mod pを計算し、H(g || V || A || UserID || OtherInfo) = cが成立するかチェックする。この変形例のセキュリティは、(c, r)からVを、(V, r)からcを計算することができるという事実に従う。したがって、(c, r)を送信することは(V, c, r)を送信することと同じで、それは(V, r)を送信することと同じだ。このためSchnorr NIZK proofのサイズは大幅に削減でき、証明者と検証者の計算コストは同じままである。

(V, r)の送信を(c, r)の送信に置き換えることで、同様の最適化手法を楕円曲線を使った設定にも適用できるが、利点は限定的になる。Vが圧縮形式でエンコードされると、この最適化により削減できるサイズは1 bit分のみであるためで、ゼロ知識証明の生成および検証の計算コストは以前と同じだ。

5. Schnorr NIZK proofの応用

J-PAKEやYAKのようないくつかの主要な交換プロトコルでは、参加者が離散対数の知識を持っていることを保証するためにSchnorr NIZK proofに依存している。このドキュメントに記載されている技法は、それらのプロトコルに直接適用することができる。

OtherInfoを含めることで、 Schnorr NIZK proofは幅広い応用に対応するため一般に便利で柔軟性がある。例えば記載されている技術は、ユーザーが公開鍵登録期間中、秘密鍵の証明を証明期間に示すのに使うことができる。ハッシュにはある鍵の登録手順にリンクされているデータが含まれていることが保証されなければならない（OtherInfo内に、CA名、有効期間、申請者の電子メールの連絡先など）。この場合Schnorr NIZK proofは、DSAもしくはECDSAを使って生成されたCSRと機能的に同等だ。

6. セキュリティに関する考慮事項

Schnorrの同定プロトコルは、検証者が正直で離散対数問題の困難性という仮定のもと、以下の特性を満たすことが証明されている。

完全性
離散対数を知っている証明者は常に検証チャレンジに合格できる。
健全性
離散対数を知らない敵対者が、検証チャレンジに合格する確率は無視できるレベルしかない（2^-t）。
正直な検証者のゼロ知識性
証明者は正直な検証者に、自身が離散対数を知っているかどうか1 bitも情報を漏らさない。

Fiat-Shamir変換はセキュアな暗号学的ハッシュ関数が存在すると仮定した上で、three-pass対話型のゼロ知識証明プロトコルを（検証者がランダムにチャレンジを選択する）非対話型プロトコルに変換する標準的な手法だ。ハッシュ関数は公に定義されているので、証明者は単独でチャレンジを計算することができ、プロトコルを非対話型にすることができる。この場合、証明者が送信した各コミットメント（g^v もしくは G x [v]）に、一様にランダムにチャレンジcを割り当てるため、ハッシュ関数（正確にはセキュリティ証明のランダムオラクル）は正直な検証者を実装する。これはまさに正直な検証者がやることだ。

Schnorrの同定スキームと非対話型の要素には、安全な乱数生成器が必要なことに注意することが重要だ。特に、vのランダム精度が低いと秘密の離散対数が明らかになる。例えば、（ランダム値の生成に失敗して）同じランダム値 V = g^v mod p が証明者によって2回使われたとする。そして検証者が異なるチャレンジ c と c' を選択する（もしくは、2つの異なるOtherInfo dataにハッシュ関数が使われ、2つの異なるチャレンジ c と c' を生成する）。敵対者は2つの証明トランスクリプト（V, c, r）と（V, c', r'）を観察して、以下のように秘密鍵を計算する。

(r-r')/(c'-c) = (v-a*c-v+a*c')/(c'-c) = a mod q.

より一般的には、このような攻撃は、同じvが生成されることはないが敵対者にとって既知の値wに対してv' = v + wという関係が成り立つvとv'を生成するような、やや精度の良い（でも安全ではない）乱数生成器でも機能する。敵対者が2つの証明トランスクリプト（V, c, r）と（V, c', r'）を観察すると仮定すると、敵対者は以下のように秘密鍵を計算することができる。

(r-r'+w)/(c'-c) = (v-a*c-v-w+a*c'+w)/(c'-c) = a mod q

この例は、Schnorrのスキームで一時的なシークレットvを生成するのに安全な乱数生成器を使用することの重要性を強調している。

最後に、セキュリティプロトコルが非対話的な方法で離散対数の知識を証明するSchnorr NIZK proofに依存する場合、リプレイ攻撃の脅威が考慮される。例えばSchnorr NIZK proofは（暗号プロトコルで項目間に好ましくない相関関係を導入するため）証明者自身にリプレイバックされる可能性がある。この特定の攻撃はハッシュに一意のUserIDを含めることで防止される。検証者は証明者のUserIDが有効なアイデンティティで自身のものと異なることを確認しなければならない。特定のプロトコルのコンテキストによって、他の形式のリプレイ攻撃について考慮し、必要に応じてOtherinfoに適切なコンテキスト情報を含める必要がある。

Develop with pleasure!

福岡でCloudとかBlockchainとか。