Develop with pleasure!

福岡でCloudとかBlockchainとか。

NTTを必要としない既存のNIST曲線を用いたゼロ知識証明

Cryptography ECDSA

昨年Googleが公開したECDSAを利用した匿名認証のペーパーで↓、P-256などの既存のNIST曲線で動作するゼロ知識証明の仕組みが面白そうだったので読んでみた

eprint.iacr.org

VCと匿名性とリンク不能性

ここ数年、VC（Verifiable Credential）の活用の提案が活発だけど、ユースケースによっては、発行者が認めたClaimをすべて開示する必要はなく、すべて開示されることによるプライバシー上の問題も発生する。そこで、クレデンシャルに記載されている自身の情報を必要な部分だけ開示したり（選択的開示）することができる。

たとえば、運転免許証のMDOCドキュメントにはユーザーの個人情報や属性情報のハッシュが格納される。例えば18歳以上であることのデータであれば、

{
  "valueDigests": {
    "org.iso.18013.5.1": {
      14: "8CFE...604C",  // 年齢18歳超の属性のハッシュ値
      ...
    }
  }
}

で、そのハッシュ値は以下のデータから作られる↓

"digestID": 14,
"random": "8c082af3d5d78b98bcc00bd26fae5130",  // ランダムな値（ナンス）
"elementIdentifier": "age_over_18",            // 属性の識別子
"elementValue": true                           // 属性の値

自分が18歳以上であることを証明したい場合、ハッシュの元となった上記のデータを開示することで証明することができる。

ただ、異なる機関に対して同じ認証情報が提供され、それが相互に関連付けられるとそれが同一人物によるものであることがリンクできてしまう。

冒頭の論文は、ハッシュの元のデータを公開することなくゼロ知識証明でそれが正しいことを証明することで、このリンク問題を解消する提案。

BBS+などで実現するアプローチは既にあるが、その場合BBS+をサポートするようにデバイスやセキュアエレメントの更新が必要になり、コスト面やNISTで標準化されていないスキームという点で現実的なハードルがある。この論文のスキームはECDSAベースなので、既に展開されているデバイスやセキュアエレメントを使用できるというメリットがある（たとえば、マイナンバーカードは2026年の更新で、デジタル署名アルゴリズムがRSAからECDSAに切り替わる予定とされている）。

ゼロ知識証明アプローチ

18歳以上であることをゼロ知識証明システムで証明する場合、

  • 免許証の発行者の公開鍵
  • 証明したい属性のフィールド名（age_over_18）
  • 期待するフィールドの値（true）
  • セッショントランスクリプト

を公開入力（つまり検証者が確認可能な情報）とし、

  • MDOC全体
  • デバイスの秘密鍵で署名されたデバイス署名

を秘密の入力（証明者のみが知る情報＝witness）として、「age_over_18 = trueを含む有効なMDOCを持っている」ことを証明する算術回路を構築する。

証明者は秘密の情報からプルーフを生成し、検証者は回路と公開入力およびプルーフを使って検証する。回路を使って検証される内容は↓

  1. 発行者の公開鍵に対してMSOの有効な署名があること
  2. 属性のハッシュ値の検証
  3. 属性値（true）の検証
  4. デバイスの公開鍵を用いたデバイスの認証（署名検証）
  5. 有効期限の検証

この算術回路は以下の3つのサブ回路を組み合わせたものになる：

  • ECDSAの署名検証回路
  • SHA-256回路：SHA-256のラウンド関数を回路化
  • CBOR*1パース回路

この中で、特にネックになるのがECDSAの署名検証回路になる。

ECDSAとゼロ知識証明

多くのゼロ知識証明システムでは、計算の正しさを効率的に検証するため多項式を利用している。Groth16やPlonkなどの主要なゼロ知識証明システムは、

  • 多項式の乗算：制約の検証、商多項式の計算
  • 多項式の評価：コミットメントの計算、検証点での評価
  • 多項式の補間：witnessから多項式の構築

などの計算を効率的に行うためにNTTを利用している↓

techmedia-think.hatenablog.com

ただ、↑の記事の最後でも触れたように、NTTを利用するためには適切な有限体（適切な原始根を持つ有限体）を持つ楕円曲線を選択する必要がある。

一方、現在チップなど含め広く採用されている楕円曲線はP-256曲線が主流で、このP-256曲線はNTTに適した有限体ではない（高次の原始根が存在しない）。P-256を用いたゼロ知識証明を行うには、演算を別の体でエミュレートする必要があり、回路が巨大化し、とても非効率なものになってしまう。

P-256に限らずECDSA用にNISTが定義している曲線はいずれもNTTに適していない。これは当時このようなゼロ知識証明用の要件がなかったから。後に設計されたSNARKフレンドリーな曲線BN255やBLS12-381、Pasta (Pallas/Vesta)などは、NTTと親和性があるよう意図的に設計されたもの。

Ligero + Sumcheckアプローチ

論文ではNTTに代わって、LigeroとSumcheckという2つの仕組みを利用している。

Ligeroを簡単に説明すると、証明者は実行トレースをリード・ソロモン符号でエンコードし、その結果をマークルツリーでコミットする。 検証者は、ランダムに選択した位置の評価値を要求して、それが正しくエンコードされていること、そして制約を満たしていることを確認するというスキーム。詳細は↓

techmedia-think.hatenablog.com

Ligeroでも多項式の評価を高速化するためにNTTを利用することは可能だけど、NTTがなくてもLigeroの場合、やや遅いものの愚直に多項式の評価ができる。これはLigeroが評価点に対して、ペアリングを必要としたり、プロトコルが評価点の乗法群に依存するなど、既存の証明システムで求められるような特定の構造を要求しないため。

Sumcheckプロトコルは多変数多項式の総和を効率的に検証するためのプロトコル↓

techmedia-think.hatenablog.com

Ligeroは回路全体の実行トレース（回路の各ゲートの入出力をすべて記録したデータに対するコミットメント）を作成するため、例えばSHA-256を1ブロック検証する場合、このコミットメントは約13万要素になる。コミットメントの作成にはリード・ソロモン符号によるエンコードが必要で、これがボトルネックになる。

そのため、回路の検証はSumcheckで行うようになっており、回路内のすべてのゲートを個別にチェックするのではなく全ゲートの計算結果の総和をチェックする。

  1. 署名検証を算術回路（quad form表現）に変換し、
  2. その回路をd個の層に分割し、
  3. 各層についてその値が次の層の値から正しく計算されているかをSumcheckで検証し、
  4. 最後に1点だけ自分で検証する（↑の記事内の {r_n}を選択した評価）

（回路の層毎の分割や具体的な多項式の展開とかまだよく分かってない）

SumcheckはNTT自体の代替ではなく、NTTの対象を小さくするための圧縮技術（回路の検証を対数サイズのトランスクリプトに圧縮する）という位置づけ。

Sumcheck自体はゼロ知識証明プロトコルではないため、Sumcheckでの対話記録をトランスクリプトとしてワンタイムパッドで暗号化する。そしてLigeroは元のwitnessと暗号化用のパディング、暗号化されたトランスクリプトにコミットする。

また単にSumcheckとLigeroを導入しただけでなく、P-256の有限体用に最適化されたリード・ソロモン符号やECDSAの検証に特化した回路設計、楕円曲線演算の効率的な回路化などの最適化が行われている模様。※ちなみに、厳密にNTTを使っていない訳ではなく、最適化で二次拡大体上で一部NTTによる高速化は使用してるみたい。

また最後に、ECDSAとSHA-256の回路は異なる体で動作するため、各回路の入力整合性をMAC（メッセージ認証コード）で検証する手法が提案されている。

ベンチマークでは、

  • ECDSA署名検証のゼロ知識証明は、Pixel 6 Proで約80msで生成
  • MDOC全体の匿名認証（署名検証、ハッシュ検証、CBORパースを含む）は、最大2231バイトのMSOに対して約1.2秒で証明を生成

という実用的なパフォーマンスが報告されている。

以上が論文のざっくりとした内容。

*1:Concise Binary Object Representation、JSONに似た構造を持つバイナリフォーマットでMDOCのエンコードに使われている