ゼロ知識証明入門
土井洋(情報セキュリティ大学院大学)
今回の入門講義では，ゼロ知識証明とはどんな技術か，そのからくりはどうなっているか，またなぜ知識を示さないのに証明といえるのか，解説を行う．
効率のよいゼロ知識証明では，数学の一分野である整数論が利用される場合が多い．本講義では例として整数のべき乗演算と密接に関係がある離散対数問題を取り上げ，ゼロ知識証明の解説を行う．
最終的にはゼロ知識証明を利用した電子署名の構成例を示す．

暗号入門7講(2007/05/25)

1

離散対数問題• 離散対数とは
G=(Z/pZ)*, g：位数がq(素数)の元
y=gx mod p に対してxをyのgに対する離散対数とよぶ• 離散対数問題(p,q,g,y)が与えられた時，xを求める問題•

離散対数問題は，|p|，|q|が十分大きい場合は，困難な問題であると考えられている．
– |p|=1024以上，|q|=160以上• 離散対数は指数と呼ばれる場合もある．

今回の講義では，離散対数問題をターゲットとする暗号入門7講(2007/05/25)21離散対数問題と暗号• 公開鍵暗号系を構築するための2大数論問
題– 素因数分解問題• RSA暗号で利用される(1978)– 公開鍵暗号方式の現在の標準– 離散対数問題• DH鍵配送方式で利用される(1976)• ElGamal暗号で利用される(1985)

暗号入門7講(2007/05/25)

3ゼロ知識対話証明• 1985年に概念が提案された– Goldwasser, Micali, Rackoff, ”The knowledge
complexity of interactive proof-systems”• 特徴– 対話証明
– ゼロ知識– 確率的

今回の講義で扱う命題Xは，「公開された情報yに対する秘密情報xを知っていること」に限定する．
暗号入門7講(2007/05/25)

42

対話証明とは(直感的)• (通常の)証明の拡張– 証明者Pと検証者Vが存在する．
– PとVでデータのやり取り(対話)をする．
– 対話のあと，Vは，Pの主張(命題Xが真であること)が正しいと(非常に高い確率で)確信する(=受理する)．
命題X
P(証明者)

V(検証者)

受理する
or受理しない

秘密情報：x暗号入門7講(2007/05/25)

5ゼロ知識とは(直感的)• 証明したいこと(Pの主張(命題Xが真であること)が正しいこと)以外の情報がVに漏れない[命題X](p,q,g,y)が与えられた時，y≡gx (mod p) となるxを知っている．
[ゼロ知識対話証明後]
検証者Vは，(証明者Pが) y≡gx (mod p) となるxを知っているに違いないと確信する．しかしながら，検証者Vはxに関する情報を得ることができない．
暗号入門7講(2007/05/25)

63

ゼロ知識対話証明
秘密情報：x

命題X

P(証明者)

V(検証者)

受理する
or受理しない• 完全性– 命題Xが真の場合，(P,Vがプロトコルに従えば)Vは高確率で受理する．

• 健全性– 命題Xが偽の場合，(P*がどのように振舞っても)Vが受理する確率は無視できるほど小さい．

• ゼロ知識性– PとVの対話証明で得られるデータは，(Pなしでも)模倣できる．
模倣=simulation
暗号入門7講(2007/05/25)

7

模倣とは?
• 本物の対話により得られる対話データと識別できない対話データを(秘密情報xを用いずに)作成すること．
• 模倣のレベル– 確率分布の差異が重要• PとVのデータのやり取り･･･確率変数• 模倣･･･確率変数– 模倣が完全であるとは･･･• 上記2つの確率変数の分布が同一

暗号入門7講(2007/05/25)84例1(p,q,g,y)が与えられた時y≡gx (mod p)となるxを知っている

V(検証者)

P(証明者)(秘密の情報x)a =gr mod p(r:乱数)

c= r+bx mod q

ab:0/1をランダムに選ぶbc?

gc ≡ayb (mod p)
この対話を(a,b,c)と略記する

暗号入門7講(2007/05/25)

9

攻撃1(例1への攻撃)•xを知らない証明者P*がVに受理させる方法
1. bをランダムに選ぶ
2. cもランダムに選ぶ
3. a=gcy-b mod pを計算する．
4. aをＶに送り，Vの返事を待つ．
5-1 もし，Vがbを返してきたら，cをVに送る．(攻撃成功)
5-2 もし，Vがbを返してこなかったら，中止．(攻撃失敗)

暗号入門7講(2007/05/25)

105考察(攻撃1の成功確率)
攻撃1の成功確率=1/2•–

P*がランダムに選んだbを，たまたまVが選べばVは受理してしまう．

攻撃成功
確率=1/2–

P*が選ばなかったb’対して，P*がc’を送ることができるか?⇒できない

攻撃失敗
確率=1/2

攻撃方法に依存しない議論
Pが(a, 0, c0 ), (a,1, c1 )を生成できるとせよ．
検証式g c0 ≡ a mod p, g c1 ≡ ay mod pが成立するので
g c1 − c0 ≡ y mod pが成り立つ．つまり，離散対数
x = c1 − c0 mod qをPが計算できたことになる．
これはPがxを知らないということに反する．
暗号入門7講(2007/05/25)

11

例2(例1の繰り返し)(p,q,g,y)が与えられた時y≡gx (mod p)となるxを知っている

V(検証者)

P(証明者)(秘密の情報x)a =gr mod p(r:乱数)

c= r+bx mod q

ab:0/1をランダムに選ぶbc?

gc ≡ayb (mod p)

20回繰り返せばどうなるか?

暗号入門7講(2007/05/25)

126考察(例2への攻撃1の成功確率)
攻撃1の成功確率=1/2
20回繰り返すとどうなるか?

••
–

•

成功確率は1/220=0.000001

Vの視点–

Pがxを知らないのなら，20回繰り返せば，1回くらいは失敗するはず(確率0.999999で1回は失敗するはず)．

暗号入門7講(2007/05/25)

13

例2の評価(繰り返し回数=20回)• 完全性– Pがy≡gx (mod p)となるxを知っていたら，Vは必ず受理する．
• 健全性– P*がy≡gx (mod p)となるxを知らない場合，20回連続してVが受理する確率は1/220≒0.000001，逆にVが受理しない確率は11/220≒0.999999• ゼロ知識性– 対話を模倣可能(攻撃1を繰り返せばよい)
攻撃1が成功したら終了．外れたら，その回だけやり直し．
20回分の対話の模倣には40回程度試行する必要がある．
本来の対話回数の2倍程度
暗号入門7講(2007/05/25)

147

対話回数削減• HVZKIP– Honest Verifier Zero Knowledge Interactive Proof の略– 検証者は正しく乱数を生成するというモデル．

• このモデルだと，対話回数を減らすことができる．
– ただし，健全性，ゼロ知識性の定義を若干変更する必要がある．

• 電子署名などへの拡張も可能– これには，「非対話化」を行う必要がある．
• 理想的なランダム関数を利用する．
• 現実世界では，ハッシュ関数を「理想的なランダム関数」の代替として利用している．

暗号入門7講(2007/05/25)15

例3(p,q,g,y)に対してy=gx mod p となるxを知っている

V(検証者)

P(証明者)(秘密の情報x)a = gr mod p(r:乱数)a0≦b<qをランダムに選ぶbc

c= r+bx mod q
Pが離散対数xを知らない場
合，受理される確率は1/q?

gc≡ayb (mod p)
qを2160程度にすれば健全性はOK

暗号入門7講(2007/05/25)

168健全性について•秘密xを知らないP*は，2通り以上のb,b’に対して，Vが受理するc及びc’を構成できるか?
⇒できない
攻撃方法に依存しない議論

b0 ≠ b1である(a, b0 , c0 ), (a, b1 , c1 )を生成できるとせよ．
検証式g c0 ≡ ay b0 mod p, g c1 ≡ ay b1 mod pが成立するので
g c1 − c0 ≡ y b1 −b0 mod pが成り立つ．つまり，離散対数
x = c1 − c0 b1 − b0 mod qを計算できたことになる．
これはPがxを知らないということに反する．
暗号入門7講(2007/05/25)

17

模倣の方法
• 模倣の手順– まず，bをランダムに選ぶ• 検証者がbをランダムに選ぶモデルであることに注意– 次にcをランダムに選ぶ– 最後に， a=gcy-b mod pとする．

• 模倣により得られた分布は本物の分布と等しいか?
– 完全に一致する

暗号入門7講(2007/05/25)

189

ゼロ知識性について• ゼロ知識性– b,c,aの順に生成した対話は，本物の対話と分布が同じ．
– 本物• rはZqからランダムに選ばれる元であり， 確率は1/q– a=gr mod pはrから一意に定まる．

• bはZqからランダムに選ばれる元であり，確率は1/q• a,bが定まれば，cは一意に定まる．
– 模倣• b,cはZqからランダムに選ばれる元であり，確率は各々1/q• b,cが定まれば，aは一意に定まる．
– 本物，模倣の対話データの集合が一致することも確認できる• 本物の対話データを(a,b,c)とする．
– a=gr mod pとなるr(Zqの元)が存在することに注意．

• 模倣で(r,b)がランダムに選ばれた場合，対話データは(a,b,c)となる

暗号入門7講(2007/05/25)

19

例3の評価
• 完全性
– Pが離散対数xを知っていたら，Vは必ず受理する．

• 健全性– Pが離散対数xを知らない場合，Vが受理する確率は1/q．
• |q|=160の場合，受理する確率は1/2160.

• ゼロ知識性– Honest Verifier に対するゼロ知識性は有する．

暗号入門7講(2007/05/25)2010例4a(非対話化)(p,q,g,y)に対してy=gx mod pとなるxを知っている

V(検証者)

P(証明者)(秘密の情報x)a = gr (r:乱数)

ab=h(p,q,g,y,a)bc= r+bx mod qcbを証明者であるPが計算するため，対話不要(送りつけるだけ)①b=h(p,q,g,y,a)を計算②gc≡ayb (mod p)が成り立つか検証する

h：理想的なランダム関数(現実世界ではhash関数が用いられる)Vが生成すべき乱数を，Pが(理想的な)ランダム関数を用いて生成していることに注意
暗号入門7講(2007/05/25)21

例4b(非対話化・改良版)(p,q,g,y)に対してy=gx mod pとなるxを知っている

V(検証者)

P(証明者)(秘密の情報x)a = gr (r:乱数)aは送る必要なし

b=h(p,q,g,y,a)bc= r+bx mod qcbを証明者であるPが計算するため，対話不要(送りつけるだけ)①a=gc/yb mod pを計算
②b=h(p,q,g,h,a)が成り立
つか検証するaはb,cから計算できるので，送っていないデータ長を小さくできる

Vが生成すべき乱数を，Pが(理想的な)ランダム関数を用いて生成していることに注意
暗号入門7講(2007/05/25)2211

例5(知識の署名)
公開鍵簿

Pの公開鍵:yPはy=gx mod pとなるxを知っている

V(検証者)

P(証明者)(秘密の情報x)a = gr (r:乱数)b=h(M,p,q,g,y,a)(b,c),M

c= r+bx mod q①a=gc/yb mod p②c=h(M,p,q,g,h,a)が成り立つか検証する

乱数生成時，PがメッセージMを(理想的な)ランダム関数へ入力している．
Mの値が変わったら，乱数bも変わることに注意．
Schnorr署名と呼ばれる方法とほぼ同じ
暗号入門7講(2007/05/25)

23

まとめ• ゼロ知識証明についての紹介– ゼロ知識証明の概要– 基本形(多くの対話が必要な方式)– HVZKIP(検証者がHonestなモデルでの方式)– 非対話化(ランダム関数の利用)– 知識の署名

暗号入門7講(2007/05/25)

24

12