ZKAttest：WebAuthnの改良 | HashPort技術ブログ

Table of Contents

はじめに

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

zkattestが作られた目的等は [12]のブログで解説されています(英語)。

前提知識

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

コミットメント方式

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

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

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

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

リング署名

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

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

ゼロ知識証明

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

完全性(completeness)
Pの証明が正しければ、Vが証明が真であることが必ず分かる。
健全性(soundness)
Pの証明が間違っていれば、Vは高い確率で証明が偽であると分かる。
ゼロ知識性(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ラウンドのやり取り

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

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

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

背景

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

WebAuthn

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

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

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]より引用。