JP3689292B2 - Anonymous electronic voting apparatus and anonymous electronic voting processing method - Google Patents

Description

【００１５】
として暗号文Ｍを得る。以下では、この暗号化手順をＥ_i （ｍ，ｒ）と書く。
各投票者は、送信すべきメッセージ・署名対ＭをＥ₁ （Ｅ₂ （…Ｅ_L （Ｍ，ｒ_L ），…），ｒ₂ ），ｒ₁ ）のように、各暗号化鍵を用いて多重に暗号化し、Ｕ₁ へ送付する。
【００１６】
Ｕ₁ は、複数の投票者から暗号化された入力文が集まった後、これをＸ₁ で復号し、各入力文について、Ｅ₂ （…Ｅ_L （Ｍ，ｒ_ｌ ），…）ｒ₂ ）およびｒ₁ を得る。Ｕ₁ はそれぞれの入力文から得られたＥ₂ （…Ｅ_L （Ｍ，ｒ_ｌ ），…）ｒ₂ ）の順序をランダムに置換し、Ｕ₂ へ送付する。
【００１７】
この際、各メッセージについてのｒ₁ を秘密とすることで、Ｕ₂ へ送付された各Ｅ₂ （…Ｅ_L （Ｍ，ｒ_ｌ ），…）ｒ₂ ）がＵ₁ への入力のどのメッセージに関する復号結果であるのかを判別できないようにすることができる。
【００１８】
以下、Ｕ₂ ，…，Ｕ_L も同様の処理を繰り返す。最後にＵ_L は、復号されてランダムに置換されたメッセージ・署名対のリストを公開する。少なくとも一つのサーバが乱数ｒ_i および置換の順序を秘密に保つことにより、各利用者がＵ₁ へ入力した入力暗号文と、Ｕ_L が出力した各メッセージ・署名対との関連は隠匿され、匿名通信路として機能する。
【００１９】
【発明が解決しようとする課題】
上記従来の方法のように、物理的な匿名通信路をＭＩＸ−ＮＥＴで置き換えた場合、Ｍｉｘサーバの故障によってあるいは投票者とＭｉｘサーバとの結託による意図的な妨害によって、不正な結果が出力される可能性がある。
【００２０】
例えば、投票者の一人が、暗号化されたメッセージ・署名対Ｅ₁ （Ｅ₂ （…Ｅ_L （Ｍ，ｒ_L ），…），ｒ₂ ），ｒ₁ ）の代わりに、検証に失敗するようなランダムな値Ｒを暗号化した値Ｅ₁ （Ｅ₂ （…Ｅ_L （Ｒ，ｒ_L ），…），ｒ₂ ），ｒ₁ ）を送信し、正規のメッセージ・署名対Ｍを結託した相手のＭｉｘサーバＵ_L へ秘密裏に送付したと想定する。
【００２１】
サーバＵ_L は、すべての処理を終えた後、結果を出力する直前に、出力すべきメッセージ・署名対のリストのうちの一つのメッセージ・署名対を予め結託した投票者から渡されたメッセージ・署名対Ｍですり替えて出力する。このリストを検証することによって、Ｒは棄却されるが、置き換えられてしまった正しいメッセージ・署名対はリストに含まれないために集計対象とならず、本来の集計結果と異なる、不正な結果が現れることになってしまう。
【００２２】
本発明は、物理的な匿名通信路を用いない電子投票システムにおいて、上記のような票のすり替えによる集計上の不正を防止するようにすることを目的としている。
【００２３】
【課題を解決するための手段】
まず、署名者は、ブラインド署名の代わりに、抹消可能ブラインド署名（Fair
Blind Signature）を用いて署名を発行する。
【００２４】
抹消可能ブラインド署名は、ブラインド署名と同様に、署名者が発行したメッセージ・署名対ｍ′，σ′を投票者がｍ，σへ変換する手段を備える署名方法であり、署名者にｍ，σを知られることなく投票者が署名を入手する手段を実現することができる。抹消可能ブラインド署名は、これに加えて、ある監視情報τを保持する監視者がｍ′，σ′からｍ，σを特定する情報を引き出す手段を持つ署名方法である。
【００２５】
集計時に、不正なメッセージ・署名対（ｍ，σ）を発見した場合、ＭｉｘサーバＵ_L は、その不正な出力（ｍ，σ）に対応する入力を公開し、その出力が正しい処理によって得られたものであることを証明する。
【００２６】
処理が正しいことが証明されたならば、次のサーバＵ_L-1 は、Ｕ_L が公開した入力値が出力値となるＵ_L-1 の入力を公開し、その入出力関係について、処理の正しさを証明する。この手順を順次最初のサーバＵ₁ まで繰り返す。途中、証明に失敗するようなＭｉｘサーバが存在する場合、そのサーバを不正者と見なす。
【００２７】
すべてのサーバが証明に成功した場合、Ｕ₁ が公開した入力を送付した投票者を不正投票者と見なす。
【００２８】
不正投票者が発見された場合、監視者は、その不正投票者に対して署名者が発行した抹消可能ブラインド署名ｍ′，σ′および、監視情報τを用いて、本来のメッセージ・署名対ｍ，σを特定する情報Ｗを得る。このＷを用いて、集計時に得られたメッセージ・署名対のリスト中にｍ，σが含まれているかどうかを確認する。ｍ，σが含まれていた場合、前述の手段により、逐次、各サーバがその出力に対応する入力を公開し、処理の正しさを証明する。以上の手段を繰り返すことにより、すべての不正な投票者による投票を排除し、かつ、不正なＭｉｘサーバを特定する事ができる。
【００２９】
【発明の実施の形態】
実施例について説明する。図１は本実施例の電子投票装置のブロック図である。本実施例の電子投票装置は、ｎ個の投票装置１−ｉ、署名装置２、監視装置３、ｋ個のＭｉｘ装置４−ｉ、検証装置５および公開掲示板６を具備する。各装置と公開掲示板とは相互認証が可能な認証通信路７で接続される。以下の説明で、各装置が相互に情報を送受信する場合には、全て公開掲示板を介して行うものとする。
【００３０】
以下、各装置について説明する。本実施例では、抹消可能ブラインド署名方法として、J.Camenisch, "Group Signature Schemes and Payment Systems Based on the Discrete Logarithm Problem", ETH Series in Information Security and cryptography,Volumn 2,pp.124-132,Hartung-Gorre Verlag で提案されているSchnorr 署名に基づく方法を用いる。まず、この抹消可能ブラインド署名方法について説明する。
【００３１】
ｐ，ｑを大きな素数とし、ｑは（ｐ−１）を割り切るものとする。ｇ，ｇ₁ ，ｇ₂ をＺ^* _p における位数ｑの元とする。Ｈ（・）は一方向性ハッシュ関数であり、二項演算子ａ‖ｂはａとｂとの二進表現を結合した値を表す。
【００３２】
乱数τに対してｙ_T を
【数３１】

を満たす値とする。τは署名抹消に必要な秘密情報であり、監視者が秘密に保持する。ｙ_T は公開する。
【００３３】
同様に、乱数ｘに対して、ｙをｙ＝ｇ^x mod p を満たす値とする。ｘは署名鍵であり、署名者が秘密に保持する。ｙは署名検証鍵として公開する。
【００３４】
以下の説明は、署名要求者が文書ｍに対する署名を署名者から入手する際の要求者と署名者との処理手順である。
手順１：要求者は、乱数ａをＺ^* _q から選び、
【００３５】
【数２】

【００３６】
を計算する。次に、この計算が正しく行われたこと（即ち、
【００３７】
【数３】

【００３８】
が成り立つこと）を証明する証明書（ｃ₁ ，ｓ₁ ）を以下の手順で作成する。
（ａ）乱数ｗ₁ ∈Ｚ^* _q を選び、
【００３９】
【数４】

【００４０】
を計算する。
（ｂ）ｓ₁ ：＝ｗ₁ ＋ｃ₁ ａ ^-1 mod p を計算する。
上記計算結果（ｈ_w ，ｄ，ｃ₁ ，ｓ₁ ）を署名者へ送付する。
手順２：署名者は以下のステップを実行する。
（ａ）
【００４１】
【数５】

【００４２】
が成り立つことを確認する。成り立たなければ処理を停止する。
（ｂ）ｚ_w ：＝ｈ_w ^x mod p を計算する。
（ｃ）乱数ｗ₂ ∈Ｚ_q を選び、
【００４３】
【数６】

【００４４】
を計算する。
（ｄ）（ｚ_w ，ｔ'_g ，ｔ'_h ）を要求者へ送付する。
手順３：要求者は乱数γ，δをＺ_q より選び、
【００４５】
【数７】

【００４６】
を計算し、ｃ'₂ を署名者へ送付する。
手順４：署名者はｓ'₂ ：＝ｗ₂ −ｃ'₂ ｘmod q を計算し、要求者へ送付する。
【００４７】
手順５：要求者はｓ₂ ：＝ｓ'₂ ＋γmod q を計算する。更に、ｈ_p ＝ｈ_W ^a mod p であることの証明書（ｃ₃ ，ｓ₃ ）を以下の手順で生成する。
（ａ）乱数ｗ₃ ∈Ｚ_q を生成する。
（ｂ）
【００４８】
【数８】

【００４９】
を計算する。
（ｃ）ｓ₃ ：＝ｗ₃ −ｃ₃ ａmod q を計算する。
【００５０】
最後に、（ｍ，ｈ_p ，ｚ_p ，ｃ₂ ，ｓ₂ ，ｃ₃ ，ｓ₃ ）を文書・署名対として保存する。
上記手順において、
【００５１】
【数９】

【００５２】
であり、
【００５３】
【数１０】

【００５４】
であり、更に、
【００５５】
【数１１】

【００５６】
であるので、発行された（ｍ，ｈ_p ，ｚ_p ，ｃ₂ ，ｓ₂ ，ｓ₃ ，ｃ₃ ）は、
【００５７】
【数１２】

【００５８】
が成り立つことを確認することによってその正しさを検証することができる。
発行した署名を抹消する場合には、秘密情報τを持つ監視者が、
【００５９】
【数１３】

【００６０】
を計算して公開する。この値は、
【００６１】
【数１４】

【００６２】
となるので、この値ｈ_p を含む署名を無効と見なす。また、監視者の計算が正しいことを証明する証明書（ｓ₄ ，ｃ₄ ）を以下のように計算する。
計算１：乱数ｗ₄ ∈Ｚ_q を生成する。
計算２：
【００６３】
【数１５】

【００６４】
を計算する。
計算３：ｓ₄ ：＝ｗ₄ −ｃ₄ τmod q を計算する。
この証明書は、
【００６５】
【数１６】

【００６６】
が成り立つ場合に、監視者の処理が正しいことを保証する。
本実施例では、ＭＩＸ−ＮＥＴへ入力する暗号文を作成する方法として従来法の説明中で記述したＲＳＡ暗号に基づく方法を用いる。以下の説明で、｜ａ｜はａのビット数を表す。ｉ＝１，…，ｎに対して、（ｅ_i ，Ｎ_i ）、（ｄ_i ，Ｎ_i ）をそれぞれＲＳＡ暗号の公開鍵、秘密鍵とする。ただし、｜Ｎ_i ｜＞｜Ｎ_i+1 ｜とする。
【００６７】
図２を参照し、署名装置について説明する。署名装置２は、メモリ２１、追跡情報埋込検証器２２、コミットメント演算器２３、署名演算器２４および、これらを制御する制御部２５を具備する。メモリ２１には、ｇ，ｇ₁ ，ｇ₂ ，ｐ，ｑ，ｙ，ｙ_T およびｘが格納されている。制御部２５は以下の各ステップを実行するよう各機器を制御する。
【００６８】
・（追跡情報埋込検証およびコミットステップ）Ａ：
投票装置１−ｉから受信した入力（ｈ_w ，ｄ，ｃ₁ ，ｓ₁ ）に対して、追跡情報埋込検証器２２へ（ｈ_w ，ｄ，ｃ₁ ，ｓ₁ ）およびｇ₁ ，ｇ₂ ，ｐ，ｑ，ｙ_T を入力する。駆動された追跡情報埋込検証器２２は
【００６９】
【数１７】

【００７０】
を計算し、その結果がｃ₁ と等しければＯＫを出力し、等しくなければＮＧを出力する。ＮＧが出力された場合、制御部２５は処理を停止する。ＯＫが出力された場合、コミットメント演算器２３へｈ_w ，ｇ，ｐ，ｑを入力する。駆動されたコミットメント演算器２３は、入力ｈ_w ，ｇ，ｐ，ｑに対し、１以上ｑ未満の整数乱数ｗ₂ を生成し、ｚ_w ，ｔ'_g ，ｔ'_h を
【００７１】
【数１８】

【００７２】
のように計算して出力する。
・（署名生成ステップ）Ｂ：
投票装置１−ｉから受信した入力ｃ'₂ に対して、署名演算器２４へｃ'₂ およびｗ₂ ，ｘ，ｑを入力する。署名演算器２４は、ｓ'₂ ：＝ｗ₂ −ｃ'₂ ｘmod q を計算して出力する。
【００７３】
制御部２５は、それぞれのステップで得られた出力（ｚ_w ，ｔ'_g ，ｔ'_h ）およびｓ'₂ を、順次、投票装置１−ｉへ送信する。
【００７４】
図３を参照し、投票装置について説明する。投票装置１−ｉは、メモリ１１、追跡情報埋込器１２、追跡情報埋込証明器１３、攪乱器１４、攪乱修正器１５、暗号化器１６および、これらを制御する制御部１７を具備する。メモリ１１には、ｇ，ｇ₁ ，ｇ₂ ，ｐ，ｑ，ｙ，ｙ_T が格納されている。制御部１７は以下の各ステップを実行するよう各機器を制御する。
【００７５】
・（追跡情報埋込および証明ステップ）Ｃ：
追跡情報埋込器１２へｇ₁ ，ｇ₂ ，ｐ，ｑ，ｙ_T を入力する。追跡情報埋込器は、乱数ａ∈Ｚ^* _q を生成し、
【００７６】
【数１９】

【００７７】
を計算し、ｈ_w ，ｄを出力する。ｇ₁ ，ｙ_T ，ｐ，ｑおよび、追跡情報埋込器１２の出力ｈ_w ，ｄ，ａを追跡情報埋込証明器１３へ入力する。追跡情報埋込証明器１３は乱数ｗ₁ ∈Ｚ^* _q を選び、
【００７８】
【数２０】

【００７９】
およびｓ₁ ：＝ｗ₁ ＋ｃ₁ ａmod p を計算し、ｃ₁ ，ｓ₁ を出力する。制御部１７は、（ｈ_w ，ｄ，ｃ₁ ，ｓ₁ ）を署名装置２へ送信する。
【００８０】
・（ブラインド処理ステップ）Ｄ：
投票すべきメッセージｍおよび、署名装置２から受信した（ｚ_w ，ｔ'_g ，ｔ'_h ）の入力に対し、ｍ，ｚ_w ，ｔ'_g ，ｔ'_h およびｐ，ｑ，ｇを攪乱器１４へ入力する。攪乱器１４は乱数γ，δをＺ_q より選び、
【００８１】
【数２１】

【００８２】
を計算し、γ，ｈ_p ，ｚ_p ，ｃ₂ ，ｃ'₂ を出力する。制御部１７は、ｃ'₂ を署名装置２へ送信する。
【００８３】
・（暗号投票文作成ステップ）Ｅ：
署名装置２から受信したｓ'₂ の入力に対し、ｓ'₂ および、ｑ，γを攪乱修正器１５へ入力する。駆動された攪乱修正器１５は、ｓ₂ ：＝ｓ'₂ ＋γmod q を計算する。更に、以下の手順を実行して、ｓ₃ ，ｃ₃ を得、ｓ₂ ，ｓ₃ ，ｃ₃ を出力する。
【００８４】
手順１１：乱数ｗ₃ ∈Ｚ_q を生成する。
手順１２：
【００８５】
【数２２】

【００８６】
を計算する。
手順１３：ｓ₃ ：＝ｗ₃ −ｃ₃ ａmod q を計算する。
【００８７】
次に、ｓ₂ ，ｓ₃ ，ｃ₃ ，ｍ，ｈ_p ，ｚ_p ，ｃ₂ を暗号化器１６へ入力する。簡単のため、これらの入力全体をＭと表すことにする。さらに、Ｙ₁ ，…，Ｙ_n を入力して暗号化器１６を駆動する。駆動された暗号化器１６は、乱数Ｋ₁ ，…，Ｋ_n を生成し、
【００８８】
【数２３】

【００８９】
を計算し、さらに、Ｅ₀ ：＝Ｅｎｃ（…Ｅｎｃ（Ｅｎｃ（Ｍ，Ｋ_n ），Ｋ_n-1 ）…，Ｋ₁ ）を計算し、Ｒ₀ ，Ｅ₀ を出力する。ここで、Ｅｎｃ（α，β）は暗号文αを秘密鍵βで暗号化する演算を意味する。制御部１７は、Ｒ₀ ，Ｅ₀ を公開掲示板へ送信する。
【００９０】
暗号化演算ＥｎｃはＩＤＥＡやＲＣ６など予め定めたどのような暗号アルゴリズムを用いても良い。更に、各暗号化の演算は異なるアルゴリズムを使用しても良い。各Ｋ_i のビット数は使用する暗号アルゴリズムに適合するように定める。各公開鍵Ｎ_i も、｜Ｎ_i ｜と｜Ｎ_i-1 ｜の差が｜Ｋ_i ｜以上となるよう定めておく。
【００９１】
以下の説明では、各投票装置１−ｉが公開掲示板６へ送信した（Ｒ₀ ，Ｅ₀ ）からなるリストをＬ₀ と記述する。
【００９２】
図４を参照し、Ｍｉｘ装置について説明する。Ｍｉｘ装置４−ｉは、メモリ４１、復号器４２、置換装置４３、対応証明器４４および、これらを制御する制御部４５を具備する。Ｍｉｘ装置４−ｉのメモリ４１には、Ｘ_i ：＝（ｄ_i ，Ｎ_i ）および、Ｙ₁ ，…，Ｙ_k が格納されている。制御部４５は以下の各ステップを実行するよう各機器を制御する。
【００９３】
・（Ｍｉｘ処理ステップ）Ｆ：
入力Ｌ_i-1 に対し、Ｘ_i およびＬ_i-1 に含まれる各（Ｒ_i-1 ，Ｅ_i-1 ）を順次復号器４２へ入力する。復号器４２は、
【００９４】
【数２４】

【００９５】
を計算し、演算結果の下位側から予め定められたビット数分の値をＫ_i とし、残りの部分をＲ_i とする。Ｋ_i を用いてＥ_i ：＝Ｄｅｃ（Ｅ_i-1 ，Ｋ_i ）を計算する。ここで、Ｄｅｃは復号演算であり、投票装置１−ｉが利用する暗号演算に対応するアルゴリズムを表す。復号器４２は、（Ｒ_i ，Ｅ_i ）を出力する。制御部４５は、復号器４２から順次出力される（Ｒ_i ，Ｅ_i ）をメモリ４１へ格納する。Ｌ_i-1 のすべてのエントリに対して復号が終了した後、置換装置４３を駆動し、すべての（Ｒ_i ，Ｅ_i ）を順番に並べたリストを置換装置４３へ入力する。置換装置４３は、ランダムな置換πを生成し、πに従って入力されたリストの各エントリの順序を入れ換えてできるリストをＬ_i として出力する。例えば、ｎ＝３のとき、ランダムに生成された置換をπ＝｛３，１，２｝とすると、リストの１番目にある（Ｒ_i ，Ｅ_i ）を３番目に、２番目にある（Ｒ_i ，Ｅ_i ）を１番目に、３番目にある（Ｒ_i ，Ｅ_i ）を２番目においてできるリストをＬ_i とする。置換装置４３はπも出力する。制御部４５はπをメモリ４１へ格納し、Ｌ_i を公開掲示板６へ送信する。
【００９６】
・（対応証明ステップ）Ｇ：
１≦Ｊ_i ≦ｎなる整数値Ｊ_i （以下、この変数を追跡インデックスと呼ぶ）とＬ_i-1 の入力に対し、Ｊ_i ，Ｌ_i-1 およびπ，Ｘ_i を対応証明器４４へ入力する。対応証明器４４は、π中にＪ_i が現れる場所を検索し、Ｊ_i がＪ_i-1 番目に現れたら、リストＬ_i-1 のＪ_i-1 番目のエントリ（Ｒ_i-1 ，Ｅ_i-1 ）を得、復号器４２の動作と同様に、
【００９７】
【数２５】

【００９８】
を計算し、演算結果の下位側から予め定められたビット数分の値をＫ_i とし、Ｊ_i-1 ，Ｋ_i を出力する。
【００９９】
最後尾（ｉ＝ｋ）のＭｉｘ装置４−ｉが出力するリストＬ_k の各エントリ（Ｒ_k ，Ｅ_k ）は、すべて正常に処理された場合、Ｒ_k には何も含まれず、Ｅ_k はメッセージ・署名対Ｍ＝｛ｓ₂ ，ｓ₃ ，ｃ₃ ，ｍ，ｈ_p ，ｚ_p ，ｃ₂ ｝となる。以下では、Ｌ_k をＭのリストとして説明する。
【０１００】
図５は監視装置のブロック図である。監視装置３は、制御部３１、メモリ３２、追跡情報演算器３３、追跡情報証明器３４を具備する。監視装置３のメモリ３２には、ｇ，ｇ₁ ，ｇ₂ ，ｐ，ｑ，τ，ｙ_T が格納されている。制御部３１は以下に説明する
・（追跡情報生成ステップ）Ｈ
を実行するよう各機器を制御する。
【０１０１】
処理１：入力ｄに対して、ｄ，ｇ₁ ，τ，ｑ，ｐを追跡情報演算器３３へ入力する。
処理２：駆動された追跡情報演算器３３は、
【０１０２】
【数２６】

【０１０３】
を計算し、出力する。
処理３：次に、追跡情報証明器３４へｈ_p ，ｄ，ｇ₁ ，ｇ₂ ，ｐ，ｑ，τを入力する。
【０１０４】
処理４：追跡情報証明器３４は、以下の手順で（ｃ₄ ，ｓ₄ ）を計算する。
（ａ）乱数ｗ₄ ∈Ｚ_q を生成する。
（ｂ）
【０１０５】
【数２７】

【０１０６】
を計算する。
（ｃ）ｓ₄ ：＝ｗ₄ −ｃ₄ τmod q を計算する。
処理５：制御部３１はｈ_p およびｃ₄ ，ｓ₄ を出力する。
【０１０７】
図６を参照し、検証装置について説明する。検証装置５は、メモリ５１、署名検証器５２、対応検証器５３、追跡情報検証器５４、署名抹消器５５および、これらを制御する制御部５６を具備する。検証装置５のメモリ５１には、Ｙ₁ ，…，Ｙ_k ，ｇ，ｇ₁ ，ｇ₂ ，ｙ，ｙ_T ，ｐ，ｑが格納されている。制御部は各機器を以下のように制御する。
【０１０８】
・（署名検証ステップ）Ｉ：
公開掲示板からＬ_k を読み込み、リスト中の各エントリＭ＝｛ｓ₂ ，ｃ₂ ，ｓ₃ ，ｃ₃ ，ｍ，ｈ_p ，ｚ_p ｝を順次、署名検証器５２へ入力する。更に、ｇ，ｙ，ｑ，ｐを入力する。駆動された署名検証器５２は、
【０１０９】
【数２８】

【０１１０】
を計算し、その結果をそれぞれｃ₂ およびｃ₃ と比較する。いずれも等しければ、署名検証器５２はＯＫを出力し、そうでなければＮＧを出力する。制御部５６は、署名検証器５２がＮＧを出力した場合に、リスト中におけるその不正な署名の位置（インデックス）をＪ_k として出力する。不正な署名が複数ある場合には、それらすべてのインデックスを出力する。一度もＮＧが出力されなければ、ＯＫを出力する。
【０１１１】
・（対応検証ステップ）Ｊ：
追跡インデックスＪ_i と、Ｊ_i に対してＭｉｘ装置４−ｉが出力したＪ_i-1 ，Ｋ_i とに対して、Ｊ_i ，Ｊ_i-1 ，Ｋ_i および、Ｌ_i のＪ_i 番目のエントリ（Ｒ_i ，Ｅ_i ）、Ｌ_i-1 のＪ_i-1 番目のエントリ（Ｒ_i-1 ，Ｅ_i-1 ）、およびＹ_i を対応検証器５３へ入力する。対応検証器５３は、Ｄｅｃ（Ｅ_i-1 ，Ｋ_i ）がＥ_i に等しく、
【０１１２】
【数２９】

【０１１３】
がＲ_i-1 に等しい場合にＯＫを出力し、そうでない場合にはＮＧを出力する。
・（追跡情報検証ステップ）Ｋ：
監視装置が出力したｈ_p ，ｃ₄ ，ｓ₄ およびｄ，ｇ₁ ，ｇ₂ ，ｙ_T ，ｑ，ｐを追跡情報検証器５４へ入力する。追跡情報検証器５４は
【０１１４】
【数３０】

【０１１５】
を計算し、その結果がｃ₄ と等しければＯＫを出力し、等しくなければＮＧを出力する。制御部５６は追跡情報検証器５４の出力を出力する。
【０１１６】
・（署名抹消ステップ）Ｌ：
ｈ_p およびＬ_k を署名抹消器５５へ入力する。署名抹消器５５は、Ｌ_k の中に、入力されたｈ_p と一致するｈ_p を含むＭが存在するか否かを調べ、存在しない場合はＯＫを出力し、存在するならば、そのＭのＬ_k 中での位置（インデックス）Ｊ_k を出力する。制御部５６はＯＫまたはＪ_k を公開掲示板６へ送信する。
【０１１７】
本実施例の投票装置は、以下の手順を順次実行する。
手順２１：各投票装置と署名装置とは以下のステップを順次実行する。
（ａ）投票装置１−ｉは、投票内容ｍが外部より入力されると、上述の（追跡情報埋込および証明ステップ）Ｃを実行し、（ｈ_w ，ｄ，ｃ₁ ，ｓ₁ ）を署名装置へ送信する。
（ｂ）署名装置２は、（ｈ_w ，ｄ，ｃ₁ ，ｓ₁ ）を受信して上述の（追跡情報埋込検証およびコミットステップ）Ａを実行し、（ｚ_w ，ｔ'_g ，ｔ'_h ）を投票装置１−ｉへ送信する。
（ｃ）投票装置１−ｉは、（ｚ_w ，ｔ'_g ，ｔ'_h ）を受信し、上述の（ブラインド処理ステップ）Ｄを実行してｃ'₂ を署名装置２へ返信する。
（ｄ）署名装置２は、ｃ'₂ を受信し、上述の（署名生成ステップ）Ｂを実行してｓ'₂ を署名装置２へ返信する。
（ｅ）投票装置１−ｉはｓ'₂ を受信し、上述の（暗号投票文作成ステップ）Ｅを実行してＲ₀ ，Ｅ₀ を公開掲示板６へ送信する。
【０１１８】
（暗号投票文作成ステップ）Ｅの説明にあるように、Ｅ₀ は投票文ｍとそれに対して署名装置が発行した署名との対Ｍを多重に暗号化したものである。各投票装置１−ｉが公開掲示板６に送信した（Ｒ₀ ，Ｅ₀ ）からなるリストをＬ₀ とする。
【０１１９】
手順２２：ｉ＝１，…，ｋに対して、Ｍｉｘ装置４−ｉは公開掲示板６からＬ_i-1 を読み込み、（Ｍｉｘ処理ステップ）Ｆを実行し、Ｌ_i を公開掲示板６へ送信する（前述の通り、Ｌ_k はＭのリストとなる）。
【０１２０】
手順２３：検証装置５は、上述の（署名検証ステップ）Ｉを実行する。ＯＫが出力されれば、正常終了であり、停止する。追跡インデックスＪ_k が出力された場合，以下のステップに進む。
【０１２１】
手順２４：以下の処理をｊ＝ｋ，…，１に対して順次繰り返す。
（ａ）検証装置５は、Ｊ_j をＭｉｘ装置４−ｊへ送信する。
（ｂ）Ｍｉｘ装置４−ｊは、検証装置５からＪ_j を受信し、上述の（対応証明ステップ）Ｇを実行し、Ｊ_j-1 ，Ｋ_j を検証装置５へ送信する。
（ｃ）検証装置５は、上述の（対応検証ステップ）Ｊを実行し、ＮＧが出力されたならば、Ｍｉｘ装置４−ｊが不正であると認定して停止する。
【０１２２】
手順２５：検証装置５は、Ｊ₀ を監視装置３へ送信する。
手順２６：監視装置３は、Ｊ₀ を受信し、Ｊ₀ 番目の投票装置が署名装置へ送信した（ｈ_w ，ｄ，ｃ₁ ，ｓ₁ ）のｈ_w を公開掲示板６より読み込んで上述の（追跡情報生成ステップ）Ｈを実行し、ｈ_p ，ｃ₄ ，ｓ₄ を検証装置５へ送信する。
【０１２３】
手順２７：検証装置５は、ｈ_p ，ｃ₄ ，ｓ₄ を受信し、上述の（追跡情報検証ステップ）Ｋを実行する。ＮＧが出力された場合、監視装置３が不正であると認定して停止する。ＯＫが出力された場合、Ｌ_k を読み込んで上述の（署名抹消ステップ）Ｌを実行する。ＯＫが出力された場合には、正常終了として停止する。インデックスＪ_k が出力された場合、以下を実行する。まず、得られたＪ_k が既に上述の（署名検証ステップ）Ｉの出力中に含まれていないことを確認する。含まれている場合には、この処理を終了する。含まれていない場合、手順２４以降を再度実行する。
【０１２４】
以上の動作によって得られたリストＬ_k において、検証装置５が公開掲示板６へ送付したすべてのインデックスＪ_k を抹消情報とし、これに該当する全ての投票を無効としたものが最終的な開票結果とする。
【０１２５】
上記では、検証装置５のみが他の装置の出力を検証する場合について説明したが、各装置が独立した安全性を確保できるよう、検証装置５が備える各検証機能を、各Ｍｉｘ装置４−ｉおよび監視装置３が具備し、同様の検証を行っても良い。
【０１２６】
上記では、全ての通信を公開掲示板６を通じて行う場合について説明したが、各装置間に通信路を設け、送信する全てのデータに送信側のディジタル署名を添付することによって、公開掲示板６の代替とする事も可能である。
【０１２７】
上記において、匿名電子投票装置および匿名電子投票処理方法について説明したが、当該匿名電子投票処理方法はプログラムの形で記述しておくことができかつ当該プログラムを記録媒体に記録しておくことができる。したがって、本発明は当該記録媒体自体をも発明の対象とするものである。
【０１２８】
【発明の効果】
以上説明した如く、本発明によれば、不正者を特定する手段を提供することによって、投票者あるいはＭｉｘサーバによる不正に対する抑止効果が得られる。
【図面の簡単な説明】
【図１】電子投票装置のブロック図を示す。
【図２】署名装置のブロック図を示す。
【図３】投票装置のブロック図を示す。
【図４】Ｍｉｘ装置のブロック図を示す。
【図５】監視装置のブロック図を示す。
【図６】検証装置のブロック図を示す。
【符号の説明】
１：投票装置
２：署名装置
３：監視装置
４：Ｍｉｘ装置
５：検証装置
６：公開掲示板
７：認証通信路[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a method for efficiently realizing bearer voting in a telecommunications system.
[0002]
[Prior art]
  As a conventional technique, Japanese Patent Application No. 10-320173(Disclosed in Japanese Patent Laid-Open No. 2000-207483 as a domestic priority application)Will be described.
[0003]
This method is an improved version of the method proposed in A. Fujioka, T. Okamoto, K. Ohta: "A Practical Secret Voting Scheme for Large Scale elections", AUSSCRYPT '92, LNCS 718, Springer-Verlag . This method includes a signature terminal, a plurality of voting terminals, a public bulletin board, and a plurality of aggregation terminals. The signing terminal and all voting terminals are connected by an authentication communication path, and the public bulletin board and all voting terminals are connected by an anonymous communication path.
[0004]
Here, the anonymous communication path allows the caller to authenticate the receiver (that is, it can confirm that the receiver is indeed a valid receiver), but the receiver can specify the caller. It is a communication path having a function of being impossible or extremely difficult.
[0005]
Communication using such a communication path corresponds to, for example, a case where a caller communicates from a public telephone that is not under monitoring to a specific receiver. All voters hold the encryption key y, and each tabulation terminal holds partial information of the decryption key x corresponding to the encryption key y.
[0006]
After determining the message m to be voted, the voter drives the voting terminal to connect to the signing terminal, and obtains the blind signature σ for m. The signing terminal issues a blind signature after confirming that the voter is legitimate, that is, has the right to vote and has not yet voted.
[0007]
In the blind signature, the signer issues a signature σ ′ for the message m ′, but the voter has means for converting m ′, σ ′ to m, σ. Therefore, by using a blind signature, the signer can issue a signature but does not know the value of the actual message / signature pair (m, σ).
[0008]
Such blind signature methods are described in, for example, D. Chaum: “Security without identification: Transaction systems to make big brother obsolete”, Communications of the ACM, Vol. 28, No. 10, pp. 1030-1044, October, 1985. As shown in FIG. 4, it can be easily configured based on the RSA signature.
[0009]
The voter who has obtained the message / signature pair S: = (m, σ) encrypts S with y to obtain the ciphertext E, and sends E to the public bulletin board through the anonymous communication path.
[0010]
After the voting deadline, the totaling terminal having partial information of the decryption key cooperates to decrypt the ciphertext from each voter appearing on the public bulletin board to obtain a list of message / signature pairs (m, σ). Of these, only messages with correct signatures are counted as a count target.
[0011]
Since the above conventional method uses a physical anonymous communication path, it is not suitable for home voting or when voting from the home via the Internet. MIX-NET has been proposed as a means for realizing an anonymous communication path by a telecommunications system regardless of a physical configuration. In MIX-NET, L servers U₁, ..., U_LIs a system connected in series with a registered communication path.
[0012]
When implementing this using the RSA function, each server has a large prime number p_i, Q_iN_i= P_i・ Q_iAnd e_i・ D_i= 1 (mod LCM (p_i-1, q_i-1)) is satisfied (d_i, N_i), (E_i, N_i) Are a decryption key and an encryption key, respectively.
[0013]
To encrypt the message m by RSA, first, the random number r is selected, and m and r are bit-coupled to m‖r. And
[0014]
[Expression 1]

[0015]
The ciphertext M is obtained as follows. In the following, this encryption procedure is referred to as E_iWrite (m, r).
Each voter chooses a message / signature pair M to be sent.₁(E₂(... E_L(M, r_L), ...), r₂), R₁) And multiplex encryption using each encryption key, and U₁Send to.
[0016]
U₁After collecting encrypted input sentences from multiple voters,₁For each input sentence₂(... E_L(M, r_l ), ...) r₂) And r₁Get. U₁Is the E obtained from each input sentence₂(... E_L(M, r_l ), ...) r₂) In random order and U₂Send to.
[0017]
At this time, r for each message₁By keeping U secret₂Each E sent to₂(... E_L(M, r_l ), ...) r₂) U₁It is possible to make it impossible to determine which message of the input to the decryption result.
[0018]
Hereinafter, U₂, ..., U_LRepeats the same process. Finally U_LPublishes a list of message / signature pairs that have been decrypted and randomly replaced. At least one server has a random number r_iAnd by keeping the order of replacement secret, each user₁The input ciphertext input to_LThe connection with each message / signature pair output by is hidden and functions as an anonymous communication path.
[0019]
[Problems to be solved by the invention]
When the physical anonymous communication path is replaced with MIX-NET as in the conventional method described above, an incorrect result is output due to a malfunction of the Mix server or intentional interference caused by voting between the voter and the Mix server. There is a possibility.
[0020]
For example, if one of the voters is an encrypted message / signature pair E₁(E₂(... E_L(M, r_L), ...), r₂), R₁), Instead of a random value R that fails verification, an encrypted value E₁(E₂(... E_L(R, r_L), ...), r₂), R₁) And the mix server U of the partner with whom the legitimate message / signature pair M was colluded_LAssume that you sent it secretly.
[0021]
Server U_LIs a message / signature pair M passed from a voter who has collaborated in advance with one message / signature pair in the list of messages / signature pairs to be output immediately after outputting all the processing and immediately before outputting the result. Instead, output. By verifying this list, R is rejected, but the correct message / signature pair that has been replaced is not included in the list, so it is not subject to tabulation, and an incorrect result that is different from the original tabulation result is displayed. It will appear.
[0022]
It is an object of the present invention to prevent fraud in counting due to vote replacement as described above in an electronic voting system that does not use a physical anonymous communication path.
[0023]
[Means for Solving the Problems]
First, instead of blind signatures, signers can use erasable blind signatures (Fair
Issue a signature using Blind Signature.
[0024]
The erasable blind signature is a signing method including means for converting a message / signature pair m ′, σ ′ issued by the signer into m, σ, similar to the blind signature. It is possible to realize a means for a voter to obtain a signature without knowing the above. In addition to this, the erasable blind signature is a signature method in which a monitor holding certain monitoring information τ has means for extracting information identifying m and σ from m ′ and σ ′.
[0025]
If an invalid message / signature pair (m, σ) is found at the time of aggregation, the Mix server U_LPublishes the input corresponding to the incorrect output (m, σ) and proves that the output is obtained by the correct processing.
[0026]
If the process is proved correct, the next server U_L-1U_LThe input value published by is the output value U_L-1, And prove the correctness of the processing for the input / output relationship. Repeat this procedure for the first server U₁Repeat until. On the way, if there is a Mix server that fails to prove, the server is regarded as an unauthorized person.
[0027]
If all servers are successfully certified, U₁Voters who send input published by are considered fraudulent voters.
[0028]
When an unauthorized voter is found, the monitor uses the erasable blind signature m ′, σ ′ issued by the signer to the unauthorized voter and the monitoring information τ, and the original message / signature pair m. , Σ is obtained. Using this W, it is confirmed whether m and σ are included in the list of message / signature pairs obtained at the time of aggregation. When m and σ are included, each server sequentially discloses the input corresponding to the output by the above-described means, and proves the correctness of the processing. By repeating the above means, it is possible to eliminate voting by all unauthorized voters and identify an unauthorized Mix server.
[0029]
DETAILED DESCRIPTION OF THE INVENTION
Examples will be described. FIG. 1 is a block diagram of the electronic voting apparatus of this embodiment. The electronic voting device of this embodiment includes n voting devices 1-i, a signature device 2, a monitoring device 3, k mix devices 4-i, a verification device 5, and a public bulletin board 6. Each device and the public bulletin board are connected by an authentication communication path 7 capable of mutual authentication. In the following description, when each device transmits and receives information to and from each other, it is assumed that all are performed via a public bulletin board.
[0030]
Hereinafter, each device will be described. In this embodiment, as an erasable blind signature method, J. Camenisch, “Group Signature Schemes and Payment Systems Based on the Discrete Logarithm Problem”, ETH Series in Information Security and cryptography, Volumn 2, pp.124-132, Hartung- The method based on the Schnorr signature proposed by Gorre Verlag is used. First, the erasable blind signature method will be described.
[0031]
Let p and q be large prime numbers, and q be divisible by (p−1). g, g₁, G₂Z^* _pLet be the element of order q in. H (·) is a one-way hash function, and the binary operator a‖b represents a value obtained by combining binary expressions of a and b.
[0032]
  Y for random number τ_TThe
[31]

  A value that satisfies τ is secret information necessary for signature deletion, and is kept secret by the monitor. y_TPublish.
[0033]
Similarly, y = g for random number x^xThe value satisfies mod p. x is a signing key and is kept secret by the signer. y is disclosed as a signature verification key.
[0034]
The following description is a processing procedure between the requester and the signer when the signature requester obtains a signature for the document m from the signer.
Step 1: The requester sets the random number a to Z^* _qChoose from
[0035]
[Expression 2]

[0036]
Calculate The calculation was then performed correctly (ie,
[0037]
[Equation 3]

[0038]
Certificate that proves that₁, S₁) In the following procedure.
(A) Random number w₁∈Z^* _qSelect
[0039]
[Expression 4]

[0040]
Calculate
(B) s₁: = W₁+ C₁ a ^-1 Calculate mod p.
  The above calculation result (h_w, D, c₁, S₁) To the signer.
  Procedure 2: The signer performs the following steps:
(A)
[0041]
[Equation 5]

[0042]
Confirm that If not, the process is stopped.
(B) z_w: = H_w ^xCalculate mod p.
(C) Random number w₂∈Z_qSelect
[0043]
[Formula 6]

[0044]
Calculate
(D) (z_w, T '_g, T '_h) To the requester.
Step 3: The requester sets random numbers γ and δ to Z_qChoose from
[0045]
[Expression 7]

[0046]
And c '₂Is sent to the signer.
Step 4: The signer is s'₂: = W₂-C '₂xmod q is calculated and sent to the requester.
[0047]
Step 5: The requester is₂: = S '₂+ Γmod q is calculated. Furthermore, h_p= H_W ^amod p certificate (c_Three, S_Three) Is generated by the following procedure.
(A) Random number w_Three∈Z_qIs generated.
(B)
[0048]
[Equation 8]

[0049]
Calculate
(C) s_Three: = W_Three-C_Threeamod q is calculated.
[0050]
Finally, (m, h_p, Z_p, C₂, S₂, C_Three, S_Three) As a document / signature pair.
In the above procedure,
[0051]
[Equation 9]

[0052]
And
[0053]
[Expression 10]

[0054]
In addition,
[0055]
## EQU11 ##

[0056]
So it was issued (m, h_p, Z_p, C₂, S₂, S_Three, C_Three)
[0057]
[Expression 12]

[0058]
The correctness can be verified by confirming that
In order to delete the issued signature, the supervisor with the confidential information τ
[0059]
[Formula 13]

[0060]
Calculate and publish. This value is
[0061]
[Expression 14]

[0062]
Therefore, this value h_pSignatures containing are considered invalid. In addition, a certificate (s_Four, C_Four) Is calculated as follows.
Calculation 1: Random number w_Four∈Z_qIs generated.
Calculation 2:
[0063]
[Expression 15]

[0064]
Calculate
Calculation 3: s_Four: = W_Four-C_FourCalculate τmod q.
This certificate
[0065]
[Expression 16]

[0066]
If the following holds, it is guaranteed that the processing of the observer is correct.
In this embodiment, a method based on the RSA encryption described in the description of the conventional method is used as a method for creating a ciphertext to be input to the MIX-NET. In the following description, | a | represents the number of bits of a. For i = 1,..., n, (e_i, N_i), (D_i, N_i) Are the public key and secret key of RSA encryption. However, | N_i｜ ＞ ｜ N_{i + 1}|
[0067]
The signature apparatus will be described with reference to FIG. The signature device 2 includes a memory 21, a tracking information embedding verifier 22, a commitment calculator 23, a signature calculator 24, and a control unit 25 for controlling them. The memory 21 includes g, g₁, G₂, P, q, y, y_TAnd x are stored. The control unit 25 controls each device to execute the following steps.
[0068]
(Tracking information embedded verification and commit step) A:
Input received from voting device 1-i (h_w, D, c₁, S₁) To the tracking information embedded verifier 22 (h_w, D, c₁, S₁) And g₁, G₂, P, q, y_TEnter. The driven tracking information embedded verifier 22
[0069]
[Expression 17]

[0070]
And the result is c₁If they are equal, OK is output, and if they are not equal, NG is output. When NG is output, the control unit 25 stops the process. If OK is output, go to commitment calculator 23_w, G, p, q. The driven commitment calculator 23 has an input h_w, G, p, q, an integer random number greater than or equal to 1 and less than q₂And z_w, T '_g, T '_hThe
[0071]
[Expression 18]

[0072]
Calculate and output as follows.
(Signature generation step) B:
Input c ′ received from voting device 1-i₂In response to the signature calculator 24 c ′₂And w₂, X, q. The signature calculator 24 is s ′₂: = W₂-C '₂Calculate and output xmod q.
[0073]
The control unit 25 outputs the output (z_w, T '_g, T '_h) And s'₂Are sequentially transmitted to the voting apparatus 1-i.
[0074]
The voting device will be described with reference to FIG. The voting apparatus 1-i includes a memory 11, a tracking information embedding device 12, a tracking information embedding prover 13, a disturbance device 14, a disturbance correction device 15, an encryption device 16, and a control unit 17 for controlling them. . The memory 11 has g, g₁, G₂, P, q, y, y_TIs stored. The control unit 17 controls each device to execute the following steps.
[0075]
(Tracking information embedding and certification step) C:
To trace information embedder 12₁, G₂, P, q, y_TEnter. The tracking information embedder uses a random number a∈Z^* _qProduces
[0076]
[Equation 19]

[0077]
And h_w, D are output. g₁, Y_T, P, q and the output h of the tracking information embedder 12_w, D, a are input to the tracking information embedded certifier 13. The tracking information embedded certifier 13 is a random number w.₁∈Z^* _qSelect
[0078]
[Expression 20]

[0079]
And s₁: = W₁+ C₁compute amod p and c₁, S₁Is output. The controller 17 (h_w, D, c₁, S₁) To the signature device 2.
[0080]
(Blind processing step) D:
Message m to be voted and received from the signature device 2 (z_w, T '_g, T '_h), M, z_w, T '_g, T '_hAnd p, q, and g are input to the disturber 14. Disturber 14 converts random numbers γ and δ to Z_qChoose from
[0081]
[Expression 21]

[0082]
To calculate γ, h_p, Z_p, C₂, C '₂Is output. The control unit 17 is c ′₂Is transmitted to the signature device 2.
[0083]
・ (Cryptographic ballot making step) E:
S ′ received from the signature device 2₂S '₂Q and γ are input to the disturbance corrector 15. The driven disturbance corrector 15 is s₂: = S '₂+ Γmod q is calculated. In addition, perform the following steps to_Three, C_ThreeS₂, S_Three, C_ThreeIs output.
[0084]
Step 11: Random number w_Three∈Z_qIs generated.
Step 12:
[0085]
[Expression 22]

[0086]
Calculate
Step 13: s_Three: = W_Three-C_Threeamod q is calculated.
[0087]
Then s₂, S_Three, C_Three, M, h_p, Z_p, C₂Is input to the encryptor 16. For simplicity, we will denote these inputs as M. Y₁, ..., Y_nIs input to drive the encryptor 16. The driven encryptor 16 has a random number K₁, ..., K_nProduces
[0088]
[Expression 23]

[0089]
And E₀: = Enc (... Enc (Enc (M, K_n), K_n-1) ..., K₁) And R₀, E₀Is output. Here, Enc (α, β) means an operation for encrypting the ciphertext α with the secret key β. The control unit 17 is R₀, E₀To the public bulletin board.
[0090]
The encryption operation Enc may use any predetermined encryption algorithm such as IDEA or RC6. Furthermore, different algorithms may be used for each encryption operation. Each K_iThe number of bits is determined so as to match the encryption algorithm used. Each public key N_iAlso, N_i| And | N_i-1The difference between |_i｜ Determine that it is over.
[0091]
In the following description, each voting device 1-i transmits to the public bulletin board 6 (R₀, E₀)₀Is described.
[0092]
The Mix device will be described with reference to FIG. The Mix device 4-i includes a memory 41, a decoder 42, a replacement device 43, a correspondence prover 44, and a control unit 45 that controls them. The memory 41 of the Mix device 4-i has X_i: = (D_i, N_i) And Y₁, ..., Y_kIs stored. The control unit 45 controls each device to execute the following steps.
[0093]
(Mix processing step) F:
Input L_i-1X_iAnd L_i-1Each (R_i-1, E_i-1) Are sequentially input to the decoder 42. The decoder 42
[0094]
[Expression 24]

[0095]
And calculate the value for the predetermined number of bits from the lower side of the operation result_iAnd the rest is R_iAnd K_iUsing E_i: = Dec (E_i-1, K_i). Here, Dec is a decryption operation and represents an algorithm corresponding to the cryptographic operation used by the voting device 1-i. The decoder 42 (R_i, E_i) Is output. The controller 45 is sequentially output from the decoder 42 (R_i, E_i) Is stored in the memory 41. L_i-1After the decoding is completed for all the entries of, the replacement device 43 is driven and all the (R_i, E_i) Are input to the replacement device 43. The replacement device 43 generates a random replacement π, and generates a list obtained by exchanging the order of each entry of the list input according to π._iOutput as. For example, when n = 3, if the randomly generated substitution is π = {3, 1, 2}, it is the first in the list (R_i, E_i) Is third and second (R_i, E_i) Is first and third (R_i, E_i) For the second list_iAnd The substitution device 43 also outputs π. The control unit 45 stores π in the memory 41, and L_iIs sent to the public bulletin board 6.
[0096]
・ (Corresponding Proof Step) G:
1 ≦ J_i≦ n integer value J_i(Hereafter, this variable is called the tracking index) and L_i-1J_i, L_i-1And π, X_iIs input to the correspondence prover 44. Correspondence prover 44 is_iSearch for the location where J_iIs J_i-1List L_i-1J_i-1Th entry (R_i-1, E_i-1) And similar to the operation of the decoder 42,
[0097]
[Expression 25]

[0098]
And calculate the value for the predetermined number of bits from the lower side of the operation result_iAnd J_i-1, K_iIs output.
[0099]
List L output by the last (i = k) Mix device 4-i_kEntries (R_k, E_k) If all were processed successfully, R_kContains nothing, E_kIs a message / signature pair M = {s₂, S_Three, C_Three, M, h_p, Z_p, C₂}. In the following, L_kIs described as a list of M.
[0100]
FIG. 5 is a block diagram of the monitoring device. The monitoring device 3 includes a control unit 31, a memory 32, a tracking information calculator 33, and a tracking information prover 34. The memory 32 of the monitoring device 3 has g, g₁, G₂, P, q, τ, y_TIs stored. The control unit 31 will be described below.
・ (Tracking information generation step) H
Control each device to execute.
[0101]
Process 1: For input d, d, g₁, Τ, q, p are input to the tracking information calculator 33.
Process 2: The driven tracking information calculator 33
[0102]
[Equation 26]

[0103]
Is calculated and output.
Process 3: Next, to the tracking information prover 34_p, D, g₁, G₂, P, q, τ.
[0104]
Process 4: The tracking information prover 34 (c_Four, S_Four).
(A) Random number w_Four∈Z_qIs generated.
(B)
[0105]
[Expression 27]

[0106]
Calculate
(C) s_Four: = W_Four-C_FourCalculate τmod q.
Process 5: The control part 31 is h_pAnd c_Four, S_FourIs output.
[0107]
The verification apparatus will be described with reference to FIG. The verification device 5 includes a memory 51, a signature verification unit 52, a correspondence verification unit 53, a tracking information verification unit 54, a signature deletion unit 55, and a control unit 56 for controlling them. The memory 51 of the verification device 5 has Y₁, ..., Y_k, G, g₁, G₂, Y, y_T, P, q are stored. The control unit controls each device as follows.
[0108]
(Signature verification step) I:
L from public bulletin board_kAnd each entry in the list M = {s₂, C₂, S_Three, C_Three, M, h_p, Z_p} Are sequentially input to the signature verifier 52. Furthermore, g, y, q, and p are input. The driven signature verifier 52 is
[0109]
[Expression 28]

[0110]
And the result is c₂And c_ThreeCompare with If both are equal, the signature verifier 52 outputs OK, and otherwise outputs NG. When the signature verifier 52 outputs NG, the control unit 56 sets the position (index) of the invalid signature in the list to J_kOutput as. If there are multiple illegal signatures, all the indexes are output. If NG is never output, OK is output.
[0111]
・ (Corresponding verification step) J:
Tracking index J_iAnd J_iOutput by Mix device 4-i_i-1, K_iAnd J_i, J_i-1, K_iAnd L_iJ_iTh entry (R_i, E_i), L_i-1J_i-1Th entry (R_i-1, E_i-1) And Y_iIs input to the correspondence verifier 53. Correspondence verifier 53 uses Dec (E_i-1, K_i) Is E_iEqual to
[0112]
[Expression 29]

[0113]
Is R_i-1If it is equal to, OK is output, otherwise NG is output.
(Tracking information verification step) K:
H output by the monitoring device_p, C_Four, S_FourAnd d, g₁, G₂, Y_T, Q, p are input to the tracking information verifier 54. The tracking information verifier 54
[0114]
[30]

[0115]
And the result is c_FourIf they are equal, OK is output, and if they are not equal, NG is output. The control unit 56 outputs the output of the tracking information verifier 54.
[0116]
・ (Signature deletion step) L:
h_pAnd L_kIs input to the signature deleting device 55. Signature deleter 55 is L_kEntered in h_pMatching h_pWhether or not there is an M, and if it does not exist, OK is output._kPosition (index) J_kIs output. The control unit 56 is OK or J_kIs sent to the public bulletin board 6.
[0117]
The voting apparatus of the present embodiment sequentially executes the following procedures.
Procedure 21: Each voting device and the signature device sequentially execute the following steps.
(A) When the voting content m is input from the outside, the voting apparatus 1-i executes the above-described (tracking information embedding and proofing step) C, and (h_w, D, c₁, S₁) To the signing device.
(B) The signature device 2 is (h_w, D, c₁, S₁) And execute the above (tracking information embedding verification and commit step) A, and (z_w, T '_g, T '_h) To the voting apparatus 1-i.
(C) The voting device 1-i_w, T '_g, T '_h) And execute the above (blind processing step) D to execute c ′₂Is returned to the signature device 2.
(D) The signature device 2 is c ′₂, And execute (Signature generation step) B described above to execute s ′₂Is returned to the signature device 2.
(E) Voting device 1-i is s'₂And execute the above (encrypted vote sentence creation step) E to execute R₀, E₀Is sent to the public bulletin board 6.
[0118]
(Encryption Voting Text Creation Step) As explained in E, E₀Is a multiplex encryption of a pair M of a vote sentence m and a signature issued by the signature device. Each voting device 1-i transmits to the public bulletin board 6 (R₀, E₀)₀And
[0119]
Procedure 22: For i = 1,..., K, the Mix device 4-i moves from the public bulletin board 6 to L_i-1Is read, (Mix processing step) F is executed, and L_iTo the public bulletin board 6 (as described above, L_kIs a list of M).
[0120]
Procedure 23: The verification apparatus 5 executes (Signature verification step) I described above. If OK is output, it is a normal end and stops. Tracking index J_kIf is output, proceed to the following steps.
[0121]
Procedure 24: The following processing is sequentially repeated for j = k,.
(A) The verification device 5 is J_jIs transmitted to the Mix device 4-j.
(B) The Mix device 4-j sends the verification device 5 to the J_jAnd execute the above (corresponding proof step) G, and J_j-1, K_jIs transmitted to the verification device 5.
(C) The verification device 5 executes the above (corresponding verification step) J, and if NG is output, the verification device 5 recognizes that the Mix device 4-j is illegal and stops.
[0122]
Procedure 25: The verification apparatus 5₀Is transmitted to the monitoring device 3.
Procedure 26: The monitoring device 3₀Received, J₀Th voting device sent to the signing device (h_w, D, c₁, S₁) H_wIs read from the public bulletin board 6 and the above-described (tracking information generation step) H is executed._p, C_Four, S_FourIs transmitted to the verification device 5.
[0123]
Step 27: The verification device 5_p, C_Four, S_FourAnd (Tracking information verification step) K described above is executed. When NG is output, the monitoring apparatus 3 is recognized as being illegal and stops. L when OK is output_kIs read and the above-mentioned (signature deletion step) L is executed. If OK is output, the process ends as a normal end. Index J_kIf is output, execute the following. First, the obtained J_kIs not already included in the output of the above-mentioned (signature verification step) I. If it is included, this process ends. If not included, step 24 and the subsequent steps are executed again.
[0124]
List L obtained by the above operation_k, All indexes J sent from the verification device 5 to the public bulletin board 6_kIs the erasure information, and all votes corresponding to this are invalidated as the final vote result.
[0125]
In the above description, the case where only the verification device 5 verifies the output of another device has been described. However, each verification function included in the verification device 5 is provided to each Mix device 4-i so that each device can ensure independent safety. The monitoring device 3 may be provided and the same verification may be performed.
[0126]
In the above description, the case where all communications are performed through the public bulletin board 6 has been described. However, by providing a communication path between the devices and attaching the digital signature of the transmission side to all data to be transmitted, It is also possible to do.
[0127]
In the above description, the anonymous electronic voting apparatus and the anonymous electronic voting processing method have been described. However, the anonymous electronic voting processing method can be described in the form of a program and the program can be recorded on a recording medium. . Therefore, the present invention also covers the recording medium itself.
[0128]
【The invention's effect】
As described above, according to the present invention, by providing a means for identifying an unauthorized person, a deterrence effect against fraud by a voter or a Mix server can be obtained.
[Brief description of the drawings]
FIG. 1 shows a block diagram of an electronic voting apparatus.
FIG. 2 shows a block diagram of a signature device.
FIG. 3 shows a block diagram of a voting device.
FIG. 4 shows a block diagram of a Mix device.
FIG. 5 shows a block diagram of a monitoring device.
FIG. 6 shows a block diagram of the verification device.
[Explanation of symbols]
1: Voting device
2: Signature device
3: Monitoring device
4: Mix device
5: Verification device
6: Public bulletin board
7: Authentication channel

Claims (2)

Anonymous electronic voting device that makes it difficult to know the correspondence between each vote and the voter by inputting the vote sentences from a plurality of voters and outputting them by randomly replacing the order of all inputted vote sentences Because
Multiple fraud devices, multiple mix devices to ensure anonymity by reordering encrypted voting and decrypting ciphertext parts, signature devices, A monitoring device for eliminating anonymity for enabling tracking of invalid voting / signature pairs, and a verification device;
The voting device includes information h _w used by the signature device to issue a signature, and includes a tracking information embedding and proof step configuration unit that proves that the tracking information is included in the information,
The signing device comprises a tracking information embedding verification and commit step component for verifying that the tracking information is correctly embedded in h _w created by the voting device,
The voting device includes a blind processing step configuration unit that randomizes an input vote sentence m and creates a disturbed vote sentence m ′,
The signature device comprises a signature generation step configuration unit that issues a blind signature σ ′ for the inputted disturbed vote sentence m ′,
The voting device converts σ ′ to obtain a signature σ for the voting text m, encrypts the voting text / signature pair (m, σ) with the public key of the Mix device, and obtains a cipher text E Comprising a component,
The Mix device includes a Mix processing step configuration unit that outputs a list created by decrypting and randomly replacing an input list including a plurality of ciphertexts E,
The verification device includes a signature verification step configuration unit that verifies that each element included in the list output from the Mix device is a correct vote sentence / signature pair by verifying the signature,
Based on the replacement used by the Mix processing step component, the Mix device discloses the position in the input list corresponding to the specified position in the output list, and the output has the input ciphertext at the disclosed position. A correspondence proof step configuration unit that outputs a certificate that proves that the value is based on a correctly decrypted result;
The verification device includes an input / output correspondence output by the Mix device in the correspondence proof step, and a correspondence verification step configuration unit for verifying that the certificate is correct,
Monitoring device, by using the secret information tau, with tracking information generating step configuration unit for outputting trace information h _p capable of identifying the (m ', σ') corresponding to the (m, sigma),
Verification device, when the Mix device searches the list output in Mix process step, the monitoring device is vote-signature pair specified from h _p output by the tracking information generating step (m, sigma) are included, the An anonymous electronic voting apparatus comprising a signature erasure step configuration unit that outputs erasure information for invalidating voting. Anonymous electronic voting process that makes it difficult to know the correspondence between each vote and the voter by taking the vote sentences from multiple voters as input and replacing the order of all the entered vote sentences at random A method,
Multiple fraud devices, multiple mix devices to ensure anonymity by reordering encrypted voting and decrypting ciphertext parts, signature devices, In order to invalidate the illegal vote / signature pair, a monitoring device that erases anonymity for enabling tracking thereof, and an electronic voting device equipped with a verification device are used,
A voting device creates information h _w used by the signing device to issue a signature and performs tracking information embedding and proofing steps to prove that the tracking information is included in the information;
The signing device performs a tracking information embedding verification and commit step to verify that the tracking information is correctly embedded in the h _w created by the voting device;
The voting device performs a blind processing step of randomizing the input vote sentence m to create a disturbed vote sentence m ′,
The signature device performs a signature generation step of issuing a blind signature σ ′ for the input disturbed vote sentence m ′,
The voting device converts σ ′ to obtain a signature σ for the voting text m, encrypts the voting text / signature pair (m, σ) with the public key of the Mix device, and obtains a cipher text E Run
A Mix device executes a Mix processing step of outputting a list created by decrypting and randomly replacing an input list consisting of a plurality of ciphertexts E;
The verification device performs a signature verification step for verifying by verifying the signature that each element included in the list output by the Mix device is a correct vote sentence / signature pair;
The Mix device discloses the position in the input list corresponding to the specified position in the output list based on the substitution used in the Mix processing step, and the output correctly decrypts the input ciphertext at the disclosed position Execute a corresponding proof step that outputs a certificate certifying that the value is based on the result obtained,
The verification device executes an input / output correspondence output by the Mix device in the correspondence proof step and a correspondence verification step for verifying that the certificate is correct,
Monitoring device, using a secret information tau, perform the (m ', σ') tracking information generating step of outputting the tracking information h _p that can be identified corresponding to (m, sigma),
Verification device, when the Mix device searches the list output in Mix process step, the monitoring device is vote-signature pair specified from h _p output by the tracking information generating step (m, sigma) are included, the An anonymous electronic voting processing method characterized by executing a signature erasure step for outputting erasure information for invalidating voting.

Images