プライバシ保護技術
土井洋(情報セキュリティ大学院大学)
今回の入門講義では，匿名性を有する電子署名とはどんな技術か，またその仕組みについて解説したい．このような匿名性を有する電子署名を構成する場合には，ゼロ知識証明が広く利用される．具体例として，離散対数問題の困難性を利用するゼロ知識証明を取り上げ，匿名性を有する電子署名の構成方法をみる．
また，署名者集合のサイズに署名長が依存しない方法の構成方法の概要と，それに深く関係する幾つかの数論問題についても述べたい．

講義中に説明が不足していた部分について追記をしました．
暗号入門7講(2007/06/22)

1

電子署名とプライバシ保護• 電子署名とプライバシ保護– 電子署名を用いると，誰が，どのような文書に対して署名を行ったかを，誰でも確認できる．
– 実世界における署名よりも強力な機能であるが，プライバシ保護の観点からはこの機能を一部制限したい場合もある．
• 電子商取引において，署名者が作成した電子署名を収集された場合は，署名者の意図に反して，商取引の履歴が第三者に知られるといった不都合が生じるかもしれない．

• 目標– 匿名性を有する署名の構築• 署名者が誰であるかを検証できない機能の実現

暗号入門7講(2007/06/22)

21

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

V(検証者)

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

cc= r+bx mod q

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

Pが離散対数xを知らない場
合，受理される確率は1/q

暗号入門7講(2007/06/22)

3

復習(知識の署名)
公開鍵簿

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

V(検証者)

P(証明者)(秘密の情報x)a = gr (r:乱数)b=h(M,p,q,g,y,a)c= r+bx mod q(b,c),M①a=gc/yb mod p②c=h(M,p,q,g,y,a)が成り立つか検証する

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

42

知識の署名(記号について)• 知識の証明:– PK{(α):y≡gα (mod p)}• zero-knowledge Proof of Knowledge of integer α
such that y≡gα (mod p)• 知識の署名– SPK{(α):y≡gα (mod p)}(m)• Singnature of Proof of Knowledge of integer α
such that y≡gα (mod p)
暗号入門7講(2007/06/22)

5

知識の証明の拡張(OR)• (p,q,g1,g2,y1,y2)に対してy1=g1x mod p または y2=g2x modpとなるxの知識の証明– いずれの知識を持っているかを検証者が識別できないことを目標• y1=g1x mod pとなるxの知識• y2=g2x mod pとなるxの知識証明者Pがいずれの知識を持っているか検証者は識別できない• 戦略– 一方の知識(例えば y2=g2x mod pとなるxの知識)を持っているので，こちらのほうは証明を構成可能– 他方の知識(例えば y1=g1x mod pとなるxの知識)は持っていないので証明不可能だが，模倣はできる．
– そこで，「本当の証明」と「模倣」を並べる．
暗号入門7講(2007/06/22)

63

知識の証明の拡張(OR)(p,q,g1,g2,y1,y2)に対してy1=g1x mod p かy2=g2x mod pとなるxの知識

P(証明者)(秘密の情報x (y2=g2x mod p))
a1 = g1c1 y1− b1 mod pa2 = g 2 w mod pa1,a2V(検証者)

0≦b <qをランダムb?

b ≡ b1 + b2 (mod q )b2 = b − b1 mod qb1,b2,c1,c2?

g1c1 ≡ a1 y1b1 (mod p )?

g 2c2 ≡ a2 y2b2 (mod p )c2 = w + xb2 mod q
暗号入門7講(2007/06/22)

7

知識の証明の拡張(OR)の証明• 完全性– 証明者に一方の秘密xの知識があれば，プロトコルどおりに振舞えば，検証は成功する．

• 健全性– 2種類以上の(異なる)b,b’に対して答えることのできる証明者は秘密xを知っている．
• b, b’ に対して，正しく答えることができたとせよ(今回の場合は，(b2,b2’,c2,c2’)をb,b’に対して答えることになる．
• すると，xは次の式で求まる．

x=c2 − c2 'mod qb2 − b2 '• ゼロ知識性(special honest-verifier zero knowledge)– b,(b1,b2,c1,c2),(a1,a2)の順に生成した対話は，本物の対話と分布が同じ．
– 本物でない方の模倣を行うことができる．
暗号入門7講(2007/06/22)

84

1-out-of-n署名
PKI• 署名者集合S

AliceのPK– 署名を生成する可能性がある署名者の集合

BobのPK
CoddのPK• 設計目標1. 公開鍵登録

Alice– 署名者集合Sの誰かが作成した署名であることを検証可能– 署名者集合Sの誰が作成したかは検証不可能

2. 署名生成処理
検証者

Bob

集合S={A, B}

3. A, Bの誰かが署名したことを検証

文書+A, B の誰かが作成した署名

Codd

暗号入門7講(2007/06/22)

9

1-out-of-n証明(知識の証明(n=2))(p,q,g,y1,y2)に対してy1=gx mod p かy2=gx mod pとなるxの知識P(証明者)(秘密の情報x (y2=gx mod p))
a1 = g c1 y1− b1 mod pa2 = g w mod p

a1,a2bV(検証者)

0≦b <qをランダム?

b ≡ b1 + b2 (mod q )b2 = b − b1 mod qc2 = w + xb2 mod q?

b1,b2,c1,c2

暗号入門7講(2007/06/22)

g c1 ≡ a1 y1b1 (mod p )?

g c2 ≡ a2 y2b2 (mod p )スライド7と全く同じ 105

1-out-of-n署名(n=2)• システムパラメタ– p,q,g• 署名者の公開鍵– y1(Alice)– y2(Bob)• 署名– (b1,b2,c1,c2)• 検証

b1 + b2 ≡ h( M , p, q, g , g c1 y1− b1 , g c2 y2 − b2 ) (mod p )?

スライド10の知識の証明を非対話化
暗号入門7講(2007/06/22)

11nを増やすと･･･• n=2の場合を容易に拡張できる• 署名サイズはnに比例– (b1,b2,･･･,bn,c1,c2 , ･･･,cn)• |bi|=|ci|=160– 署名者集合のサイズが大きくなると，非現実的• 改良目標– 署名者集合のサイズ(=n)に比例しない

暗号入門7講(2007/06/22)

126

グループ署名の考え方(‘91～)
管理者
Tom
1. 登録依頼

2. 署名鍵1. U1は管理者Tomに組織Aへの登録を依頼する．
2. Tomは参加OKなら署名鍵SK1を発行する．
3. U1は，署名鍵SK1を使い署名を生成する．
4. 検証者は組織Aの誰かの署名であることがわかる．
5. 不適切な文書への署名者がだれかを，(特殊な管理者Ozzieが)開示できる．

U1

3. 署名生成処理

検証者
4. 組織Aの誰かが署名したことを検証

文書+組織Aの誰かの署名
組織A

暗号入門7講(2007/06/22)

提案当時の方式は署名者集合のサイズに依存
13

目標(informal)• 管理者Tは署名者集合Sに含まれる各署名者(U1,U2,U3,･･･)の登録依頼を受けて，署名鍵SK1,SK2,SK3,･･を生成できる．
• 管理者Tは検証鍵PKGを生成できる• 署名者Uiは署名鍵SKiを使い署名σを生成できる• 検証者は検証鍵PKG，署名σと文書Mから「署名σは署名者集合Sの誰かが署名鍵を用いて生成したこと」を検証できる．
• 署名σを署名者集合Sに含まれていない人が偽造できない．
• 署名σから署名者を特定できない．
• 特殊な管理者Ozzieのみは，署名σから，署名者が誰かを開示できる．
• 署名長は，署名者集合のサイズに依存しない．
暗号入門7講(2007/06/22)

147

構成例
• 署名者は秘密xを選び，y=F(x)を計算し，yを管理者に送る．
• 管理者はyに対してv=S(y)を計算し，vを署名者に送る．
– 検証用の関数Vがあり，(y,v)が正しく作成されたかどうか，すなわちV(y,v)=1かどうかを確認できる．

• SPK{(x,v):V(F(x),v)=1}(m)を署名とする．
関数F, S, V の設計が重要(難しい)
暗号入門7講(2007/06/22)

15

例(CS97)• CRYPTO’97で発表されたグループ署名– 署名長が署名者集合Sのサイズに依存しない– ただし，署名長は短くはない．

• 数論問題– 離散対数問題と素因数分解問題に深く関連• double discrete logarithm of y to the bases g and a• e-th root of the discrete logarithm of y to the base g– RSA署名と離散対数問題に関する知識があれば理解できる．(本講義で取り扱う理由)[CS97] Camenisch, Stadler, “Efficient Group Signature Schemes for LargeGroups”, CRYPTO '97, LNCS 1294, pp. 410-424, 1997.
暗号入門7講(2007/06/22)

168

CS97で用いられた2つの数論問題• double discrete logarithm of y to the bases g and aGiven P, n = pq, g , y, a where n | P − 1, g = n,αfind α s.t. g ( a ) ≡ y (mod P )αSPK {(α ) : g ( a ) ≡ y (mod P)}(m)

これを利用• e-th root of the discrete logarithm of y to the base gGiven P, n = pq, g , y, e where n | P − 1, g = n,find β s.t. g ( β ) ≡ y (mod P )e

SPK {( β ) : g ( β ) ≡ y (mod P )}(m)
e

これを利用

暗号入門7講(2007/06/22)

17

RSA署名(概要)• 公開鍵(n,e)– 素数p,qの積n– gcd(e,φ(n))=1となるe• 秘密鍵(d)– d = e-1 mod φ(n)• 署名σ– メッセージMに対し，σ=Md mod n• 署名検証?

– メッセージと署名の対(M,σ)に対し，M≡σe mod n

暗号入門7講(2007/06/22)

189

管理者によるパラメタ生成• 素数p,qの積nを計算(nはRSA署名で用いるn)• n|P-1となる素数Pを計算– P=kn+1 (k=2,4,6,･･･)• 位数がnとなるZ*Pの元gを計算• グループ公開鍵– (n,P,g)• 管理者の秘密鍵– p,q
暗号入門7講(2007/06/22)

19

各署名者の署名鍵の生成(登録処理)• 署名者の秘密鍵xi• 署名者→管理者
xyi = a i mod n– 署名者はxiの知識の証明を行う．

署名者集合への登録処理• 管理者→署名者

vi = ( yi + 1)1 e mod n• 管理者以外は(nの素因数分解を知らないと)，viを作成できそうにない．
暗号入門7講(2007/06/22)

20

10

グループ署名生成と検証
署名生成( g , z, σ 1 , σ 2 )の生成

( g , z, σ 1 , σ 2 ) whereg = g r mod P (r ∈R Z n* ),z = g y mod Pασ 1 = SPK {(α ) : z ≡ g a (mod P)}(m)  ≡ g β (mod P)}(m)σ 2 = SPK {( β ) : zge

署名検証
知識の署名
V1,V2の検証

σ 1 , σ 2よりβ =(aα + 1)1 e mod nの知識のα  = g a +1 = g β だから).
証明となる( zge

暗号入門7講(2007/06/22)

21

署名者の開示• yiを所持している管理者は，全署名者のyiに対して以下を計算

z = g yi mod P• 計算で得た z が署名 ( g , z , σ 1 , σ 2 )の第2成分と一致するかチェック

暗号入門7講(2007/06/22)2211

αPK {(α ) : z = g a }P(証明者)(秘密の情報x)V(検証者)(a1 ," , al )riai = g a (i = 1," , l )(b1 ," , bl ) : random(b1 ," , bl )ci = ri (bi = 0)ci = ri − x(bi = 1)

ai = g a (bi = 0)ci(c1 ," cl )ai = z a (bi = 1)ci注1)|ri|>|x|でなくてはならない．
注2)統計的ゼロ知識証明になる．
暗号入門7講(2007/06/22)23

  = g }PK {( β ) : zgβeP(証明者)(秘密の情報x)V(検証者)eai = g ri (i = 1," , l )(a1 ," , al )(b1 ," , bl )ci = ri (bi = 0)ci = ri x mod n(bi = 1)

(c1 ," cl )暗号入門7講(2007/06/22)(b1 ," , bl ) : randomai = g ci (bi = 0)e  )ci (bi = 1)
ai = ( zge24

12

目標を達成できたか?(Informal)• 署名σを署名者集合Sに含まれていない人が偽造できない．
– 署名者集合Sへの登録処理を行わない限り，viを得ることはできない．
– 署名にはviの知識の署名(σ1，σ2)が含まれている(つまり，viを得た人のみが署名生成可能)．

vi = ( yi + 1)1 e mod n• 署名σから署名者を特定できない．
– viの知識の署名を作成しているのだが，(ゼロ知識証明なので)登録処理を行ったどのviを利用しているかという情報は漏れない．

• 特殊な管理者Ozzieのみは，署名σから，署名者が誰かを開示できる．
– 署名者集合のサイズに比例するが，開示は可能．

• 署名長，公開鍵長は，署名者集合のサイズに依存しない．

暗号入門7講(2007/06/22)

25

まとめ• 匿名性を有する署名の構成例を2つ示した．
– 1-out-of-n署名• 知識の署名の拡張(OR)により実現• 署名サイズが，署名者集合Sのサイズに比例– グループ署名(CS97)• g の指数部が(管理者からもらった)RSA署名• g の指数部がRSA署名であることの知識の署名を構成– (管理者からもらった)RSA署名は，検証者には見えない．

• 署名サイズが，署名者集合Sのサイズに依存しない

暗号入門7講(2007/06/22)

2613