ZKAttest:WebAuthnの改良

お知らせ
Table of Content

はじめに

この記事ではECDSA署名を行うシグマプロトコルであるZKAttest([1]ZKAttest: Ring and Group Signatures for Existing ECDSA Keys)について解説します。

前提知識

ZKAttestの理解の前提となる知識について解説します。

コミットメント方式

コミットメント方式とは秘密情報を「コミット」することでその値を秘密に保ちつつも後からその値を明らかにすることができるアルゴリズム方式のことです。典型的にはハッシュ関数を通してハッシュ化した情報だけを先に渡しておき、変更できないデータの存在について互いに合意した後でハッシュ関数に通す前の値を公開するようなものが考えられます。

以下の2つの性質が求められます。

  1. 秘匿性(Hinding property)
    受信者は(値が開示される前には)コミットした値を知ることができない
  2. 拘束性(Binding property)
    送信者は後から送った値を変えられない。つまり送信者がコミットした値と違う値を公開できないことを保証する。

ZKAttestでは群とその生成元から構成されるPedersen commitment[2]を用います。生成元g,hとランダムに生成した値rによるxのPedersen commitmentはCom(x;r) = xg+rhで与えられます。

リング署名

リング署名とはあるグループの公開鍵のリストが与えられ、その中に真の署名者が存在することを保証する署名のことです。管理者がいない状態で匿名性を保証しながらグループの代表による署名が可能です。
リング署名には以下の性質が求められます。

  1. Anonymous against full key exposure
    検証者は誰が署名したかを知ることができない。
  2. Unforgeable against insider corruption
    グループ内部の者はたとえ署名者自身であっても署名者が誰であるのかを証明できない。(たとえ署名に何か問題があっても署名の開示は不可能である。)

ゼロ知識証明

シグマプロトコルについて解説するためにゼロ知識証明について説明します。証明者Pと検証者Vの間のゼロ知識証明プロトコルとは以下の条件を満たす証明プロトコルのことです。

  1. 完全性(completeness)
    Pの証明が正しければ、Vが証明が真であることが必ず分かる。
  2. 健全性(soundness)
    Pの証明が間違っていれば、Vは高い確率で証明が偽であると分かる。
  3. ゼロ知識性(zero-knowledge)
    Pの持つ知識をVは得ることができない。厳密には知識wがなくても入力xとランダムなeに対して出力(a,e,z)であってプロトコルに従うPとVのやり取りと確率的に区別できないものを出力できるシミュレータを構成できること、と言い換えられる。

初めの2つの条件は通常の証明プロトコルでも満たされるので最後の条件が重要です。

また証明者Pと検証者Vの間の証明において、PとVの間の何度か繰り返されるやりとり(transcript) によって行われる証明を対話証明(interactive proof)と言います。

一方、PがVに一度証明を送ることによって行われる証明を非対話証明(non-interactive proof)と言います。

ゼロ知識証明は対話証明でなければ構成できないことが証明されています。
しかしCRS(Common Reference Strings)と呼ばれるPとV共に公開された情報の存在を仮定した状況(信頼されたセットアップ)では対話型証明を非対話なゼロ知識証明(Non-Interactive Zero-Knoledge proof, NIZK)に構築し直せます。

NIZKはデジタル署名や暗号通貨、ブロックチェーンに応用されています。

シグマプロトコル

シグマプロトコルとは証明者Pと検証者V、共通の入力x、Pだけが持つ知識w(witness)が与えられた上での3ラウンドのやり取り

  1. Pがメッセージaを送る。
  2. Vがランダムな(ビット数は指定)チャレンジeを送る。
  3. Pが返答としてzを送り、Vがx,a,e,zに基づいてPの証明が正しいかどうかを検証する。

からなるプロトコルです。以下の性質を満たします。

  1. 完全性(completeness)
    Pの証明が正しければ、Vが証明が真であることが必ず分かる。
  2. SHVZK(Special Honest-Verifier Zero-Knowledge)
    Vがプロトコルに従う場合、つまりVが送るeがランダムに選ばれた場合ゼロ知識性が保証される。(通常のゼロ知識性より弱い。)
  3. Special soundness
    同一の入力x、メッセージaと異なるチャレンジeに対する、Vが正しいと認める複数のやりとりが与えられるとPの知識wが分かる。

背景

ZKAttestの背景について解説します。

WebAuthn

現在ブラウザでは認証システムとしてWebAuthn[9]が広く用いられています。WebAuthnはパスワードを用いずにウェブブラウザ上でECDSAなどの公開鍵暗号を用いて認証を行うAPIで、以下の利点があります。

  1. フィッシングからの保護
    サイトのオリジンによって署名が変わるので偽のサイトは認証を通過することができません。
  2. 情報漏洩の影響を軽減
    パスワードと異なり公開鍵は漏洩しても問題がありません。
  3. パスワード攻撃に強い
    パスワード認証ではユーザーがパスワードを再利用する可能性があります。また公開鍵暗号の署名の方がテキストより膨大で公開鍵の推測は困難です。

WebAuthnはChromeやSafariなどのほとんどのブラウザで使用されています。

WebAuthnの具体的な動作

WebAuthnは以下の二者の仲介を行うAPIです。

  • サーバー(Server)
    検証者とも呼ばれ作成された認証情報の登録と認証を行う。
  • 認証器(Authenticator)
    作成された認証情報を格納するハードウェア。

WebAuthnの動作は登録と認証の2つの手順に分かれます。

  • 登録
    1. サーバーがアプリケーションにチャレンジ、ユーザー情報、検証者情報を送信。
    2. ブラウザが認証器(Authenticator)に認証データを用意させる。
    3. 認証器がユーザ確認を行い新しい公開鍵と証明書から成る認証情報(Attenstation)を作成。ユーザ確認は指紋認証やパスワード認証によって行われる。
    4. 認証器が作成した認証情報をブラウザに返す。
    5. アプリケーションがサーバーに認証情報を返す。
    6. サーバーが公開鍵を使って認証情報を検証し、ユーザを登録する。

      登録の手順。[9]より引用。

  • 認証
    1. サーバーがユーザーの登録を確認しチャレンジを送信。
    2. ブラウザが認証器に認証データを用意させる。
    3. 認証器がユーザ確認を行いアサーション(Assertion)を作成。アサーションには秘密鍵を用いて作成された署名が含まれる。
    4. 認証器が作成した情報をブラウザに返す。
    5. アプリケーションがサーバーにアサーションを返す。
    6. サーバが公開鍵を用いてアサーション内の署名を検証し、ユーザーを認証する。

      認証の手順。[9]より引用。

なお、登録と認証開始時のアプリケーションからサーバへの要求はWebAuthnの範囲外です。

WebAuthnの問題点

登録時に認証器からサーバーに送信される認証情報の中には認証器の情報が含まれています。特に認証器が特定されてしまうのでリング署名を行うことはできません。しかし認証器の情報を含めないと認証情報の信頼度が低下してしまいます。

この問題を解決するためシグマプロトコルによってリング署名化されたECDSA署名を実現し認証器の情報を明かさずに認証を行いたい、というのがZKAttestの背景です。

まとめと感想

ZKAttestの理解の前提知識と背景について解説を行いました。この論文はあまり知られていないようですが個人的には大きな可能性があるのではないかと思います。ZKAttestの具体的なプロトコルについては次回解説します。

参考文献

[1]https://dl.acm.org/doi/abs/10.1007/978-3-030-99277-4_4
[2]https://doi.org/10.1007/3-540-46766-1_9
[3]https://www.w3.org/TR/webauthn-2/
[4]Bröker, R.: Constructing Elliptic Curves of Prescribed Order. Ph.D. thesis, Leiden (2006)
[5]https://doi.org/10.1007/3-540-48910-X_8
[6] https://doi.org/10.1007/978-3-662-46803-6_9
[7] IPUSIRON(2017). 暗号技術の全て, 翔泳社
[8] Damgard(2010). On Σ-protocols https://www.cs.au.dk/~ivan/Sigma.pdf
Goldwasser, S., Micali, S., & Rackoff, C. (1985). The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). STOC 1985.
[9] WebAuthn: https://developer.mozilla.org/ja/docs/Web/API/Web_Authentication_API#Registration

タイトルとURLをコピーしました