(57)【要約】電子投票プロセスでは、有権者（Ｖi）は投票総数の計算に使用される計算機ミックスネット（５０）の暗号化方式（ETM）で自身の投票（vi）を暗号化する。有権者（Ｖi）は管理サーバ（２０）から自身の暗号化投票(ｘi)の公正ブラインド署名(FBSS)を得る。暗号化投票(ｘi)は、出力(ci)を出すために、無作為抽出装置ミックスネット（４０）の暗号化方式(EM)を使用する管理サーバで、それの非ブラインドデジタル署名(yi)と共に再度暗号化される。有権者は出力（σi）を署名するため有権者自身の署名方式（si）を使用する。有権者はＩＤコードと(ci,σi)を有するデータとを掲示板サーバ（３０）に送信する。この投票データでの不一致は、検出でき、ＦＢＳＳの署名−追跡手段を使用して、正当性の証明を提供するため、無作為抽出装置ミックスネット（４０）で迅速にそれらの発生源を追跡できる。
2007526567.tif 000002
【特許請求の範囲】
【請求項１】
有権者の投票(vi)に具備されているデータ信号(xi)のデジタル署名(yi)を取得するために公正ブラインド署名方式を使用するステップを有することを特徴とする電子投票方法。
【請求項２】
前記公正ブラインド署名方式は、
複数サーバのグループのサブセットから取得される前記デジタル署名についてのしきい値公正ブラインド署名方式であり、前記複数サーバのグループがｎ個のサーバを有するとともに、前記サブセットがｔ個のサーバを有し、ｔ＜ｎである請求項１に記載の電子投票方法。
【請求項３】
前記データ信号(xi)は、第１暗号化方式(ETM)にしたがって暗号化された前記有権者の投票(vi)に対応し、
前記第１暗号方式は、第１ミックスネットワーク(TM)の暗号方式であるとともに、
前記方法は、前記有権者の投票(vi)を回収するために、前記第１暗号化方式の逆(inverse)の復号化方式(DTM)を前記データ信号(xi)に使用するステップをさらに有する請求項１又は２に記載の電子投票方式。
【請求項４】
暗号化されたデータ信号のバッチを第１順序で受信するステップであって、前記暗号化されたデータ信号(ci)のそれぞれが、第２暗号化方式(EM)にしたがって暗号化されたデータを有し、前記データが、それぞれデータ信号(xi)を有するステップと、
前記第２暗号化方式(EM)の逆の復号化方式(DM)を使用して、前記バッチにおけるそれぞれ暗号化されたデータ信号(ci)から各データ信号(xi)を回収するステップと、
前記第１順序とは異なる順序で、前記バッチについて回収されたデータ信号(xi)を出力するステップと
をさらに有する請求項３に記載の電子投票方式。
【請求項５】
前記第２暗号化方式は、第２ミックスネットワーク(M)の暗号化方式である請求項４に記載の電子投票方式。
【請求項６】
投票プロセスにおける不正（irregularities）を検出するステップをさらに有し、
前記不正を検出するステップは、数えられる投票が重複したデータ組を含まないことを確認することを有し、
前記データ組は、前記データ信号の一つとそれの前記デジタル署名とに相当する請求項５に記載の電子投票方式。
【請求項７】
前記投票プロセスにおける前記不正を検出するステップをさらに有し、
前記不正を検出するステップは、数えられるべき前記投票についてのデジタル署名の正当性を検査することを有する請求項５に記載の電子投票方式。
【請求項８】
前記投票プロセスにおける前記不正を検出するステップをさらに有し、
前記不正を検出するステップは、数えられた投票と取消しリストにおけるエントリとの間で重複がないことを検査することを有する請求項５に記載の電子投票方式。
【請求項９】
前記公正ブラインド署名方式にしたがうデジタル署名のために前記データ信号(xi)をサーバモジュール（ＡＳ）で受信するステップと、
受信信号の中のデジタル署名(si)が有効であることを、前記サーバモジュール（ＡＳ）によって確認するステップと、
前記データ信号(xi)の前記デジタル署名(yi)を生成するためにデジタル署名メッセージ(SAS(ei))のブラインドを除去するステップと、
暗号化されたデータ信号(ci)を生成するために前記第２暗号化方式(EM)にしたがって前記データ信号(xi)とその前記デジタル署名(yi)とを暗号化するステップと、
有権者（vi）の署名方式にしたがって前記暗号化されたデータ信号を署名するステップと
をさらに有し、
前記データ信号(xi)は、有権者（vi）によって選択された投票(vi)を有し、
前記投票(vi)は、前記第１暗号化方式(ETM)にしたがって暗号化され、且つ、前記公正ブラインド署名方式にしたがってブラインドされ、且つ、前記有権者のデジタル署名方式にしたがってデジタル署名され、
前記確認するステップにおいて、前記サーバモジュール（ＡＳ）によって、受信された信号の中のデジタル署名が有効であると確認された場合、前記サーバモジュール（ＡＳ）は、ブラインドされ暗号化された投票(ei)をデジタル署名するとともに、デジタル署名メッセージ(SAS(ei))を出力する請求項１から８のいずれかに記載の電子投票方式。
【請求項１０】
複数の有権者モジュール（１０）と、管理サーバモジュール（２０）とを有し、
前記有権者モジュール（１０）と管理サーバモジュール（２０）とは、各有権者の投票(vi)に具備されているデータ信号(xi)のデジタル署名(yi)を得るために、公正ブラインド署名方式のアプリケーションにおいて連携することを特徴とする電子投票システム。
【請求項１１】
有権者の投票(vi)に具備されているデータ信号(xi)のデジタル署名(yi)を得るために、公正ブラインド署名方式のアプリケーションにおいて管理サーバモジュール（２０）と連携するように構成された有権者モジュール（１０）。
【請求項１２】
コンピュータ装置が使用中であるとき、前記コンピュータ装置が請求項１１に記載の有権者モジュール（１０）となるように構成された命令セットを有しているコンピュータプログラム。
【請求項１３】
有権者の投票(vi)に具備されている データ信号(xi)のデジタル署名(yi)を得るために、公正ブラインド署名方式のアプリケーションにおいて有権者モジュール（１０）と連携するように構成された投票システム管理サーバモジュール（２０）。
【請求項１４】
コンピュータ装置が使用中であるとき、前記コンピュータ装置が請求項１３に記載の投票システム管理サーバモジュール（２０）となるように構成された命令セットを有しているコンピュータプログラム。
【請求項１５】
投票のバッチと、公正ブラインド署名方式にしたがってデジタル署名された各有権者の投票(vi)を有している暗号化されたデータ信号(ci)を有している各投票と、所定暗号化方式(EM)にしたがってそれぞれ暗号化されたデータ信号(ci)とを受信する入力手段と、
前記所定暗号化方式(EM)の逆の復号化方式(DM)を使用して、前記暗号化されたデータ信号(ci)を復号化するミックスネットワーク(M)と、
前記バッチにおける対応する暗号化されたデータ信号の順序とは異なる順序で、前記バッチの復号化された信号を出力する出力手段と
を有する投票システム無作為抽出装置モジュール（４０）。
【請求項１６】
コンピュータ装置が使用中であるとき、前記コンピュータ装置が請求項１５に記載の投票システム無作為抽出装置モジュール（４０）となるように構成された命令セットを有しているコンピュータプログラム。
【請求項１７】
投票と、公正ブラインド署名方式にしたがってデジタル署名されたデータ信号(xi)を有している各投票と、暗号化方式（ETM）にしたがって暗号化された各有権者の投票(vi)を有している各データ信号(xi)とを受信する入力手段と、
前記暗号化方式（ETM）の逆の復号化方式(DTM)を使用して、暗号化された投票(vi)を復号化するミックスネットワーク（Ｍ）と
を有する投票システム計算機モジュール（５０）。
【請求項１８】
コンピュータ装置が使用中であるとき、前記コンピュータ装置が請求項１７に記載の投票システム計算機モジュール（５０）となるように構成された命令セットを有しているコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号の分野に関するものであり、さらに具体的には、本発明は、電子投票に関するものである。
【背景技術】
【０００２】
有権者が投票するときに投票所に物理的に出席して投票する従来の投票とは異なり、電子または「オンライン」投票は、インターネットなどのネットワークに接続された適当な装置（コンピュータ、移動電話など）に補助された各有権者がリモート投票することを可能にする。
【０００３】
本明細書において、文脈上他の意味に解すべき場合を除き、「オンライン投票」と「電子投票」との表現が同義的に使用される、と理解される。
【０００４】
オンライン投票システムが従来の投票方式を満足に代替するものを構成するためには、下記の要件を留意することがオンラインシステムのために必要な一般検討事項である。
＜有資格＞：正規有権者の投票のみが票数計算に入れられなければならない。
＜非再利用性＞：各有権者は、１票のみが投票可能でなければならない。
＜匿名性＞：投票が秘密でなければならず、換言すれば、特定の有権者がどのように投票したかを知らせることが不可能であるべきである。
＜精度＞：票が一旦投じられると、それを変更することが不可能であるべきである。
＜公正性＞：全ての票が投じられた後にのみ投票結果を計算することが可能であるべきである（換言すれば、投票がまだ進行している間、部分的な集計を実行することが不可能であるべきである）。
＜簡易な手間での投票＞：有権者が一旦投票すると、その有権者が取らなければならない行動がこれ以上ない。
＜公衆の検証可能性＞：投票プロセス全体の正当性をだれでも容易に確認することができる。
【０００５】
多くの研究が確実で便利な電子投票システムを設計するために試みられた。確かに、電子投票は、暗号手法の主な用途の一つである。電子投票方式として知られている提案は、多くの場合ブラインド署名を利用する。
【０００６】
デジタル署名方式は、利用者と署名者とにかかわる暗号プロトコルである。利用者は、インターネットなどのネットワーク上で伝送するために一般にメッセージを出力する。署名者は、前記メッセージの正当性または真正性の証拠として、前記メッセージにデジタル署名を加える。従来のデジタル署名方式において、署名者は、デジタル署名が加えられているメッセージの内容を知っており、偽造することが困難または不可能なデジタル署名を生成するためにアルゴリズム（例えば、周知のＲＳＡアルゴリズム）が使用され、そして、デジタル署名の正当性は、署名者の公開鍵を使用することで、利害関係を持つあらゆる第三者によって確認することができる。
【０００７】
ブラインド署名方式では、署名者がメッセージの内容についての情報を取得することなく、利用者が自身のメッセージについてデジタル署名を得ることができる。明らかに、これは、メッセージが投票に対応して署名される投票アプリケーションとして望ましい特徴である。「Prof. Dr. David Chaum」によって開発された周知のブラインド署名方式は、「EP-A-0 139 313」に記載されている。ブラインド署名方式は、電子マネーを使用した後の追跡を可能とすることを金融機関が防ぐ方法において、個人が金融機関から電子マネーを取得することを可能とするために、電子マネーでの使用としてしばしば提案されている。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記のように、ブラインド署名を使用する各種の電子投票方式が提案されている。しかしながら、これらの従来の提案には、多くの欠点がある。いくつかの方式では、「簡易な手間での投票」の要件を満たさず、かわりに、全ての有権者が投票をした後に、各有権者が開票手続に参加しなければならない。いくつかの方式では、「簡易な手間での投票」の要件が尊重される場合、「精度」の要件が尊重されない。
【課題を解決するための手段】
【０００９】
本発明の好適実施形態は、通常のブラインド署名ではなく、公正ブラインド署名に基づく、効率的でかつ確実な電子投票方式を提供する。
【００１０】
通常のブラインド署名方式では、署名者が異なる利用者のために多くの書類に署名した場合、署名者が署名した１つの特定の書類を署名者に与えたとき、その書類をいつ、だれのために署名者が署名したか、署名者が判別できない。差異として、公正ブラインド署名方式（ＦＢＳＳ）では、１つ以上の信任された当局（または「判定者」）である追加関係者が存在し、さらに、与えられた署名セッションで生じた署名を、信任された権威（または信任された当局が複数である場合、信任された当局の定足数）の援助により、署名者が識別できる。
【００１１】
署名者が特定の署名セッションに関する写しを持っている場合、署名者は、そのセッションから生じる署名−メッセージの組を識別できる。これは「署名追跡」と呼ばれる。逆に、署名者が署名−メッセージの組を使用可能である場合、署名者は、これが生成された署名セッションを判別できる。これは「セッション追跡」と呼ばれる。公正ブラインド署名方式は、与えられたデジタル署名を与えられた利用者にリンクすることを可能にするが、一般に、利用者のメッセージは、まだ私有(private)のままで残っている。公正ブラインド署名方式は、組織的犯罪を敵として戦う状況で主に提案されており、特にマネーロンダリングの防止に提案されている。
【００１２】
本発明の好適実施形態は、従来技術の問題点を解消するために公正ブラインド署名方式を使用する電子投票方式であって、上記要件である匿名性と、有資格と、非再利用性と、精度と、公正性と、簡易な手間での投票と、公衆の検証可能性とを尊重し、効率的で且つ確実な電子投票方式を提供する。
【００１３】
本発明は、有権者の投票に具備されている信号のデジタル署名を取得するために公正ブラインド署名方式を使用するステップを有する電子投票方法を提供する。通常、デジタル署名は、「管理サーバ」モジュールとして指定されることができるサーバモジュールで使用される。
【００１４】
本発明の好適実施形態では、前記公正ブラインド署名方式は、ブラインド署名がｎ個の管理サーバのｔ個の出力の連携によって生成されるしきい値公正ブラインド署名方式であり、さらに、特定の投票をした有権者（しかし有権者が投票した方法ではない）は、ｎ個の信任された当局のｒ個の出力の連携によって識別できる。
【００１５】
好適なものとして、管理サーバのセットから得られたデジタル署名は、前記グループにおいてサーバのn-t+1個が正当である限り、一つ以上が非偽造可能となっている。
【００１６】
一般に、前記信号は、第１暗号化方式（特に、投票総数を計算するために使用される計算機モジュール）にしたがって暗号化された有権者の投票に対応している管理サーバモジュールによって署名される。そこで、この場合、前記電子投票方法は、前記有権者の投票を回収するために、前記第１暗号化方式の逆の復号化方式を前記データ信号に使用するステップをさらに有する。望ましくは、計算機モジュールはミックスネットワークとして実行される。
【００１７】
本発明の好適実施形態によれば、データ信号は、有権者の暗号化された投票を有し、第２暗号化方式（特に、無作為抽出装置モジュールのもの）にしたがってそれ自身暗号化されており、さらに、この暗号化されたデータ信号は、有権者が自身の票を投票することとして電子投票箱に送信される。好適なものとして、暗号化されたデータ信号のバッチは、復号化と再配置（有権者の身元が、投票リストにおける有権者の位置の考察によっても判別できないように）のために無作為抽出装置モジュールに供給される。望ましくは、無作為抽出装置モジュールはミックスネットワークとして実行される。
【００１８】
上記本発明の好適実施形態に係る電子投票方法において、ミックスネットワークサーバは、通常、それらの動作（それの出力がそれらの入力の一つを再配置ものに実際に一致することを認証する）の正当性の証明を生成する必要がない。そのような証明は、投票プロセスの中で不一致が認識された場合にのみ必要である。したがって、正当な投票の場合（有権者またはミックスネットワークサーバが不正行為をしない場合）、開票が非常に迅速となる。
【００１９】
本発明の更なる特徴および利点は、添付図面で示すように、一例として挙げられた、それらの好適実施形態の説明から明らかとなる。
【発明を実施するための最良の形態】
【００２０】
本発明の電子投票方法は、６個の基本タイプの関係者を有する。
有権者、
管理サーバまたは「選挙当局」（望ましくは、１組の管理サーバを使用して実行される）、
ランダム化手段(entity)（望ましくは、ランダム化ミックスネットワークで実行される）、
投票箱サーバ、
計算機（望ましくは、計算機ミックスネットワークの投票集計サーバ）、および
ｎ個の信任された当局（または「審査員(judge)」）。
【００２１】
一定の有権者が記号Ｖiの使用および識別コードを持つことで指定されることができる。前記識別コードとしては、Ｉｄiを指定できる。一定の有権者Ｖiは、一定の投票プロセスに参加する資格を該有権者が持つことを示すために、該有権者が送信するデータに証明書Ｃiを添付することができる。
【００２２】
図１は、本発明の一好適実施形態における各種の関係者の相互作用を概略的に示す図である。
【００２３】
図１に示すように、本発明の好適実施形態の電子投票方式によれば、有権者１０は、公正なブラインド(blind)署名方式（ＦＢＳＳ）にしたがって、暗号化された投票データのデジタル署名を得るために、管理サーバモジュール２０と接触する。有権者が投票するとき、前記デジタル署名がされた投票データが掲示板サーバ３０に提供される。この投票データは、２重に暗号化されている。前記暗号の外層は、無作為抽出装置モジュール４０の暗号方式にしたがっており、前記暗号の内層は、計算機モジュール５０の暗号方式にしたがっている。無作為抽出装置モジュール４０は、（一つの）暗号化されたフォームを残して、前記投票を復号化するとともに、各有権者から受信した投票の順序をランダム化する。計算機モジュール５０は、前記（一つの）暗号を復号化するとともに、投じられた票を回収するために投票を再配置し、投票を集計するとともに、投票結果を出力する。
【００２４】
管理サーバモジュール２０は、デジタル署名を有する有権者から受け取ったデータのデータベースＬＡＳの保守をする。掲示板サーバ３０は、票を投じた有権者から受け取ったデータのデータベースＬＢＢの保守をする。
【００２５】
投票プロセスにおける各段階での不一致（または「異常」）は、検出できる（例えば、掲示板サーバ３０、無作為抽出装置モジュール４０または計算機モジュール５０において）。異常が有権者に起因することが特定されている場合、信任された当局６０のセットは、（一つの）暗号化された投票データであって前記異常による影響を受けたデジタル署名データに対応したものを判別可能となるように、公正ブラインド署名方式が関係付けられる動作を助けることに任命される。無作為抽出装置モジュール４０がミックスネットワークとして実行される場合では、異常が投票プロセスにおいて検出された場合に、正当性（特に、正当性のゼロ知識(zero-knowledge)証明）を証明するものを生成するミックスネットワークサーバのみが必要となる。異常が前記投票プロセスで検出されない場合、無作為抽出装置モジュール４０のミックスネットワークサーバが正当性を証明するものを生成する必要はない。これは、本発明の好適実施形態に係る電子投票プロセスであって、高速に投票結果を出すものを示している。
【００２６】
本発明の好適実施形態に係る投票方法は、以下の暗号基本要素を有する。デジタル署名方式（有権者１０に適用される）と、公正なブラインド署名方式（有権者と、１組の管理サーバを使用して実現される管理サーバモジュール２０と、信任された当局６０のセット）の閾値と、２つのミックスネットワーク（無作為抽出装置モジュール４０を実現する１つのミックスネットワークと計算機モジュール５０を実現する１つのミックスネットワーク）と、２つの暗号方式（無作為抽出装置ミックスネットワーク４０のものと計算機ミックスネットワーク５０のもの）。
【００２７】
本発明の好適実施形態に係る電子投票プロセスについての以下の説明では、なにか特定の実現方式の詳細は挙げずに、使用される前記暗号基本要素は、概括的に示されている。これは本発明は、これらの各種基本要素が実行される特定方法に関して、限定されないからである。多数のデジタル署名方式と、公正なブラインド署名方式の閾値と、ミックスネットワークと、暗号方式とは、暗号の分野で周知であるとともに、これらのいかなる安全な実施が本発明における使用に適合する。
【００２８】
同様の方法で、本発明は、各種の表現(described)機能を実行するのに使用される特定のハードウェアまたはソフトウェアに関して無制限に適用可能である。適当なソフトウェアルーチンおよびハードウェアは、当業者によれば容易に作成できる。
【００２９】
本発明の一好適実施形態に係る前記投票方法について、図２から５を参照して説明する。この投票方法は、登録段階と、投票段階と、開票段階の３つの主要段階をもつ。
【００３０】
前記登録段階は、有権者が投票権を行使するために、有権者Ｖiが管理サーバＡＳまたは選挙当局(electoral authority)と対話することを有する。この対話の結果、管理サーバは、今後の選挙に参加可能な有権者の選挙人名簿に有権者Ｖiを加える。登録段階における有権者と管理サーバとの間の対話は、あらゆる好都合な形をとることができる。有権者は、例えば、電子的手段によって、直接管理サーバと連絡してもよく、または、例えば、電話ベースの音声操作の応答システムを使用して、または、管理サーバで保持された選挙リストを更新する選挙委員に完成した書類(form)を郵送することによって、間接的に管理サーバと連絡してもよい。あらゆる好都合なタイプの何らかの安全対策は、真に投票権を与えられた人のみが管理サーバの選挙人名簿に記録されることができることを、確保するために、有利に採用されている。
【００３１】
登録段階において、有権者は、自身がメッセージに署名することを可能にする証明書Ｃiを入手する。この証明書はあらゆる好都合な形をとることができる。例えば、その証明書はＸ５０９証明書とすることができる。証明書Ｃiは、投票段階において有権者によって使用される。
【００３２】
本発明に係る電子投票方法の好適実施形態における投票段階につて、図２のフローチャートを参照して説明する。
【００３３】
有権者Ｖiは、自身の選択ｖiの投票を選択するとともに、この投票を計算機の暗号化キーを使用して暗号化する。すなわち、計算機が投票プロセスの結果を計算することに携わる手段(entity)となる。あらゆる好都合な非対称アルゴリズム（ＲＳＡ，エルガマ（Ｅｌ  Ｇａｍａｌ）など）が前記計算機の暗号化方式として使用できる。
【００３４】
本発明の好適実施形態における前記計算は、複数サーバ（または「混合（mixes）」）のシーケンスから成るミックスネットワークＴＭとして実行される。ミックスネットワークの各サーバは、入力メッセージのバッチを受信するとともに、前記バッチの順序を並べ換えた出力を生成する。計算機ミックスネットワークは、各種のタイプとすることができ、例えば、ショーマイアン(Chaumian)ミックスネットワーク（すなわち、メッセージが各サーバのキーで逐次暗号化されるミックスネットワーク）、再暗号化ミックスネットワーク（それについては、ミックスネットワークにおける全サーバに対しての単一キーであるが、各サーバにおいて再暗号化についてランダム化される）などがある。望ましくは、計算機ミックスネットワークは、シンプル・ミックスネットワークであるが、それは強健なものとする（すなわち、一つの計算サーバが使用不能である場合、それは別のものに取り換えることが可能である）。
【００３５】
前記プロセスは、有権者が前記計算機ミックスネットワークＴＭの暗号化キーを使用して自身の投票を暗号化するので、以下の数１のように表すことができる。
【００３６】
【数１】
2007526567.tif 000003
【００３７】
ここで、Ｘiは暗号化された投票であるとともに、ETMは計算機ミックスネットワークＴＭの暗号化方式のアプリケーションを表す。
【００３８】
そのとき有権者Ｖiは、以下の数２のように、前記暗号化された投票ｘiを隠蔽（ブラインド）する。
【００３９】
【数２】
2007526567.tif 000004
【００４０】
ここで、ＦＢはブラインド処理手順のアプリケーションを表すとともに、ｒiは無作為に選択されたブラインド要素である。
【００４１】
有権者Ｖiは、自身のデジタル署名方式Ｓiを使用し、真正性の判断基準として、ブラインドされ且つ暗号化された前記投票ｅiに署名する。すなわち、有権者は、下記の数３を生成する。
【００４２】
【数３】
2007526567.tif 000005
【００４３】
そして、前記有権者Ｖiは、データ(Idi,Ci,ei,si)を管理サーバＡＳに送信する。
【００４４】
前記管理サーバＡＳは、署名siが有効であるか検査するとともに、選挙人名簿に示された有権者から来たか検査する（この検査は、証明書Ｃiの正当性を確認することで実行される）。また、管理サーバは、この有権者がまだ投票していないことを検査する。後者の検査は、管理サーバＡＳが現在の選挙においてこの有権者Ｖiについて既に生成されたデジタル署名を持っているか否かを、判断することを有する。
【００４５】
これらの検査が満足できる結果をもたらす場合、管理サーバＡＳは、そのデジタル署名方式SASを使用し、真正性の判断基準として、ブラインドされ且つ暗号化された前記投票ｅiに署名する。すなわち、管理サーバは、下記の数４を生成する。
【００４６】
【数４】
2007526567.tif 000006
【００４７】
前記管理サーバは、有権者Ｖiへ戻し（back）ｄiを伝送する。
【００４８】
管理サーバＡＳは、投票プロセスにおいてデジタル署名を出す全ての有権者から受信したデータ(Idi,Ci,ei,si)の記録を保持する。投票段階の最後では、管理サーバＡＳは署名された投票を持つ有権者の数を発表するとともに、これらの有権者の全てに受信されたデータを有するリストＬAS＝(Idi,Ci,ei,si)を出す(publishes)。
【００４９】
有権者Ｖiが戻しｄi（すなわち管理サーバによって署名された自身のブラインド投票）を受信したとき、有権者は、以下の数５のようなブラインド除去ｄiによって自身の投票（ｘi）のデジタル署名バージョン（ｙi）を取り出す。
【００５０】
【数５】
2007526567.tif 000007
【００５１】
ここで、ＵＦＢは、ブラインド除去処理手順のアプリケーションを表す。
【００５２】
その後、有権者Ｖiは、自身の暗号化された投票に対応する暗号化データ(xi,yi)に、ランダム化手段の暗号化キーＥＭを使用するとともに、自身の暗号化された投票のバージョンは、以下の数６のように管理サーバＡＳによって署名される。
【００５３】
【数６】
2007526567.tif 000008
【００５４】
このランダム化手段は、ミックスネットワークＭとするのが好適であり、重ねて、ショーマイアン・ミックスネットワーク、ランダム化ミックスネットワークなどが実行できるものであって、簡素であるが強健なミックスネットワークが望ましい。
【００５５】
その後、有権者は、下記の数７に示すように、署名メッセージσiを生成するために自身の署名機能Ｓiを使用してこの暗号化されたデータに署名する。
【００５６】
【数７】
2007526567.tif 000009
【００５７】
その後、有権者は、電子投票箱ＢＢにデータ(Idi,Ci,ei,σi)を送信して自身の投票を終了する。この電子投票箱は、速報板として好適に公開されているとともに、ウェブサーバ（またはその他）で実行される。前記速報板は、前記署名σiの正当性を確認するとともに、それが正当である場合、この伝送で提供されたデータ(Idi,Ci,ei,σi)を記録する。望ましくは、このデータは、後の変更に耐性のある形でウェブサーバ（またはその他）で記録される（例えばリードオンリーメモリ）。
【００５８】
投票プロセスが終了したとき（すなわち投票が）、速報板ＢＢは、有効な有権者の署名を伴って、伝送における投票段階の間に出された全データのリストＬBB＝(Idi,Ci,ei,σi)を出す。このリストＬBBは、前記投票段階の間備えられている全てのデジタル署名に関して生成されたデータＬＡＳのリストと、管理サーバで比較される。ＬＡＳにおけるエントリ(Idi,Ci,ei,si)がＬBBにおけるエントリ(Idi,Ci,ei,σi)に対応しない場合、本手段では、有権者が自身の暗号化された投票のブラインドデジタル署名を取得するが、前記投票は投票されない（無効となる）。その後のステップでは、対応するメッセージ−署名の組(xi,yi)を判別できるように、処理ｅｉが行われる。特に、信任された当局（または判定者）は、処理ｅｉを援助するために連絡される。
【００５９】
本発明の実施形態によれば、信任された当局がｎである場合、処理ｅｉに協力することに信任された当局の完全なセットＪは必要ではない。信任された当局のサブセットの協力（すなわち、数ｔ、ｔ＜ｎ）で、十分である。このように、前記方式は、信任された当局Ｊの１つまたはわずかな数が所定時間に連絡できないまたは協力を拒否する場合でも実行可能である。この信任された当局のサブセットは、下記に数８のような、投票プロセスで使用されている公正ブラインド署名方式の署名追跡アルゴリズムREVJを使用する。
【００６０】
【数８】
2007526567.tif 000010
【００６１】
それにより、有権者Ｖiの暗号化された投票ｘiのブラインドバージョンであるｅiが回収される。
【００６２】
適用された特定の公正なバインド署名方式によって、検索されたデータfiは、メッセージ−署名の組(xi,yi)自体とすることができる。以下の説明では、検索されたデータfiはメッセージ−署名の組(xi,yi)と仮定する。回収されたメッセージ−署名の組(xi,yi)データは、望ましくは後で公衆の閲覧が可能で」あって、「取消しリスト」と名付けられるリストＲＬに記録される。検索されたデータは、それについて暗号化されたバージョンのみであり、有権者の投票を明るみに出さないことに留意すべきである。その結果、有権者のプライバシーが尊重される。
【００６３】
本発明の好適実施形態に係る電子投票プロセスの開票段階は、図３から５のフローチャートを参照して説明される。
【００６４】
図３のステップ１に示されているように、前記速報板サーバによって記録されたｃi値のリストは、署名−メッセージの組(xi,yi)を回収するために、複合化方式ＤMを利用する無作為抽出モジュールＭに供給される。上記のように、本発明の好適実施形態において無作為抽出モジュールがミックスネットワークで実行される。このミックスネットワークは、対応値ｃiの受け入れ順序とは異なる形で、かつ不規則な順番で値(xi,yi)のリストＬを出力する。そして、前記リストＬは、本発明の好適実施形態においてミックスネットワークとして実行される計算機モジュールＴＭに供給される。
【００６５】
図３のステップ２に示されているように、計算機ミックスネットワークは、何らかの重複エントリについてリストＬを検査する。この検査は、計算機ミックスネットワーク自身で、または計算機ミックスネットワークと連携する他のモジュールで、することができる。何らかの重複エントリが発見された場合、これは投票手続きにおける異常を示す不一致である。そこで、図４に関連して以下で説明される不一致追跡(tracing)処理手順が呼び出される。前記の場合ではない、リストＬにおいて重複エントリがない場合、リストＬにおけるエントリのデジタル署名ｙiの正当性を検査する図３のステップ３に進む。そして、デジタル署名yiのいずれかが不正である場合、再び、図４の不一致追跡処理手順が呼び出される。
【００６６】
計算機が判断する前記場合では、全てのデジタル署名yiが正当であり、Ｌにおけるエントリ(xi,yi)と取消しリストＲＬにおけるエントリ(xi,yi)との比較を実行する（図３のステップ４参照）。２組のエントリ間で重複がある場合、換言すれば、ＬとＲＬとの積集合が空集合ではない場合、図４の不一致追跡処理手順が呼び出される。そうでなければ、計算機ミックスネットワークのサーバＴＭｊは、信号ｘiを複合化することができるように、それらの秘密鍵を明らかにする。これにより、投票viが明らかにされ、計算機モジュールが選挙結果を発表する時にそれらを計算する（図３のステップ６参照）。これで開票段階が終了する。
【００６７】
上記に示されているように、ステップ２，３または４において計算機モジュールによって実行される不一致を明らかにする検査の場合では、不一致の原因が図４の不一致追跡を使用して探し出される。
【００６８】
図４の不一致追跡処理手順では、無作為抽出ミックスネットワークＭのサーバで不一致が発生するか否かが最初に検査される。この検査は、入力における質問データの組(xi,yi)qを使用するとともに、ミックスネットワークのバックトレース(back-tracing)アルゴリズムを適用して、それらの出力と入力との間の整合性を証明する正当性のゼロ知識証明を生成するために、各ミックスサーバＭｊで迅速に実行される。ところで、計算機がリストＬにおいて１つ以上のエントリーの重複を発見したので、前記不一致追跡処理手順が呼び出されている場合、前記質問データの組(xi,yi)qは、重複エントリーとなる。計算機が不正デジタル署名yiを発見したので、前記不一致追跡処理手順が呼び出されている場合、前記質問データの組(xi,yi)qは、これらの不正デジタル署名を有するデータ組となる。計算機がＬとＲＬとの間の重複を発見したので、前記不一致追跡処理手順が呼び出されている場合、前記質問データの組(xi,yi)qは、前記重複による影響を受けたデータ組となる。
【００６９】
全てのミックスネットワークが満足できる知識の証明を生成できる場合、前記不一致は、ミックスネットワークサーバで生じるのではなく、前記有権者で生じる。したがって、図５を参照して以下で説明するように、不一致追跡プロトコル（不正行為有権者を推定するもの）の各部分が呼び出される。
【００７０】
ミックスネットワークサーバの一つが満足できる知識の証明を生成できない場合、満足できる知識の証明を生成できなかったミックスサーバが不正行為をしているミックスサーバであるとの推定に基づいて、図４の不一致追跡処理手順が続けられる。このミックスサーバは、不適格とみなされる。このミックスネットワークＭにおける他のミックスサーバは、ＳＫＭをもたらすそれらの秘密鍵をここで明らかにしなければならない。前記速報板サーバによって記録されたデータｃiは、ＳＫＭを使用してここで復号化されるとともに、リストＬの新バージョンが全ての復号化されたデータ組(xi,yi)を有して生成される。このリストＬは、計算機ＴＭに送信される。
【００７１】
この場合、前記計算機ミックスネットワークＴＭは、前記投票データの復号化と同様に、前記エントリ(xi,yi)の順序を並べ換える。さらに、この場合、前記計算機ミックスネットワークのサーバＴＭｊは、それらがそれらの入力を正しくミックスし、且つ復号化したことの各証明の生成を促される。これは、前記開票段階の所要時間を増加させるとともに、コストを増加させる。しかしながら、これらの証明の生成が不正のない選挙の場合不要となることに留意する。一旦、投票データが復号化されると、それはカウントされるとともに、前記計算機が選挙結果を発表する。これで開票段階が終了する。
【００７２】
ところで、無作為抽出装置モジュール４０が署名−メッセージの組を復号化することのみに使用されるとともに、それらの順序をランダム化しない場合、モジュール４０のサーバがそれらのキーを明らかにすることを強いられた（モジュール４０の動作から異常が生じていることを検出するために）ことが、前記の場合での潜在的な問題となる。このような場合には、前記キーが明らかにされたとき、モジュール４０に入力されたリストＬにおける第１エントリとモジュール４０によって出力された署名−メッセージの組のリストにおける第１エントリとの間で直接通信される。モジュール４０に入力されたリストが各有権者を識別するコードを有しているという事実を考慮すると、これは投票プロセスの匿名性を害する。
【００７３】
その一方、図５の不一致追跡処理手順が呼び出された場合（前記不一致が、ランダム化ミックスネットワークにおけるサーバの動作ではなく、有権者の動作から生じると推定される場合）、不正投票データが処理されて前記データから排除されるなら、計算機ミックスネットワークＴＭの通常動作を維持することができる。
【００７４】
特に、図５に示されているように、有権者に起因する異常の場合では、前記質問データの組(xi,yi)qを使用するランダム化ミックスネットワークＭのバックトレース・アルゴリズムを実行して、不正行為をしている有権者の身元を明らかにすることができる。これは、速報板サーバＢＢにデータｃｉｊ，σｉｊを送信した有権者の識別子Idijをもたらす。
【００７５】
一旦、不正行為をしている有権者の識別子が明らかにされると、前記公正ブラインド署名方式の署名−追跡手段がIdijに対応するデータの組(xij,yij)を識別するために使用される。このデータの組(xij,yij)は、取消しリストＲＬに加えられるが、数えられるべき投票のリストＬから外される。次いで、前記処理手順は、図３のステップ３に戻ることができる。
【００７６】
不正投票がないとき、各種のミックスサーバは、それらの動作の正当性の証明を生成することが不要となることがわかる。これは、投票を非常に速く開票することに通じる。そのうえ、このシステムでは不正行為をしているミックスサーバが常に検出されるので、不正行為が成功する見込みがない。したがって、本発明の電子投票方式は、極めて迅速な選挙結果の取得をもたらす。
【００７７】
本発明の電子投票方式のセキュリティについて検討すると、以下の留意事項が挙げられる。
【００７８】
用意されたデジタル署名方式は、破壊することができない本発明の電子投票方式の中で使用するために選択されるので、被選挙資格および非−再使用可能性の原理が本方式では尊重される。
【００７９】
少なくとも１つのミックスサーバが正常であるとともに、信任された当局のn-t+1が正常である場合、有権者の匿名性は保護される。
【００８０】
本発明の好適実施形態は、管理サーバのn-t+1が正常である限り、署名が１つ以上非偽造可能なデジタル署名方式を使用して実行するのが好適である。このような場合には、有効データの組(xi,yi)が生成できない。したがって、精度の原理が尊重される。
【００８１】
前記計算機は、計算機モジュールがミックスネットワークとして実行されているので、開票段階が進行している間前記投票を復号化することができない。したがって、公正の原理が尊重される。
【００８２】
有権者は、自らの投票の開票、または自らの投票を数えることを可能にするために、いかなる特別な行動をも取る必要がない。したがって、「投票に行く(vote and go)」の原理が尊重される。
【００８３】
本発明の好適実施形態では、リストＬAS,ＬBB,ＬおよびRLは、全部のプロトコルの最後に公表される。さらに、開票段階の全ステップ（前記バックトレース処理手順を有する）を発表することができる。これは、本当は無効なものであって破棄された投票のみを検査することと、選挙結果が有効投票と一致していることの確認とが、いかなる利害関係人でも可能となる。したがって、公衆の検証可能性の原理が尊重される。
【００８４】
上記プロセスでは、前記公正ブラインド署名方式がしきい値公正ブラインド署名方式であることが好ましい。そのような方式は、周知であるので、ここでは詳細に説明しない。
【００８５】
本発明は、その特定の好適実施形態の観点から説明されたが、前記好適実施形態の各種特徴は、特許請求の範囲で定義されている本発明から逸脱することなく、他のものに変更、アレンジおよび／または置換が可能であることが、当業者は容易に理解できる。
【００８６】
例えば、前記好適実施形態は、通常、利用者自身の家で利用者によるオンライン投票の観点から説明されたが、状況次第では有権者の物理的位置は重要ではなく、従来の投票所で本発明を使用することの想定が可能であると、理解される（例えば、固定されていなくともよい）。
【００８７】
同様に、本発明は、前記システムの関係者間の各種信号の通信に使用されるメカニズムに関しては特に限定されない。通常、電気通信網およびインターネットが、前記利用者と、前記最初のミックスネットワークのミックスサーバと、前記管理サーバとの間の通信に使用される。しかしながら、他のネットワークを使用することもできる。状況次第では、前記システムの関係者間で交換された信号が記録媒体に記録されて、それらの関係者間で物理的に移送されることとして、確実に実行可能とすることができる。
【００８８】
本発明のオンライン投票技術は、選挙、住民投票(referendum)、世論調査などであるか否かに関係なく、いかなる種類の投票にも適用できることが理解される。
【図面の簡単な説明】
【００８９】
【図１】本発明の好適実施形態に係る電子投票方式の主要参加者を概略的に示す図である。
【図２】本発明に係る電子投票方法の好適実施形態の投票段階における主要ステップを概略的に示す図である。
【図３】本発明に係る電子投票方法の好適実施形態の開票段階における主要ステップを示すフローチャートである。
【図４】開票段階において留意される処理の不一致に対する処理手順の主要ステップを示すフローチャートであり、特に、前記不一致がランダム化ミックスネットワークにおけるサーバに起因する場合を示す図である。
【図５】開票段階において留意される処理の不一致に対する更なる処理手順の主要ステップを示すフローチャートであり、特に、前記不一致が有権者に起因する場合を示す図である。
【符号の説明】
【００９０】
１０  有権者、有権者モジュール
２０  管理サーバモジュール
３０  掲示板サーバ
４０  無作為抽出装置モジュール
５０  計算機モジュール
６０  信任された当局
【図１】
2007526567.tif 000011
【図２】
2007526567.tif 000012
【図３】
2007526567.tif 000013
【図４】
2007526567.tif 000014
【図５】
2007526567.tif 000015
【国際調査報告】
2007526567.tif 000016
2007526567.tif 000017