(57)【特許請求の範囲】
【請求項１】
複数の投票者からの投票文を入力とし、入力された全ての投票文の順序をランダムに置換して出力することによって各投票と投票者との対応を知ることを困難とする匿名電子投票装置であって、
複数の投票装置と、暗号化されている投票の順序入れ替えおよび暗号文部分の復号を行うことにより匿名性を確保するための複数のＭｉｘ装置と、署名装置と、不正が行われた場合にその不正投票・署名対を無効にするためにそれらの追跡を可能にするための匿名性を抹消する監視装置と、検証装置を具備し、
投票装置が、署名装置が署名発行に用いる情報hwを作成し、その情報に追跡情報が含まれていることを証明する追跡情報埋込および証明ステップ構成部を備え、
署名装置が、投票装置によって作成されたhwに追跡情報が正しく埋め込まれていることを検証する追跡情報埋込検証およびコミットステップ構成部を備え、
投票装置が、入力された投票文mをランダム化して攪乱投票文m’を作成するブラインド処理ステップ構成部を備え、
署名装置が、入力された攪乱投票文m’に対するブラインド署名σ’を発行する署名生成ステップ構成部を備え、
投票装置が、σ’を変換して投票文mに対する署名σを得、その投票文・署名対(m, σ)をＭｉｘ装置の公開鍵で暗号化して暗号文Eを得る暗号投票文作成ステップ構成部を備え、
Ｍｉｘ装置が、複数の暗号文Eからなる入力リストを復号およびランダムに置換して作成されるリストを出力するＭｉｘ処理ステップ構成部を備え、
検証装置が、Ｍｉｘ装置が出力するリストに含まれる各々の要素が正しい投票文・署名対であることを署名を検証することによって確認する署名検証ステップ構成部を備え、
Ｍｉｘ装置が、Ｍｉｘ処理ステップ構成部で使用した置換に基づいて、出力リスト中の指定された位置に対応する入力リスト中の位置を開示し、その出力が、開示した位置にある入力暗号文を正しく復号した結果に基づく値であることを証明する証明書を出力する対応証明ステップ構成部を備え、
検証装置が、Ｍｉｘ装置が対応証明ステップで出力した入出力対応と、その証明書が正しいことを検証する対応検証ステップ構成部を備え、
監視装置が、秘密情報τを用いて、(m’, σ’)に対応する(m, σ)を特定することのできる追跡情報hpを出力する追跡情報生成ステップ構成部を備え、
検証装置が、Ｍｉｘ装置がＭｉｘ処理ステップで出力したリストを検索し、監視装置が追跡情報生成ステップで出力したhpから特定される投票・署名対(m, σ)が含まれる場合に、その投票を無効とするための抹消情報を出力する署名抹消ステップ構成部を備えるようにした
ことを特徴とする匿名電子投票装置。
【請求項２】
複数の投票者からの投票文を入力とし、入力された全ての投票文の順序をランダムに置換して出力することによって各投票と投票者との対応を知ることを困難とする匿名電子投票処理方法であって、
複数の投票装置と、暗号化されている投票の順序入れ替えおよび暗号文部分の復号を行うことにより匿名性を確保するための複数のＭｉｘ装置と、署名装置と、不正が行われた場合にその不正投票・署名対を無効にするためにそれらの追跡を可能にするための匿名性を抹消する監視装置と、検証装置を具備した電子投票装置が用いられ、
投票装置が、署名装置が署名発行に用いる情報hwを作成し、その情報に追跡情報が含まれていることを証明する追跡情報埋込および証明ステップを実行し、
署名装置が、投票装置によって作成されたhwに追跡情報が正しく埋め込まれていることを検証する追跡情報埋込検証およびコミットステップを実行し、
投票装置が、入力された投票文mをランダム化して攪乱投票文m’を作成するブラインド処理ステップを実行し、
署名装置が、入力された攪乱投票文m’に対するブラインド署名σ’を発行する署名生成ステップを実行し、
投票装置が、σ’を変換して投票文mに対する署名σを得、その投票文・署名対(m, σ)をＭｉｘ装置の公開鍵で暗号化して暗号文Eを得る暗号投票文作成ステップを実行し、
Ｍｉｘ装置が、複数の暗号文Eからなる入力リストを復号およびランダムに置換して作成されるリストを出力するＭｉｘ処理ステップを実行し、
検証装置が、Ｍｉｘ装置が出力するリストに含まれる各々の要素が正しい投票文・署名対であることを署名を検証することによって確認する署名検証ステップを実行し、
Ｍｉｘ装置が、Ｍｉｘ処理ステップで使用した置換に基づいて、出力リスト中の指定された位置に対応する入力リスト中の位置を開示し、その出力が、開示した位置にある入力暗号文を正しく復号した結果に基づく値であることを証明する証明書を出力する対応証明ステップを実行し、
検証装置が、Ｍｉｘ装置が対応証明ステップで出力した入出力対応と、その証明書が正しいことを検証する対応検証ステップを実行し、
監視装置が、秘密情報τを用いて、(m’, σ’)に対応する(m, σ)を特定することのできる追跡情報hpを出力する追跡情報生成ステップを実行し、
検証装置が、Ｍｉｘ装置がＭｉｘ処理ステップで出力したリストを検索し、監視装置が追跡情報生成ステップで出力したhpから特定される投票・署名対(m, σ)が含まれる場合に、その投票を無効とするための抹消情報を出力する署名抹消ステップを実行するようにした
ことを特徴とする匿名電子投票処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、電気通信システムで無記名投票を効率的に実現する方法に関する。
【０００２】
【従来の技術】
従来の技術として、特願平１０−３２０１７３（国内優先の出願とされて、特開２０００−２０７４８３号公報に開示）に記載の方法について説明する。
【０００３】
この方法は、A.Fujioka,T.Okamoto,K.Ohta: "A Practical Secret Voting Scheme for Large Scale elections",AUSCRYPT'92,LNCS 718,Springer-Verlag で提案されている方法を改良した方法である。この方法は、署名端末、複数の投票端末、公開掲示板、複数の集計端末から成る。署名端末とすべての投票端末とは認証通信路で接続されており、また、公開掲示板とすべての投票端末とは匿名通信路で接続される。
【０００４】
ここで、匿名通信路は、発信者は受信者を認証できる（即ち、受信者が確かに正当な受信者であることを確認することができる）が、受信者は発信者を特定することができないか、あるいはきわめて困難であるという機能を有する通信路である。
【０００５】
このような通信路を用いた通信は、例えば、発信者が監視下にない公衆電話から特定の受信者へ通信する場合に相当する。すべての投票者は暗号化鍵ｙを保持し、各集計端末は暗号化鍵ｙに対応する復号鍵ｘの部分情報を保持する。
【０００６】
投票者は、投票すべきメッセージｍを決定した後、投票端末を駆動して署名端末へ接続し、ｍに対するブラインド署名σを入手する。署名端末は、投票者が正当な、即ち、投票の権利を持ち、かつ、未投票であることを確認した後、ブラインド署名を発行する。
【０００７】
ブラインド署名では、署名者は、メッセージｍ′に対する署名σ′を発行するが、投票者はｍ′，σ′をｍ，σへ変換する手段を持つ。そのため、ブラインド署名を用いることによって、署名者は署名を発行することはできるが実際のメッセージ・署名対（ｍ，σ）の値を知ることはない。
【０００８】
このようなブラインド署名方法は、例えば、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に示されるように、ＲＳＡ署名に基づいて簡単に構成することができる。
【０００９】
メッセージ・署名対Ｓ：＝（ｍ，σ）を得た投票者は、Ｓをｙで暗号化して暗号文Ｅを得、匿名通信路を通じて、Ｅを公開掲示板へ送付する。
【００１０】
投票締切後、復号鍵の部分情報を持つ集計端末は協力して、公開掲示板に現れた各投票者からの暗号文をそれぞれ復号し、メッセージ・署名対（ｍ，σ）の一覧を得る。これらのうち、正しい署名を伴うメッセージのみを集計対象として集計する。
【００１１】
上記従来の方法は、物理的な匿名通信路を用いているため、在宅投票や、自宅からインターネットを通じて投票するような場合には適さない。匿名通信路を物理的な構成に因らず、電気通信システムにより実現する手段として、ＭＩＸ−ＮＥＴが提唱されている。ＭＩＸ−ＮＥＴではＬ個のサーバＵ1 ，…，ＵL が直列的に記名通信路で接続されたシステムである。
【００１２】
ＲＳＡ関数を用いてこれを実装する場合には、各サーバは、大きな素数ｐi ，ｑi に対し、ｎi ＝ｐi ・ｑi およびｅi ・ｄi ＝１（mod ＬＣＭ（ｐi −１，ｑi −１））を満たす（ｄi ，Ｎi ），（ｅi ，Ｎi ）をそれぞれ復号鍵、暗号化鍵とする。
【００１３】
ＲＳＡによるメッセージｍの暗号化は、まず、乱数ｒを選び、ｍとｒとをビット結合してｍ‖ｒとする。そして、
【００１４】
【数１】
0003689292.tif 000002
【００１５】
として暗号文Ｍを得る。以下では、この暗号化手順をＥi （ｍ，ｒ）と書く。
各投票者は、送信すべきメッセージ・署名対ＭをＥ1 （Ｅ2 （…ＥL （Ｍ，ｒL ），…），ｒ2 ），ｒ1 ）のように、各暗号化鍵を用いて多重に暗号化し、Ｕ1 へ送付する。
【００１６】
Ｕ1 は、複数の投票者から暗号化された入力文が集まった後、これをＸ1 で復号し、各入力文について、Ｅ2 （…ＥL （Ｍ，ｒｌ ），…）ｒ2 ）およびｒ1 を得る。Ｕ1 はそれぞれの入力文から得られたＥ2 （…ＥL （Ｍ，ｒｌ ），…）ｒ2 ）の順序をランダムに置換し、Ｕ2 へ送付する。
【００１７】
この際、各メッセージについてのｒ1 を秘密とすることで、Ｕ2 へ送付された各Ｅ2 （…ＥL （Ｍ，ｒｌ ），…）ｒ2 ）がＵ1 への入力のどのメッセージに関する復号結果であるのかを判別できないようにすることができる。
【００１８】
以下、Ｕ2 ，…，ＵL も同様の処理を繰り返す。最後にＵL は、復号されてランダムに置換されたメッセージ・署名対のリストを公開する。少なくとも一つのサーバが乱数ｒi および置換の順序を秘密に保つことにより、各利用者がＵ1 へ入力した入力暗号文と、ＵL が出力した各メッセージ・署名対との関連は隠匿され、匿名通信路として機能する。
【００１９】
【発明が解決しようとする課題】
上記従来の方法のように、物理的な匿名通信路をＭＩＸ−ＮＥＴで置き換えた場合、Ｍｉｘサーバの故障によってあるいは投票者とＭｉｘサーバとの結託による意図的な妨害によって、不正な結果が出力される可能性がある。
【００２０】
例えば、投票者の一人が、暗号化されたメッセージ・署名対Ｅ1 （Ｅ2 （…ＥL （Ｍ，ｒL ），…），ｒ2 ），ｒ1 ）の代わりに、検証に失敗するようなランダムな値Ｒを暗号化した値Ｅ1 （Ｅ2 （…ＥL （Ｒ，ｒL ），…），ｒ2 ），ｒ1 ）を送信し、正規のメッセージ・署名対Ｍを結託した相手のＭｉｘサーバＵL へ秘密裏に送付したと想定する。
【００２１】
サーバＵL は、すべての処理を終えた後、結果を出力する直前に、出力すべきメッセージ・署名対のリストのうちの一つのメッセージ・署名対を予め結託した投票者から渡されたメッセージ・署名対Ｍですり替えて出力する。このリストを検証することによって、Ｒは棄却されるが、置き換えられてしまった正しいメッセージ・署名対はリストに含まれないために集計対象とならず、本来の集計結果と異なる、不正な結果が現れることになってしまう。
【００２２】
本発明は、物理的な匿名通信路を用いない電子投票システムにおいて、上記のような票のすり替えによる集計上の不正を防止するようにすることを目的としている。
【００２３】
【課題を解決するための手段】
まず、署名者は、ブラインド署名の代わりに、抹消可能ブラインド署名（Fair
Blind Signature）を用いて署名を発行する。
【００２４】
抹消可能ブラインド署名は、ブラインド署名と同様に、署名者が発行したメッセージ・署名対ｍ′，σ′を投票者がｍ，σへ変換する手段を備える署名方法であり、署名者にｍ，σを知られることなく投票者が署名を入手する手段を実現することができる。抹消可能ブラインド署名は、これに加えて、ある監視情報τを保持する監視者がｍ′，σ′からｍ，σを特定する情報を引き出す手段を持つ署名方法である。
【００２５】
集計時に、不正なメッセージ・署名対（ｍ，σ）を発見した場合、ＭｉｘサーバＵL は、その不正な出力（ｍ，σ）に対応する入力を公開し、その出力が正しい処理によって得られたものであることを証明する。
【００２６】
処理が正しいことが証明されたならば、次のサーバＵL-1 は、ＵL が公開した入力値が出力値となるＵL-1 の入力を公開し、その入出力関係について、処理の正しさを証明する。この手順を順次最初のサーバＵ1 まで繰り返す。途中、証明に失敗するようなＭｉｘサーバが存在する場合、そのサーバを不正者と見なす。
【００２７】
すべてのサーバが証明に成功した場合、Ｕ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 署名に基づく方法を用いる。まず、この抹消可能ブラインド署名方法について説明する。
【００３１】
ｐ，ｑを大きな素数とし、ｑは（ｐ−１）を割り切るものとする。ｇ，ｇ1 ，ｇ2 をＺ*p における位数ｑの元とする。Ｈ（・）は一方向性ハッシュ関数であり、二項演算子ａ‖ｂはａとｂとの二進表現を結合した値を表す。
【００３２】
乱数τに対してｙT を
【数３１】
0003689292.tif 000003
を満たす値とする。τは署名抹消に必要な秘密情報であり、監視者が秘密に保持する。ｙT は公開する。
【００３３】
同様に、乱数ｘに対して、ｙをｙ＝ｇx mod p を満たす値とする。ｘは署名鍵であり、署名者が秘密に保持する。ｙは署名検証鍵として公開する。
【００３４】
以下の説明は、署名要求者が文書ｍに対する署名を署名者から入手する際の要求者と署名者との処理手順である。
手順１：要求者は、乱数ａをＺ*q から選び、
【００３５】
【数２】
0003689292.tif 000004
【００３６】
を計算する。次に、この計算が正しく行われたこと（即ち、
【００３７】
【数３】
0003689292.tif 000005
【００３８】
が成り立つこと）を証明する証明書（ｃ1 ，ｓ1 ）を以下の手順で作成する。
（ａ）乱数ｗ1 ∈Ｚ*q を選び、
【００３９】
【数４】
0003689292.tif 000006
【００４０】
を計算する。
（ｂ）ｓ1 ：＝ｗ1 ＋ｃ1 ａ-1mod p を計算する。
上記計算結果（ｈw ，ｄ，ｃ1 ，ｓ1 ）を署名者へ送付する。
手順２：署名者は以下のステップを実行する。
（ａ）
【００４１】
【数５】
0003689292.tif 000007
【００４２】
が成り立つことを確認する。成り立たなければ処理を停止する。
（ｂ）ｚw ：＝ｈwx mod p を計算する。
（ｃ）乱数ｗ2 ∈Ｚq を選び、
【００４３】
【数６】
0003689292.tif 000008
【００４４】
を計算する。
（ｄ）（ｚw ，ｔ'g ，ｔ'h ）を要求者へ送付する。
手順３：要求者は乱数γ，δをＺq より選び、
【００４５】
【数７】
0003689292.tif 000009
【００４６】
を計算し、ｃ'2 を署名者へ送付する。
手順４：署名者はｓ'2 ：＝ｗ2 −ｃ'2 ｘmod q を計算し、要求者へ送付する。
【００４７】
手順５：要求者はｓ2 ：＝ｓ'2 ＋γmod q を計算する。更に、ｈp ＝ｈWa mod p であることの証明書（ｃ3 ，ｓ3 ）を以下の手順で生成する。
（ａ）乱数ｗ3 ∈Ｚq を生成する。
（ｂ）
【００４８】
【数８】
0003689292.tif 000010
【００４９】
を計算する。
（ｃ）ｓ3 ：＝ｗ3 −ｃ3 ａmod q を計算する。
【００５０】
最後に、（ｍ，ｈp ，ｚp ，ｃ2 ，ｓ2 ，ｃ3 ，ｓ3 ）を文書・署名対として保存する。
上記手順において、
【００５１】
【数９】
0003689292.tif 000011
【００５２】
であり、
【００５３】
【数１０】
0003689292.tif 000012
【００５４】
であり、更に、
【００５５】
【数１１】
0003689292.tif 000013
【００５６】
であるので、発行された（ｍ，ｈp ，ｚp ，ｃ2 ，ｓ2 ，ｓ3 ，ｃ3  ）は、
【００５７】
【数１２】
0003689292.tif 000014
【００５８】
が成り立つことを確認することによってその正しさを検証することができる。
発行した署名を抹消する場合には、秘密情報τを持つ監視者が、
【００５９】
【数１３】
0003689292.tif 000015
【００６０】
を計算して公開する。この値は、
【００６１】
【数１４】
0003689292.tif 000016
【００６２】
となるので、この値ｈp を含む署名を無効と見なす。また、監視者の計算が正しいことを証明する証明書（ｓ4 ，ｃ4 ）を以下のように計算する。
計算１：乱数ｗ4 ∈Ｚq を生成する。
計算２：
【００６３】
【数１５】
0003689292.tif 000017
【００６４】
を計算する。
計算３：ｓ4 ：＝ｗ4 −ｃ4 τmod q を計算する。
この証明書は、
【００６５】
【数１６】
0003689292.tif 000018
【００６６】
が成り立つ場合に、監視者の処理が正しいことを保証する。
本実施例では、ＭＩＸ−ＮＥＴへ入力する暗号文を作成する方法として従来法の説明中で記述したＲＳＡ暗号に基づく方法を用いる。以下の説明で、｜ａ｜はａのビット数を表す。ｉ＝１，…，ｎに対して、（ｅi ，Ｎi ）、（ｄi ，Ｎi ）をそれぞれＲＳＡ暗号の公開鍵、秘密鍵とする。ただし、｜Ｎi ｜＞｜Ｎi+1 ｜とする。
【００６７】
図２を参照し、署名装置について説明する。署名装置２は、メモリ２１、追跡情報埋込検証器２２、コミットメント演算器２３、署名演算器２４および、これらを制御する制御部２５を具備する。メモリ２１には、ｇ，ｇ1 ，ｇ2 ，ｐ，ｑ，ｙ，ｙT およびｘが格納されている。制御部２５は以下の各ステップを実行するよう各機器を制御する。
【００６８】
・（追跡情報埋込検証およびコミットステップ）Ａ：
投票装置１−ｉから受信した入力（ｈw ，ｄ，ｃ1 ，ｓ1 ）に対して、追跡情報埋込検証器２２へ（ｈw ，ｄ，ｃ1 ，ｓ1 ）およびｇ1 ，ｇ2 ，ｐ，ｑ，ｙT を入力する。駆動された追跡情報埋込検証器２２は
【００６９】
【数１７】
0003689292.tif 000019
【００７０】
を計算し、その結果がｃ1 と等しければＯＫを出力し、等しくなければＮＧを出力する。ＮＧが出力された場合、制御部２５は処理を停止する。ＯＫが出力された場合、コミットメント演算器２３へｈw ，ｇ，ｐ，ｑを入力する。駆動されたコミットメント演算器２３は、入力ｈw ，ｇ，ｐ，ｑに対し、１以上ｑ未満の整数乱数ｗ2 を生成し、ｚw ，ｔ'g ，ｔ'h を
【００７１】
【数１８】
0003689292.tif 000020
【００７２】
のように計算して出力する。
・（署名生成ステップ）Ｂ：
投票装置１−ｉから受信した入力ｃ'2 に対して、署名演算器２４へｃ'2 およびｗ2 ，ｘ，ｑを入力する。署名演算器２４は、ｓ'2 ：＝ｗ2 −ｃ'2 ｘmod q を計算して出力する。
【００７３】
制御部２５は、それぞれのステップで得られた出力（ｚw ，ｔ'g ，ｔ'h ）およびｓ'2 を、順次、投票装置１−ｉへ送信する。
【００７４】
図３を参照し、投票装置について説明する。投票装置１−ｉは、メモリ１１、追跡情報埋込器１２、追跡情報埋込証明器１３、攪乱器１４、攪乱修正器１５、暗号化器１６および、これらを制御する制御部１７を具備する。メモリ１１には、ｇ，ｇ1 ，ｇ2 ，ｐ，ｑ，ｙ，ｙT が格納されている。制御部１７は以下の各ステップを実行するよう各機器を制御する。
【００７５】
・（追跡情報埋込および証明ステップ）Ｃ：
追跡情報埋込器１２へｇ1 ，ｇ2 ，ｐ，ｑ，ｙT を入力する。追跡情報埋込器は、乱数ａ∈Ｚ*q を生成し、
【００７６】
【数１９】
0003689292.tif 000021
【００７７】
を計算し、ｈw ，ｄを出力する。ｇ1 ，ｙT ，ｐ，ｑおよび、追跡情報埋込器１２の出力ｈw ，ｄ，ａを追跡情報埋込証明器１３へ入力する。追跡情報埋込証明器１３は乱数ｗ1 ∈Ｚ*q を選び、
【００７８】
【数２０】
0003689292.tif 000022
【００７９】
およびｓ1 ：＝ｗ1 ＋ｃ1 ａmod p を計算し、ｃ1 ，ｓ1 を出力する。制御部１７は、（ｈw ，ｄ，ｃ1 ，ｓ1 ）を署名装置２へ送信する。
【００８０】
・（ブラインド処理ステップ）Ｄ：
投票すべきメッセージｍおよび、署名装置２から受信した（ｚw ，ｔ'g ，ｔ'h ）の入力に対し、ｍ，ｚw ，ｔ'g ，ｔ'h およびｐ，ｑ，ｇを攪乱器１４へ入力する。攪乱器１４は乱数γ，δをＺq より選び、
【００８１】
【数２１】
0003689292.tif 000023
【００８２】
を計算し、γ，ｈp ，ｚp ，ｃ2 ，ｃ'2 を出力する。制御部１７は、ｃ'2 を署名装置２へ送信する。
【００８３】
・（暗号投票文作成ステップ）Ｅ：
署名装置２から受信したｓ'2 の入力に対し、ｓ'2 および、ｑ，γを攪乱修正器１５へ入力する。駆動された攪乱修正器１５は、ｓ2 ：＝ｓ'2 ＋γmod q を計算する。更に、以下の手順を実行して、ｓ3 ，ｃ3 を得、ｓ2 ，ｓ3 ，ｃ3 を出力する。
【００８４】
手順１１：乱数ｗ3 ∈Ｚq を生成する。
手順１２：
【００８５】
【数２２】
0003689292.tif 000024
【００８６】
を計算する。
手順１３：ｓ3 ：＝ｗ3 −ｃ3 ａmod q を計算する。
【００８７】
次に、ｓ2 ，ｓ3 ，ｃ3 ，ｍ，ｈp ，ｚp ，ｃ2 を暗号化器１６へ入力する。簡単のため、これらの入力全体をＭと表すことにする。さらに、Ｙ1 ，…，Ｙn を入力して暗号化器１６を駆動する。駆動された暗号化器１６は、乱数Ｋ1 ，…，Ｋn を生成し、
【００８８】
【数２３】
0003689292.tif 000025
【００８９】
を計算し、さらに、Ｅ0 ：＝Ｅｎｃ（…Ｅｎｃ（Ｅｎｃ（Ｍ，Ｋn ），Ｋn-1 ）…，Ｋ1 ）を計算し、Ｒ0 ，Ｅ0 を出力する。ここで、Ｅｎｃ（α，β）は暗号文αを秘密鍵βで暗号化する演算を意味する。制御部１７は、Ｒ0 ，Ｅ0 を公開掲示板へ送信する。
【００９０】
暗号化演算ＥｎｃはＩＤＥＡやＲＣ６など予め定めたどのような暗号アルゴリズムを用いても良い。更に、各暗号化の演算は異なるアルゴリズムを使用しても良い。各Ｋi のビット数は使用する暗号アルゴリズムに適合するように定める。各公開鍵Ｎi も、｜Ｎi ｜と｜Ｎi-1 ｜の差が｜Ｋi ｜以上となるよう定めておく。
【００９１】
以下の説明では、各投票装置１−ｉが公開掲示板６へ送信した（Ｒ0 ，Ｅ0 ）からなるリストをＬ0 と記述する。
【００９２】
図４を参照し、Ｍｉｘ装置について説明する。Ｍｉｘ装置４−ｉは、メモリ４１、復号器４２、置換装置４３、対応証明器４４および、これらを制御する制御部４５を具備する。Ｍｉｘ装置４−ｉのメモリ４１には、Ｘi ：＝（ｄi ，Ｎi ）および、Ｙ1 ，…，Ｙk が格納されている。制御部４５は以下の各ステップを実行するよう各機器を制御する。
【００９３】
・（Ｍｉｘ処理ステップ）Ｆ：
入力Ｌi-1 に対し、Ｘi およびＬi-1 に含まれる各（Ｒi-1 ，Ｅi-1 ）を順次復号器４２へ入力する。復号器４２は、
【００９４】
【数２４】
0003689292.tif 000026
【００９５】
を計算し、演算結果の下位側から予め定められたビット数分の値をＫ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 ）を得、復号器４２の動作と同様に、
【００９７】
【数２５】
0003689292.tif 000027
【００９８】
を計算し、演算結果の下位側から予め定められたビット数分の値をＫi とし、Ｊi-1 ，Ｋi を出力する。
【００９９】
最後尾（ｉ＝ｋ）のＭｉｘ装置４−ｉが出力するリストＬk の各エントリ（Ｒk ，Ｅk ）は、すべて正常に処理された場合、Ｒk には何も含まれず、Ｅk はメッセージ・署名対Ｍ＝｛ｓ2 ，ｓ3 ，ｃ3 ，ｍ，ｈp ，ｚp ，ｃ2 ｝となる。以下では、Ｌk をＭのリストとして説明する。
【０１００】
図５は監視装置のブロック図である。監視装置３は、制御部３１、メモリ３２、追跡情報演算器３３、追跡情報証明器３４を具備する。監視装置３のメモリ３２には、ｇ，ｇ1 ，ｇ2 ，ｐ，ｑ，τ，ｙT が格納されている。制御部３１は以下に説明する
・（追跡情報生成ステップ）Ｈ
を実行するよう各機器を制御する。
【０１０１】
処理１：入力ｄに対して、ｄ，ｇ1 ，τ，ｑ，ｐを追跡情報演算器３３へ入力する。
処理２：駆動された追跡情報演算器３３は、
【０１０２】
【数２６】
0003689292.tif 000028
【０１０３】
を計算し、出力する。
処理３：次に、追跡情報証明器３４へｈp ，ｄ，ｇ1 ，ｇ2 ，ｐ，ｑ，τを入力する。
【０１０４】
処理４：追跡情報証明器３４は、以下の手順で（ｃ4 ，ｓ4 ）を計算する。
（ａ）乱数ｗ4 ∈Ｚq を生成する。
（ｂ）
【０１０５】
【数２７】
0003689292.tif 000029
【０１０６】
を計算する。
（ｃ）ｓ4 ：＝ｗ4 −ｃ4 τmod q を計算する。
処理５：制御部３１はｈp およびｃ4 ，ｓ4 を出力する。
【０１０７】
図６を参照し、検証装置について説明する。検証装置５は、メモリ５１、署名検証器５２、対応検証器５３、追跡情報検証器５４、署名抹消器５５および、これらを制御する制御部５６を具備する。検証装置５のメモリ５１には、Ｙ1 ，…，Ｙk ，ｇ，ｇ1 ，ｇ2 ，ｙ，ｙT ，ｐ，ｑが格納されている。制御部は各機器を以下のように制御する。
【０１０８】
・（署名検証ステップ）Ｉ：
公開掲示板からＬk を読み込み、リスト中の各エントリＭ＝｛ｓ2 ，ｃ2 ，ｓ3 ，ｃ3 ，ｍ，ｈp ，ｚp ｝を順次、署名検証器５２へ入力する。更に、ｇ，ｙ，ｑ，ｐを入力する。駆動された署名検証器５２は、
【０１０９】
【数２８】
0003689292.tif 000030
【０１１０】
を計算し、その結果をそれぞれｃ2 およびｃ3 と比較する。いずれも等しければ、署名検証器５２はＯＫを出力し、そうでなければＮＧを出力する。制御部５６は、署名検証器５２がＮＧを出力した場合に、リスト中におけるその不正な署名の位置（インデックス）をＪ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 に等しく、
【０１１２】
【数２９】
0003689292.tif 000031
【０１１３】
がＲi-1 に等しい場合にＯＫを出力し、そうでない場合にはＮＧを出力する。
・（追跡情報検証ステップ）Ｋ：
監視装置が出力したｈp ，ｃ4 ，ｓ4 およびｄ，ｇ1 ，ｇ2 ，ｙT ，ｑ，ｐを追跡情報検証器５４へ入力する。追跡情報検証器５４は
【０１１４】
【数３０】
0003689292.tif 000032
【０１１５】
を計算し、その結果がｃ4 と等しければＯＫを出力し、等しくなければＮＧを出力する。制御部５６は追跡情報検証器５４の出力を出力する。
【０１１６】
・（署名抹消ステップ）Ｌ：
ｈp およびＬk を署名抹消器５５へ入力する。署名抹消器５５は、Ｌk の中に、入力されたｈp と一致するｈp を含むＭが存在するか否かを調べ、存在しない場合はＯＫを出力し、存在するならば、そのＭのＬk 中での位置（インデックス）Ｊk を出力する。制御部５６はＯＫまたはＪk を公開掲示板６へ送信する。
【０１１７】
本実施例の投票装置は、以下の手順を順次実行する。
手順２１：各投票装置と署名装置とは以下のステップを順次実行する。
（ａ）投票装置１−ｉは、投票内容ｍが外部より入力されると、上述の（追跡情報埋込および証明ステップ）Ｃを実行し、（ｈw ，ｄ，ｃ1 ，ｓ1 ）を署名装置へ送信する。
（ｂ）署名装置２は、（ｈw ，ｄ，ｃ1 ，ｓ1 ）を受信して上述の（追跡情報埋込検証およびコミットステップ）Ａを実行し、（ｚw ，ｔ'g ，ｔ'h ）を投票装置１−ｉへ送信する。
（ｃ）投票装置１−ｉは、（ｚw ，ｔ'g ，ｔ'h ）を受信し、上述の（ブラインド処理ステップ）Ｄを実行してｃ'2 を署名装置２へ返信する。
（ｄ）署名装置２は、ｃ'2 を受信し、上述の（署名生成ステップ）Ｂを実行してｓ'2 を署名装置２へ返信する。
（ｅ）投票装置１−ｉはｓ'2 を受信し、上述の（暗号投票文作成ステップ）Ｅを実行してＲ0 ，Ｅ0 を公開掲示板６へ送信する。
【０１１８】
（暗号投票文作成ステップ）Ｅの説明にあるように、Ｅ0 は投票文ｍとそれに対して署名装置が発行した署名との対Ｍを多重に暗号化したものである。各投票装置１−ｉが公開掲示板６に送信した（Ｒ0 ，Ｅ0 ）からなるリストをＬ0 とする。
【０１１９】
手順２２：ｉ＝１，…，ｋに対して、Ｍｉｘ装置４−ｉは公開掲示板６からＬi-1 を読み込み、（Ｍｉｘ処理ステップ）Ｆを実行し、Ｌi を公開掲示板６へ送信する（前述の通り、Ｌk はＭのリストとなる）。
【０１２０】
手順２３：検証装置５は、上述の（署名検証ステップ）Ｉを実行する。ＯＫが出力されれば、正常終了であり、停止する。追跡インデックスＪk が出力された場合，以下のステップに進む。
【０１２１】
手順２４：以下の処理をｊ＝ｋ，…，１に対して順次繰り返す。
（ａ）検証装置５は、Ｊj をＭｉｘ装置４−ｊへ送信する。
（ｂ）Ｍｉｘ装置４−ｊは、検証装置５からＪj を受信し、上述の（対応証明ステップ）Ｇを実行し、Ｊj-1 ，Ｋj を検証装置５へ送信する。
（ｃ）検証装置５は、上述の（対応検証ステップ）Ｊを実行し、ＮＧが出力されたならば、Ｍｉｘ装置４−ｊが不正であると認定して停止する。
【０１２２】
手順２５：検証装置５は、Ｊ0 を監視装置３へ送信する。
手順２６：監視装置３は、Ｊ0 を受信し、Ｊ0 番目の投票装置が署名装置へ送信した（ｈw ，ｄ，ｃ1 ，ｓ1 ）のｈw を公開掲示板６より読み込んで上述の（追跡情報生成ステップ）Ｈを実行し、ｈp ，ｃ4 ，ｓ4 を検証装置５へ送信する。
【０１２３】
手順２７：検証装置５は、ｈp ，ｃ4 ，ｓ4 を受信し、上述の（追跡情報検証ステップ）Ｋを実行する。ＮＧが出力された場合、監視装置３が不正であると認定して停止する。ＯＫが出力された場合、Ｌk を読み込んで上述の（署名抹消ステップ）Ｌを実行する。ＯＫが出力された場合には、正常終了として停止する。インデックスＪk が出力された場合、以下を実行する。まず、得られたＪk が既に上述の（署名検証ステップ）Ｉの出力中に含まれていないことを確認する。含まれている場合には、この処理を終了する。含まれていない場合、手順２４以降を再度実行する。
【０１２４】
以上の動作によって得られたリストＬk において、検証装置５が公開掲示板６へ送付したすべてのインデックスＪk を抹消情報とし、これに該当する全ての投票を無効としたものが最終的な開票結果とする。
【０１２５】
上記では、検証装置５のみが他の装置の出力を検証する場合について説明したが、各装置が独立した安全性を確保できるよう、検証装置５が備える各検証機能を、各Ｍｉｘ装置４−ｉおよび監視装置３が具備し、同様の検証を行っても良い。
【０１２６】
上記では、全ての通信を公開掲示板６を通じて行う場合について説明したが、各装置間に通信路を設け、送信する全てのデータに送信側のディジタル署名を添付することによって、公開掲示板６の代替とする事も可能である。
【０１２７】
上記において、匿名電子投票装置および匿名電子投票処理方法について説明したが、当該匿名電子投票処理方法はプログラムの形で記述しておくことができかつ当該プログラムを記録媒体に記録しておくことができる。したがって、本発明は当該記録媒体自体をも発明の対象とするものである。
【０１２８】
【発明の効果】
以上説明した如く、本発明によれば、不正者を特定する手段を提供することによって、投票者あるいはＭｉｘサーバによる不正に対する抑止効果が得られる。
【図面の簡単な説明】
【図１】電子投票装置のブロック図を示す。
【図２】署名装置のブロック図を示す。
【図３】投票装置のブロック図を示す。
【図４】Ｍｉｘ装置のブロック図を示す。
【図５】監視装置のブロック図を示す。
【図６】検証装置のブロック図を示す。
【符号の説明】
１：投票装置
２：署名装置
３：監視装置
４：Ｍｉｘ装置
５：検証装置
６：公開掲示板
７：認証通信路
【図１】
0003689292.tif 000033
【図２】
0003689292.tif 000034
【図３】
0003689292.tif 000035
【図４】
0003689292.tif 000036
【図５】
0003689292.tif 000037
【図６】
0003689292.tif 000038