ダウンロード - 松嶋研究室

頑健性をもった
頑健性をもったMix
をもったMixMix-net型電子投票
net型電子投票における
型電子投票における計算量削減
における計算量削減
1G01H066-5
下村 英明
指
導 松嶋 敏泰教授
1. 序論
3.1.3. MixMix-netの
netのランダム化
ランダム化と置換
サーバ Si は掲示板から Ei−1 を受け取り，乱数
rj(i )∈R Z q ，ランダム置換 π i から暗号文 (G (j i ) , M (j i ) ) を
求める．
r(i)
r(i)
(G (ji ) , M (j i ) ) = (Gπ(ii −(1j)) ⋅ g π i ( j ) , M π(ii −(1j)) ⋅ y π i ( j ) ). (2)
Ei = (G (ji ) , M (ji ) j= 1, L, N ) を掲示板に公開する．
S2
S1
E0
E2
E1
Sm
・・・
・・・
Em −1
Em
開票
投票
電子投票とは選挙における投票・集計を電子化し，
ネットワーク上で投票を実現するための技術である．
電子投票にはいくつか事例があり，一つに2000年3
月アリゾナ州民主党大統領選挙予備選がある．
電子投票の手法として，いくつか手法が考案され
ている．実用面においてもっとも有力視されている
Mix-netでは，複数のサーバが連携して投票を暗号
処理しながらシャッフルすることで，最初の投票内容
とシャッフルされた投票内容の対応付けを不可能に
する．これによりシャッフルされた投票内容を復号し
ても投票の匿名性を保証できる．
従来，佐古らはサーバが行う操作について，不正
行為の有無を第三者が検証できる（全体検証可能）
Mix-netプロトコルを提案している[1]．さらに古川らは
佐古らの検証プロトコルに非対話型ゼロ知識証明を
使い，全体検証可能で計算量を削減したプロトコル
を提案している[2]．一方，阿部は鍵生成を工夫する
ことで，全体検証可能で，閾値以下の不正サーバが
存在しても投票をやり直す必要が無い（頑健性）投票
プロトコルを提案している[3]．しかし実装にあたり検
証にかかる計算量の多さが問題になっている．
古川らの全体検証プロトコルを阿部のプロトコルに
そのまま適用するのは投票プロトコルの違いから不
可能である．本研究ではこの課題を解決し，頑健性
を持ち且つ計算量を削減したMix-netのプロトコルを
提案し，計算量を比較する．
2. 準備
2.1. ゼロ知識証明
ゼロ知識証明
証明者と検証者が対話をしながら「証明者が秘密
情報を全く漏らさず，その情報を知っていることを検
証者に納得させる方法」である．証明の手法として大
別すると，対話型と非対話型の2つがある．対話とは
証明者と検証者が情報を送りあうことである．
対話型ゼロ知識証明では対話を繰り返すことによ
り証明を行っている．非対話型ゼロ知識証明では，
対話を行わない代わりに証明者・検証者で共通乱数
を用いることにより，証明を行っている．
2.2. ハッシュ関数
ハッシュ関数
文字の羅列から一定長のデータに要約するため
の関数である．一方向関数であるため，生成データ
から原文を推定することは不可能である．
2.3. 電子投票で
電子投票で要求される
要求される条件
される条件
不正投票防止（有権者のみが1回のみ投票可能），
匿名性（投票者と投票内容が関連づけられない），検
証可能性（不正・水増しを検出），頑健性（不正が存
在しても正しい結果を出力可能）がある．
3. 従来法
従来法
3.1. 従来法[3]
従来法
阿部のプロトコルは鍵生成を工夫し，従来サーバ
で行っていた復号を最後に一括に行うことで，頑健
性を持たせたMix-netプロトコルである．全体検証に
対話型ゼロ知識証明を利用している．
全サーバ数は m = 2t + 1 とし，不正サーバの数は t
以下とする．公開掲示板に一度公開された情報の削
除や書き換えは不可能とする． p, q を素数， Z q を0
以上 q 未満の整数集合, Z q* を Z q かつ q と互いに素
な整数集合とする． b ∈R B は b が集合 B からランダム
に選択された要素，サーバ S i (i ∈{1,L, m}) ，投票者
j∈{1,L, N} とする． π i , π~i は N 個から N 個にランダム
に置換する関数， H は入力に対して Z q の出力するハ
ッシュ関数とする．プロトコルの計算は mod p で行う．
3.1.1. 鍵生成
正当な第三者は素数 p, q を生成，乗法群 Z q* での
位数 q の部分群を Gq とし， g∈Gq とする．秘密分散
共有法を用いた鍵生成アルゴリズムにより，秘密鍵 x
を {x1 ,L, xm } に分散し，各サーバ Si に分配する．
3.1.2. 投票者の
投票者の投票
投票者 j は投票 m j ∈ Gq と乱数 rj( 0 ) ∈ Z q から以下
のElGamal暗号文 E 0 = (G (j 0 ) , M (j 0 ) | j = 1,L, N ) を作成
し，掲示板に公開する．
r(0)
r(0)
(1)
(G (j 0 ) , M (j 0 ) ) = ( g j , m j y j ) .
・・・
シャッフル
シャッフル
図1: Mix-netの流れ
シャッフル
3.1.4. 検証プロトコル
検証プロトコル
誤り確率を ε としたとき， σ = − log 2 ε として，以下
で与えられるA-1からA-4までを σ 回繰り返す．
A-1
Si は3.3節とは別の乱数 ~
rj(i )∈R Z q ，ランダム
~
~
置換 π~i から暗号文 (G (j i ) , M (j i ) ) を作成する．
~
~ ~
~
r~ ( i )
r (i )
~
(G (j i ) , M (j i ) ) = (Gπ(ii −(1j)) ⋅ g π i ( j ) , M π(ii −(1j)) ⋅ y π i ( j ) ). (3)
~ ~ ~
Ei = (G(ji) , M (ji ) j= 1,L, N ) を掲示板に公開する．
~
ただし， E0 = E0 とする．
N
A-2 検証者は c ∈R {0,1} を掲示板に公開する．
A-3 c = 0 の場合， Si は π~i , ~
rj( i ) を公開する．
c = 1 の場合， Si は
−1
(4)
ϕi = π i ⋅ ϕi−1⋅ π i , w(ji ) =w(ji−1) + ~
rj(i ) −rj( i ) mod q,
を掲示板に公開する．ただし， w(j0 ) = 0 とする．
A-4 検証者は次式が成立することを確認する．
c = 0 の場合
~
~
R
R
(5)
G (j m ) G∏~( 0)( j ) =g j , M (j m ) M ∏~( 0)( j ) = y j .
c = 1 の場合，
i
G (j m ) Gϕ( mm () j ) =g
i
w(j m )
, M (j m ) M ϕ( mm () j ) = y
w(j m )
.
(6)
~
m
ただし， R j = ∏ ~
r ~(i ) ~ , ∏ = π~m Lπ~1 とする．（式
i =1 (π i Lπ 1 )( j )
(5)，(6)）が成立するとき，不正がないといえる．
3.1.5. 復号
ランダム化と置換で不正がなかった場合，秘密分
散共有法を用いることで t + 1 以上の Si が xi を持ち寄
ることで秘密鍵 x を復元することが出来る． x と E m か
ら以下を計算し，投票を復号し集計する．
x
(7)
M (j m ) (G (j m ) ) = m j .
3.2. 従来法[2]
従来法
古川らのプロトコルは，従来法と同様各サーバが
復号処理をするので，不正サーバが存在すると投票
のやり直しが必要になるため，頑健性がない．全体
検証プロトコルにハッシュ関数を利用した非対話型
ゼロ知識証明を利用している．非対話型ゼロ知識証
明では，証明者と検証者に対話の繰り返しが必要で
ない．このため計算量の削減が可能になる．
4. 提案法
4.1. 提案法の
提案法の概要
提案法では阿部の投票プロトコルに非対話型ゼロ
知識証明を組み込む．しかし投票プロトコルの違い
から第三者が検証に利用できる公開情報が違い，そ
のまま古川らのプロトコルを使用出来ない．
古川らの投票プロトコルはサーバの処理で，暗号
とシャッフルを行ってから復号しているので，復号前
後での入出力の対応関係が分かる．しかし阿部の投
票プロトコルでは暗号とシャッフルのみを行っている
ので， Si の入出力の対応関係が分からない．そこで
従来，投票個々について行っていた割り算を，式(11)
のように投票全体で行うように設計した．式(11)から得
(i )
(i )
られる r j を含む情報を使って検証するために， r j
が隠蔽された r ' を検証者に送るように設計した．
4.2. 提案プロトコル
提案プロトコル
検証者はそれぞれの Si について，A’-1からA’-2ま
でをそれぞれ1回行う．
A’-1 Si は3.3節とは別の乱数 ~
rj(i )∈R Z q から次式を
計算する．
c = H ( p, q, g , y, G (ji ) , M (ji ) ),
(8)
N
N
N
∑ rj
∑ rj
r '=c∑ j =1 ~
rj(i )+∑ j =1 rj(i ) , g '=g j=1 , y'=y j=1 . (9)
r ' , g ' , y ' を検証者に送る．
A’-2 検証者は次式が成立することを確認する．
(10)
c = H ( p, q, g , y, G (j i ) , M (ji ) ),
∏ (G )
=
∏ (G )
N
g
r'
j =1
N
j =1
(i ) c
j
( i −1) c
j
(i )
∏ (M )
=
∏ (M )
N
⋅g ' , y
r'
j =1
N
j =1
(i ) c
j
( i −1) c
j
(i )
⋅y '. (11)
掲示板に公開されている情報 Ei −1 , Ei を用いて各
サーバ Si について検証を行っているので，不正サー
バを特定することが出来る．式(11)が全てのサーバに
おいて成立したとき，3.1.5節の復号を行う．
5. 評価
阿部の手法と提案プロトコルで，同じ安全性の元
で検証にかかる指数計算（式(3),(5),(6),(9),(10)）の回
数の比較を行う.指数計算の回数をまとめたものが表
1である． m ≤ σ 2 の時，提案法は有効である．
表 1: 指数計算の回数の比較
第3者側の計算量
各サーバ側の計算量
提案法
阿部[1]
2q
2qNσ
4mqN
2qNσ
6. 考察
阿部の検証プロトコルで不正サーバ検出のために
Si それぞれに検証を行うと， m 倍の計算量が必要に
なる．提案法では，新たにハッシュ関数の汎用一方
向性の仮定が必要になるが，非対話型ゼロ知識証明
の手法を用いることで，従来 σ 回繰り返しが必要だっ
た検証が1回で検証可能になり，計算量を削減するこ
とができた．検証プロトコルの安全性のうち健全性に
関して，阿部は (1 2)σ で与えられるが，提案法では
1 q で与えられる．阿部は安全性を保証で σ = 80 を
想定しているので，サーバ数 m ≤ 40 であれば，提案
法は有用である．
7. 結論
本研究では頑健性を持つMix-netについて，検証
における計算量を削減したプロトコルを提案し，評価
を行った．今後の課題として，鍵生成で正当な第三
者機関を仮定しないプロトコルが求められる．
参考文献
[1] Kazue Sako, and Joe Kilian, "Receipt-Free Mix-Type
Voting Scheme -A practical solution to the implementation of a
voting booth-", In Advances in Cryptology -- EUROCRYPT
'95, LNCS vol.921, pp.393-403, 1995.
[2] J.Furukawa, H.Miyabe, K.Mori, S.Obana, K.Sako, "An
implementation of a universally verifiable electronic voting
scheme based on shuffling", IFCA/Spring-Verlog 2003, LNCS
vol.2357, pp.16-30, 2003.
[3] M.Abe, "Universally Verifiable Mix-Net with Verification
Work Independent of Number of Mix-Server", IEICE Trans.
Fundamentals,vol.E83-A, no.7, pp.1431-1440, July, 2000.