はじめに

本記事では、数論を用いたプロトコルの背後に潜んでいることの多いシグマプロトコルについて紹介します。

シグマプロトコルとは

シグマプロトコル（Σ-protocol）とは、ある命題 $x$ とその解 $w$ に対して定義され、証明者と検証者の間のやりとりが3回で完結し、かつ以下に示す3つの性質を満たす知識の証明プロトコルです。

問題設定

• 証明者Pと検証者Vはともに計算能力が多項式時間に制限されているとします。
• 証明者Pと検証者Vには命題 $x$ が与えられ、証明者Pにはその解 $w$ が与えられます。
• 「命題 $x$ の解 $w$ を知っている」という証明者Pの主張が正しいことを、検証者Vに $w$ を明かすことなく示したいとします。

プロトコルの流れ

1. 証明者Pは検証者Vにメッセージ $a$ を送信する。

2. 検証者Vは証明者Pに乱数 $e\in\{0,1,\ldots,2^t-1\}$ を送信する。

3. 証明者Pは検証者Vに $z$ を送信する。 検証者Vは $(x,a,e,z)$ に基づいて証明者の主張を受け入れるか拒否するかを選ぶ。

なお、やりとりされる文字について、 $a$ はコミット、 $e$ はチャレンジ、 $z$ はレスポンスといわれることもあります。また、 $t$ をチャレンジ長といいます。

満たす性質

• 完全性（Completeness）
  正しい入力に対して、証明者Pと検証者Vがプロトコルに従えば、検証者Vは必ず主張を受け入れる。
• 健全性（Special soundness; SS）
  命題 $x$ と、検証者が主張を受け入れるような2つのやりとり $(a,e,z),(a,e’,z’)$ （ただし $e\neq e’$ ）があれば、解 $w$ を多項式時間で計算できる。
• 条件付きゼロ知識性（Special honest verifier zero knowledge; SHVZK）
  検証者Vがプロトコルに従って乱数 $e$ を送る場合にはゼロ知識性（検証者Vには $w$ の情報は漏れない）が成り立つ。

これらの性質について述べる際、以下ではしばしばSSとSHVZKという略称を用います。

📎 SSを示すことで健全性（Soundness）、すなわち証明者が実際には知識を知らない場合に、証明者の主張が偽であることを高い確率で見抜けること、がいえます。証明者が実際には知識を知らない場合に、検証者が主張を受け入れるような2つのやりとり $(a,e,z),(a,e’,z’)$ が可能であったと仮定します。このとき、SSにより解 $w$ が計算できたことになり、証明者が実際には知識を知らないことに矛盾してしまいます。この仮定のもとでの解 $w$ の計算方法はプロトコルによって異なりますが、次節では具体例としてシュノアプロトコルでの計算方法を説明します。

📎 ゼロ知識性は、より厳密にはやりとりを模擬することができることをいいます。SHVZKの場合ではやりとり $(a,e,z)$ の確率分布について、実際のものと、検証者が得られる情報だけから作れる $(a,e,z)$ の確率分布を区別することができない、ということです。

📎 性質における”Special”とは、シグマプロトコルにおいては「この性質を満たせば、一般にいうsoundnessやHVZK（honest verifier zero knowledge; プロトコルに従う検証者に対してのみ成り立つゼロ知識性）を満たすのに十分」という意味です。

シグマプロトコルの例：シュノアプロトコル

シグマプロトコルの例として、ここではシュノアプロトコルを説明します。

シュノアプロトコルは、証明者が離散対数の知識「自然数 $y,g,p$ （ただし $p$ は素数）に対して $y\equiv g^w\mod p$ をみたす整数 $w$ を知っている」ことを示すプロトコルです。

ただし $g$ は $g^{l}\not\equiv1\mod p$ （ $l=1,\ldots,q-1$ ）かつ $g^q\equiv 1\mod p$ をみたす自然数であるとします。 $q$ は $p-1$ の約数であるような素数です。

📎 シュノアプロトコルは、ゼロ知識証明の記事においても取り上げたプロトコルです。ゼロ知識証明の記事の内容とプロトコルの流れ、性質の確認ともにほとんど同じですが、今回の説明のために少し改変しています。

プロトコルの流れ

• 証明者Pのステップ (P1)
  証明者Pは、乱数 $r\in\{0,1,\ldots,q-1\}$ を選んで $a=g^r\mod p$ を計算し、検証者Vに送信します。
• 検証者Vのステップ (V1)
  検証者Vは、一様に乱数 $e\in\{0,1,\ldots,2^t-1\}$ を選んで証明者Pに送信します（ここで $2^t<q$ とします）。
• 証明者Pのステップ (P2)
  証明者Pは、 $z=r+ew\mod q$ を計算し、検証者Vに送信します。
• 検証者Vのステップ (V2)
  検証者Vは、 $g^z\equiv ay^e\pmod p$ が成り立つかどうかを検証し、成り立てば主張を受け入れ、成り立たなければ主張を受け入れないこととします。

性質の確認

このプロトコルがシグマプロトコルの性質を満たしていることは以下のように確認できます。

• 完全性
  証明者Pが離散対数の知識 $w$ を用いて正しく $z$ を計算すれば $$ g^z\equiv g^{r+ew}\equiv g^r (g^w)^e\equiv ay^e\pmod p $$ が成り立ち、検証者Vは必ず主張を受け入れます。
• SS
  やりとり $(a,e_1,z_1),(a,e_2,z_2)$ （ただし $e_1\neq e_2$）に対して $$ g^{z_1}\equiv ay^{e_1},\,g^{z_2}\equiv ay^{e_2}\pmod p $$ となることから $$ g^{z_1-z_2}\equiv y^{e_1-e_2}\pmod p $$ が成り立ちます。ここで $$ \begin{split} \frac{z_1-z_2}{e_1-e_2}&=\frac{(r+e_1w)-(r+e_2w)}{e_1-e_2}\\ &=\frac{e_1w-e_2w}{e_1-e_2}\\ &=w \end{split} $$ が成り立つので $$ g^{\frac{z_1-z_2}{e_1-e_2}}\equiv g^w\equiv y\pmod p $$ が成り立ち、 $w=(z_1-z_2)/(e_1-e_2) \mod q$ を求めることができます。
• SHVZK
  まず、離散対数仮定が成り立つ場合、検証者Vは共有パラメータから直接離散対数の知識 $x$ を計算することはできません。また、証明者Pと検証者Vの間で交換される情報は $c,e,z$ ですが、検証者Vは証明者Pから $c,z$ を受け取らずとも、離散対数の知識 $w$ を得た場合と同じ分布から $c,e,z$ を生成することができます。具体的には、 $z$ を $\{0,\ldots,q-1\}$ からの一様乱数とし、 $c=g^zy^{-e}\mod p$ によって定めると、証明者Vが証明者Pからプロトコルのやりとりで受け取る $c,z$ と比較して、それらを生成している分布の見分けがつかないものを生成できます。したがって、 $w$ を知っていても知らなくても、検証者Vが証明者Pからこのプロトコルで得る情報量は同じです。

📎 これらの説明は、ゼロ知識証明の記事において、性質の確認について行った箇所で説明を途中で止めたようなものとなっています。したがって、SSが成立すれば健全性が、SHVZKが成立すればHVZKが成立することもわかります。

シグマプロトコルの特徴

シグマプロトコルでは完全性は確率1で成り立ちます。一方で健全性についてはそうではありません。

健全性が成り立つ確率はチャレンジ長と大きく関わっています。チャレンジ長を $t$ として考えてみます。検証者が選ぶチャレンジ $e$ は、 $\{0,1,\ldots,2^t-1\}$ からの一様乱数なので、 $e$ の値はそれぞれ確率 $2^{-t}$ で選ばれます。よって、実際には知識を知らない証明者の主張が検証者に受け入れられる確率は高々 $2^{-t}$ です。したがって、健全性が成り立つ確率は少なくとも $1-2^{-t}$ です。

また、チャレンジ長について以下の性質があることが知られています。

• 逐次反復
  チャレンジ長 $t$ の同じシグマプロトコルを同じ入力で $l$ 回実行すると、チャレンジ長 $lt$ のシグマプロトコルが得られる。
• チャレンジの長さは任意に指定できる
  チャレンジ長 $t_0$ のシグマプロトコルが存在すれば、どんなチャレンジ長 $t$ のシグマプロトコルも作成できる。

したがって、健全性が成り立つ確率を1に近づけるには、同じプロトコルを複数回繰り返すか、チャレンジ長を非常に大きな数にとればよいことがわかります。

シグマプロトコルの有用性

シグマプロトコルを組み合わせることで、複数の主張を同時に示すようなものを簡単に構成することができます。

ANDのプロトコル

証明者が「 $x_0$ に対する知識 $w_0$ を知っている」かつ「 $x_1$ に対する知識 $w_1$ を知っている」ということを、検証者に $w_0,w_1$ を明かすことなく示したいとします。この場合には、「 $x_0$ に対する知識 $w_0$ を知っている」についてのシグマプロトコルと、「 $x_1$ に対する知識 $w_1$ を知っている」についてのシグマプロトコルの2つを、同じチャレンジ $e$ を利用して同時並行で行えばよいです。具体的には、以下のようにプロトコルを構成します。

プロトコルの流れ

$a_0,z_0$ と $a_1,z_1$ はそれぞれ命題 $x_0$ と $x_1$ に対するやりとりに対応するものとします。

1. 証明者Pは検証者Vにメッセージ $(a_0,a_1)$ を送信する。

2. 検証者Vは証明者Pに乱数 $e\in\{0,1,\ldots,2^t-1\}$ を送信する。

3. 証明者Pは検証者Vに $(z_0,z_1)$ を送信する。 検証者Vは $(x_0,a_0,e,z_0)$ と $(x_1,a_1,e,z_1)$ に基づいて証明者の主張を受け入れるか拒否するかを選ぶ。

2つのシグマプロトコルが並行に動いているとみなせるため、このプロトコルがシグマプロトコルとなっていることは容易に確認できます。なお、2つ以上の複数の主張に対するプロトコルを構成したい場合でも同様に考えることができます。

ORのプロトコル

証明者が「 $x_0$ に対する知識 $w_0$ を知っている」または「 $x_1$ に対する知識 $w_1$ を知っている」ことを、検証者にそれらの知識のどちらを知っているかを明かすことなく示したいとします。今回は証明者は「 $x_0$ に対する知識 $w_0$ を知っている」が「 $x_1$ に対する知識 $w_1$ を知っている」のではないとします。このとき、以下のようなプロトコルを考えればこれが実現できます。このプロトコルはORのプロトコル（OR proof）と呼ばれています。

プロトコルの流れ

1. 証明者Pは適当な乱数 $e_1$ を選択し、 $x_1$ に対するシグマプロトコルを模擬することでやりとり $(a_1,e_1,z_1)$ を生成します。 また、証明者Pは $x_0$ に対するシグマプロトコルの最初のメッセージ $a_0$ を生成します。 証明者Pは検証者Vに $(a_0,a_1)$ を送信します。

2. 検証者Vは証明者Pに乱数 $s\in\{0,1,\ldots,2^t-1\}$ を送信します。

3. 証明者Pは $e_0=s\oplus e_1$ と定めます。これを $x_0$ に対するシグマプロトコルのチャレンジ $e_0$ とみなせば、レスポンス $z_0$ を計算することができます。 証明者Pは検証者Vに $(e_0,z_0,e_1,z_1)$ を送信します。

4. 検証者Vは $e_0\oplus e_1=s$ を確認し、$(x_0,a_0,e_0,z_0)$ と $(x_1,a_1,e_1,z_1)$ に基づいて証明者の主張を受け入れるか拒否するかを選びます。

逆に、「 $x_1$ に対する知識 $w_1$ を知っている」が「 $x_0$ に対する知識 $w_0$ を知っている」のではない場合は、添え字の $0$ と $1$ を入れ替えれば同じことがいえます。検証者からすれば、添字が入れ替わったところで同じメッセージが来ていることに変わりはありません。

プロトコルの流れを見ればわかるように、1.でシグマプロトコルを模擬するというトリックを使っています。証明者が知っている知識に対しては通常通りにプロトコルを実行して検証者を納得させ、知らない知識に対しては通常のものと見分けがつかないダミーを作ることで検証者を騙す、というのが主要なアイデアです。このトリックにより、全体としては証明者がどちらの命題の知識を知っているのかが検証者にわからないままでプロトコルを遂行することができます。

このことに関連して、ORプロトコルは証拠識別不可能性（witness indistinguishable）という、正直な検証者に限らない任意の検証者に対して、証明者がどちらの命題を証明しているのかf識別ができないという良い性質を持つことが知られています。

このプロトコルはシグマプロトコルになっています。実際、やりとりの回数自体は $(a_0,a_1)$ と $s$ と $(e_0,z_0,e_1,z_1)$ の3回のみであり、完全性、健全性、条件付きゼロ知識性を満たすことも示せるので、このプロトコルは「 $x_0$ か $x_1$ に対する知識 $w$ を知っている」についてのシグマプロトコルです。

また、上で示したプロトコルを拡張すると、 $n$ 個の命題 $x_0,\ldots,x_{n-1}$ のうち $k$ 個の知識を知っていることを示すようなプロトコルを構成することも可能です。

シグマプロトコルとゼロ知識証明

ゼロ知識証明とは、完全性、健全性、ゼロ知識性を備えた二者対話式のプロトコルであり、シグマプロトコルと似た性質を持ちます。偶然似通ったわけではなく、この分野の発展の歴史的な経緯とも関係しています。

性質の違い

シグマプロトコルはゼロ知識証明と性質が似ていますが、以下に述べるように大きく4つの異なる特徴を持ちます。

• 対話回数
  シグマプロトコルは、やりとりの回数に3回という制限があります。一方で、ゼロ知識証明は回数の制限はなく、検証者が乱数 $e$ 以外の情報を送るということも可能です。
• 証明すること
  証明することがらが、シグマプロトコルでは「証明者の知識」だが、ゼロ知識証明ではそうとは限らず「何らかの主張」です。
• 検証者の計算能力の制限
  シグマプロトコルでは検証者がプロトコルに従うことが仮定されていますが、ゼロ知識証明では必ずしもそうではなく、プロトコルから逸脱する場合も考慮します。
• 証明者の計算能力の制限
  シグマプロトコルでは証明者の計算能力が多項式時間に制限されていますが、ゼロ知識証明では証明者の計算能力は無制限です。

シグマプロトコルとゼロ知識証明の発展の歴史

ゼロ知識証明の初期の研究では、どのような計算量クラスに対してゼロ知識証明が構成できるか、やりとりの回数を減らすにはどのような構成にすればよいか、といった研究が主に行われていました。

一方で、実用的なプロトコルとするための方法も考案されていきました。そのひとつが今回紹介したシュノアプロトコルです。

これらの実用的なプロトコルは、完全な意味でのゼロ知識証明ではありませんでしたが、それらは実用化に有利な共通の性質を持っていたため、後からこれらを総称してシグマプロトコルと呼ぶことにし、シグマプロトコルはゼロ知識証明とは別の概念として研究がなされるようになりました。

シグマプロトコルの応用

シグマプロトコルを利用することで認証プロトコル、署名スキーム、コミットメントプロトコル、ゼロ知識証明プロトコルなど、さまざまなものを構成することができます。

これらのプロトコルを構成する際に、わざわざシグマプロトコルを考えて構成する必要もないように思えます。しかし、シグマプロトコルを考える利点もあります。まず、ベースとなるシグマプロトコルさえ構成できれば、あとはそれぞれのプロトコルに必要な性質を備えるように変換を施すことで、比較的容易にプロトコルが構成することができるといえます。さらに、ベースとなるシグマプロトコルは対話回数に制限があり、さらに効率的な変換方法もいくつか知られていることから、冗長でない効率的なプロトコルが構成しやすいといえます。

まとめ

• シグマプロトコルは、完全性、健全性、条件付きゼロ知識性を備えた、やりとりが3回で完結する知識証明プロトコルである
• シグマプロトコルの健全性を高い確率で成立させるには、チャレンジ長を大きくするか、何回もプロトコルを反復実行すればよい
• 似た概念であるゼロ知識証明とは対話回数、証明内容、検証者と証明者の計算能力の面で異なった性質を持つ

参考文献

[1] Hazay, Carmit, and Yehuda Lindell. Efficient secure two-party protocols: Techniques and constructions. Springer Science & Business Media, 2010.

[2] 尾形わかは. Σプロトコルとその応用. オペレーションズ・リサーチ: 経営の科学 54.3, 2009.

[3] https://crypto.stackexchange.com/questions/84094/difference-between-shvzk-and-hvzk