非対話零知識証明 zk-SNARKs の解説良記事を数学的ハードルを下げつつ日本語で解説していく Part-3/7 #認証

想定読者

零知識証明 / zk-SNARKs について知りたい人
- 特に理論的側面を知りたい人
「zk-SNARKs って何だ？」という人

概要

zk-SNARKs に関する ELECTRIC COIN CO. の解説記事に簡単に補足をしながら紹介するシリーズ Part 3 です。

Part 3 のテーマは The Knowledge of Coefficient Test and Assumption(係数知識のテストと仮設) です。
Part 2から引き続いて¹、非対話零知識証明の準備になります。 Part 4 まで続きます。

読み方

Part 1 の解説記事の読み方と同様です。

込み入った議論や数学的に細かい部分は注釈(foot note)にまとめました。そのため、注釈が多くなっていますが、注釈を読まなくても大丈夫ですので、読み飛ばしていただいて構いません。

The Knowledge of Coefficient Test and Assumption

対応する記事

Explaining SNARKs Part III: The Knowledge of Coefficient Test and Assumption

一言でいうと

Part 2 において多項式の盲検(blind evaluation of polynomials)でのアリスとボブのやりとりでは、アリスはボブに $E(P(s))$ を送ることで、 $P$ を知られずに $P$ を知っていることを伝えることができる ことを確認しました。

このとき、アリスがデタラメな値を送ってしまうかもしれません。(その場合、ボブは「アリスは $P$ を知っている」と勘違いする可能性もあります。)ここでは、KCA(Knowledge of Coefficient Assumption)という仮設の下で成立するうまい方法を利用することでこれを防ぐことができることを説明しています。

Part 2の振り返りと課題

Part 2では、アリスが次数 $d$ の多項式 $P$ のHH $E(P(s))$ を $s$ を知らずに評価できることを確認しました。

しかし、このプロトコルには課題があります。 $E(P(s)$ という値をアリスが評価できるということは、アリスが実際にボブに $E(P(s))$ を送信するということを保証するものではありません。デタラメな値を送る可能性もあります。

このような事情から、アリスがプロトコルに正しく従うようにする方法が必要です。これをどのようにして実現するかは、Part 4で詳細に説明します。この記事では、そのために必要な基本的なツールについてみていきます。ここではそれを KC検定(Knowledge of Coefficient Test)　と呼ぶことにします。

記号・用語の確認

Part 1 と同様に、有限群 $\mathbb{Z} _ p$ とその生成子 $g$ が登場します。ただし、ここでは $\mathbb{Z} _ p$ を簡単に $G$ と書くことにします。
そしてもう一つ思い出しておくべきことがあります。それは $g$ と $a$ から $g^a$ を求めるのは簡単ですが、 $g^a$ と $g$ から $a$ を求めるのは難しい ということです(これを離散対数問題というのでした)。

このPart以降では、掛け算的に書くのではなく、足し算的に書くのが便利です。つまり、 $g$ を $\alpha$ だけ掛けた数のことを $g^\alpha$ ではなく、 $\alpha \cdot g$ と書くことにします。²

KC検定(KC Test)

$\alpha \in F ^ \ast _ p$³について、$a, b \neq 0$であり、$b=\alpha\cdot a$となるペア$(a,b)$を $\alpha$-ペアと呼びます。

KC検定は次のようなフローになっています。

ボブはランダムな $\alpha \in F ^ \ast _ p$ と $a \in G$ を選び、$b = \alpha \cdot a$ を計算する。
ボブはアリスに1.で作成したチャレンジペア⁴$(a,b)$を送る。
アリスは $(a,b)$とは別の $\alpha$-ペア $(a ^ \prime, b ^ \prime)$ を返送します。
ボブは$(a ^ \prime, b ^ \prime)$が $\alpha$-ペアであることを確認して、アリスの応答を受け入れる。

このフローを使うことで、アリスは、ある程度の自由度を持ちながらも返送できる値をある程度制限させることができそうです。ただし、いくつか疑問が残るので以下でその点について見ていきたいと思います。

3. でアリスはどのように α-ペアを見つけるのか

もし、アリスが $\alpha$ を知っていたとします。この場合には、 $G$ から適当に $a ^\prime$ を選び出し、 $b = \alpha \cdot a ^ \prime$ を計算することで $(a ^ \prime, b ^ \prime)$ を新たな $\alpha$-ペアとして得ることができます。

しかしながら、アリスが持っている唯一の$\alpha$に関する情報は$\alpha \cdot a$だけあり、 $G$ は離散対数問題のため、この情報からアリスは $\alpha$ を見つけることができないはずです。実は$\alpha$ を知らずに $\alpha$-ペアを見つける方法があります。

アリスは単純に一つ $\gamma \in \mathbb{F} _ p$を選び、$(a ^ \prime, b ^ \prime) = (\gamma \cdot a, \gamma \cdot b)$ とするだけです。確認のために $b ^ \prime$ を計算すると、

$$
b ^ \prime = \gamma \cdot b = \gamma \alpha \cdot a = \alpha(\gamma \cdot a) = \alpha \cdot a ^ \prime
$$

となり、$(a ^ \prime, b ^ \prime)$ が $\alpha$-ペアになっていることが確かめられます。

アリスがこの方法を利用している場合には、アリスは $a$ と $a ^ \prime$ の比($\gamma$)を知っている点に注意しておいてください。

KCA(Knowledge Coefficient Assumption)

以下の係数知識の仮設(KCA)⁵は、このことが常に成り立つとしています。

アリスがボブのチャレンジペア$(a,b)$に対して、ボブの$a$、$\alpha$の選択に対して、十分な確率で有効なレスポンスとして$(a ^ \prime, b ^ \prime)$を返すならば、アリスは$a ^ \prime = \gamma \cdot a$となるような $\gamma$ を知っている。

KC検定とKCAはPart 4で重要なツールとなります。

4. でボブはどのように α-ペアであることを確認するのか

こちらはシンプルです。ボブが $\alpha$ を知っていることを思い出しましょう。

ボブは $\alpha$ を知っているので、 $\alpha \cdot a ^ \prime$ を計算することができます。この計算の結果が $b ^ \prime$ と等しいことを確認することで、 $(a ^ \prime, b ^ \prime)$ が $\alpha$-ペアであることを確認できます。

"アリスがγを知っている" とはどういうことか

"アリスが $\gamma$ を知っている" というのは正確には何を意味しているのでしょうか？つまり、"アリスが $\gamma$ を知っている"ことを数学的定義において、どのように形式化できるでしょうか？

アリスの抽出者 という別の人物を想定することで形式化できることが大まかにわかります。アリスの抽出者は、アリスの内部状態にアクセスすることができる存在とすると、KCAを次のように定式化することができます。

アリスが $\alpha$-ペア $(a ^ \prime, b ^ \prime)$ を返す場合、アリスの抽出器は、$a ^ \prime = \gamma \cdot a$ となるような$\gamma$ を出力する⁶。

まとめ

$\alpha$-ペア $(a,b)$から別の$\alpha$-ペア $(a ^ \prime, b ^ \prime)$ を生成することができる
KC検定を利用することで、アリスの返送する値に一定の自由度を与えながら制約を加えることができる
KC検定はKCAによって担保されている

次回はPart 4(How to make Blind Evaluation of Polynomials Verifiable)です。次までが下準備になります。

二人で交互に記事を書いて進めていっております ↩
なぜこんなことするのか疑問がある人もいるでしょう。今のところは、「単純に右上に小さく書くより、左に大きく書く方が書きやすいから」と思っていただいて問題ないと思います。もしくは、「掛け算を足し算にして平気なの？」という疑問もあるでしょう。そういう時には対数の演算を思い出していただくと良いかもしれません。$\log (AB) = \log A + \log B$ というのを高校などで習ったと思います(忘れた方はこちら)。実際、上記の計算から $\log A^p = p \log A$ がわかります。この変換はここでの書き換えと非常に似ていることがわかります。この変換がどうにも納得行かない場合は、対数をとっているだけで中身は変わっていないと思っても問題ないわけです。 ↩
$\mathbb{F} ^ {\ast} _ p$ は $\mathbb{F} _ p$ (Part 2 前提知識) から $0$ を取り除いたものになります。これは Part 1 での $\mathbb{Z} _ p$ と $\mathbb{Z} ^ {\ast} _ p$ の関係と同様です。 ↩
"チャレンジ"となっているのは、アリスにも $\alpha$-ペアを3.で返送することを要求しているからです。 ↩
一般的には文献ではKEA(Knowledge of Exponent Assumption: 指数知識の仮設)と呼ばれています。伝統的には掛け算的に(乗法的に)に書かれた群について言及していたためです。この記事では、最初に足し算的に(加法的に)書き直しているので"指数"の部分を"係数"に変えています。追加の情報のために検索する場合にはKEAで検索することをおすすめします。 ↩
より完全な形式的定義では、抽出者にちょっとした"余裕"を与える必要があり、アリスが正常に応答しても抽出者がそのような $\gamma$ を出力しない確率は無視できるものであるとします。(無視できるくらいなら、本当に特殊なケースでは、抽出者が $\gamma$ を抽出できなくてもOKということです。) ↩