JP4630144B2

JP4630144B2 - 電子投票装置、開票装置、電子投開票システム、電子投開票方法並びにプログラム

Info

Publication number: JP4630144B2
Application number: JP2005199239A
Authority: JP
Inventors: 幸太郎鈴木; 英一郎藤崎
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 2005-07-07
Filing date: 2005-07-07
Publication date: 2011-02-09
Anticipated expiration: 2025-07-07
Also published as: JP2007019872A

Description

本発明は、情報セキュリティ技術に関するものであり、詳しくは電子投開票技術に関する。

従来的な電子投開票技術の代表的な例として、選挙管理者が投票にブラインド署名を付けることにより匿名性と一人一票を実現する方式がある（例えば非特許文献１参照。）。以下に、その電子投開票方法の概要を説明する。

[準備]
選挙管理者Ａは、ブラインド署名の署名鍵と検証鍵を生成し、検証鍵を公開する。

［投票］
投票者ｉ∈Ｎ（Ｎは、投票者の集合を表す。）は、投票内容ｍをマスキングしたものであるＭを選挙管理者Ａに送る。ここで選挙管理者Ａとは、人間ではなく、所定の機能（ブラインド署名の付与）を実現するサーバである。
選挙管理者Ａは、投票者ｉ∈Ｎを所定の方法（例えば本人確認など）で認証し有権者であることを確認したら、ブラインド署名σ（Ｍ）を生成し投票者ｉ∈Ｎに送る。投票者ｉ∈Ｎは、受信したブラインド署名σ（Ｍ）からマスクを外し選挙管理者Ａの署名σ（ｍ）を得て、投票内容ｍおよび署名σ（ｍ）を、匿名通信路を経由して公開掲示板Ｂに公開する。ここで公開掲示板Ｂとは、例えば端末装置からアクセスを受けた場合に、所定の情報を提供することのできるサーバである。
ブラインド署名としては、例えばＲＳＡ暗号に基づく方式などがある（例えば非特許文献２参照。）。

［開票］
開票者は、公開掲示板Ｂに公開された選挙管理者Ａの署名σ（ｍ）を検証鍵で検証し、検証に合格した投票内容ｍおよび署名σ（ｍ）を投票結果として公開する。

この方式では、ブラインド署名の性質から、（Ｍ，σ（Ｍ））と（ｍ，σ（ｍ））とを関連付けることができないので、匿名性を実現することができる。また、ブラインド署名σ（ｍ）を偽造することができないので、一人一票を実現することができる。
Atsushi Fujioka, Tatsuaki Okamoto, Kazuo Ohta, A Practical Secret Voting Scheme for Large Scale Elections, ASIACRYPT 1992, 244-251. 岡本龍明、山本博資著、「シリーズ／情報科学の数学現代暗号」、初版、産業図書株式会社、１９９７年

しかし、従来的な電子投開票方式においては、信頼できる選挙管理者Ａという電子投開票のための特別なサーバが必要である。信頼できるサーバを実現するためには分散実装などコストがかかるため、一回の投票のためだけに信頼できるサーバを設置するのは不経済であり、電子投開票を簡単に行なえないという問題点があった。

そこで、本発明は、選挙管理者を必要としない電子投票装置、開票装置、電子投開票システム、電子投開票方法並びにプログラムを提供することを目的とする。

上記課題を解決するために、本発明では、電子投票装置によって、公開鍵基盤において公開鍵証明書が与えられた全投票者の公開鍵および各投票者に固有の秘密鍵を用いて投票内容に対する署名を生成し、この署名（投票署名）をもって電子投票を行う。開票については、開票装置によって、電子投票装置から電子投票された投票署名に対して、公開鍵基盤において公開鍵証明書が与えられた全投票者の公開鍵を用いた検証を行い、検証に合格した投票署名を計数することで行う。また、公開鍵基盤において公開鍵証明書が与えられた全投票者の公開鍵、投票内容、さらには投票署名を、情報公開サーバで公開しておく。

また、電子投票装置においては、投票者に固有の秘密鍵および全投票者の公開鍵を用いて、投票者に固有の固有臨時公開鍵を生成し、固有臨時公開鍵および全投票者の公開鍵を用いて撹乱因子を生成し、さらに、撹乱因子および全投票者の公開鍵を用いて、全投票者数から１を引いた数の撹乱臨時公開鍵を生成するとし、この固有臨時公開鍵および撹乱臨時公開鍵を用いて投票内容に対する署名情報を生成して、この署名情報および撹乱因子からなる組を投票内容に対する署名（投票署名）としてもよい。なお、固有臨時公開鍵および撹乱臨時公開鍵は、撹乱因子から生成されるものであり、固有臨時公開鍵と撹乱臨時公開鍵との判別が不能である。開票については、所定の投票内容に対する全ての投票署名について、投票署名ごとに、臨時公開鍵（固有臨時公開鍵と撹乱臨時公開鍵）を生成し、この臨臨時公開鍵および全投票者の公開鍵を用いて、臨時公開鍵が生成された投票署名の検証を行い、検証に合格した投票署名を計数するようにする。

また、本発明の電子投票装置、開票装置をコンピュータ上で機能させる電子投票プログラム、開票プログラムによって、コンピュータを電子投票装置、開票装置として作動処理させることができる。

本発明によれば、公開鍵基盤において公開鍵証明書が与えられた全投票者の公開鍵および各投票者に固有の秘密鍵を用いて投票内容に対する署名を生成し、この署名（投票署名）をもって電子投票を行い、開票については、開票装置によって、電子投票装置から電子投票された投票署名に対して、公開鍵基盤において公開鍵証明書が与えられた全投票者の公開鍵を用いた検証を行い、検証に合格した投票署名を計数することで行うので、電子投開票のための特別なサーバ（選挙管理装置）を用いることなく電子投開票を実現することができる。

また、固有臨時公開鍵および撹乱臨時公開鍵を生成し、これらが撹乱因子から生成可能であるが、固有臨時公開鍵と撹乱臨時公開鍵との判別が不能であるとすることで、少なくとも開票においては、投票署名に含まれる撹乱因子から生成される臨時公開鍵のいずれが固有臨時公開鍵であるか判別不明であるため匿名性が実現でき、さらには、臨時公開鍵に固有臨時公開鍵が含まれるから、各投票署名から生成されたた臨時公開鍵を比較することで重複投票の排除（一人一票）を実現できる。

＜第１実施形態＞
本発明の第１実施形態を以下に説明する。
まず、Ｇを離散対数問題の難しい素数位数ｑの巡回群とし、ｇをその生成元とする。巡回群Ｇの例としては、例えば乗法群Ｚ_ｐ ^＊〔ｑ＝ｐ−１〕、楕円曲線上の点で定義される群などが上げられる。
また、Ｈ、Ｈ’、Ｈ”を、Ｈ：｛０，１｝^＊→Ｇ、Ｈ’：｛０，１｝^＊→Ｇ、Ｈ”：｛０，１｝^＊→Ｚ_ｑなる性質を有するハッシュ関数（一方向性関数）とする。ここで｛０，１｝^＊は、任意のビット長のバイナリ系列を表し、Ｚ_ｑは、加法群を表す。
さらに、投票者はｎ人であるとし、これら投票者の集合をＮ＝｛１，・・・，ｎ｝とする。各投票者は後述する投票装置を用いて電子投票に参加する。ここでは、投票者ｉのＩＤ（identification）をｉ（ｉ＝１，・・・，ｎ）とする。
以下では、ｙ_Ｎ＝（ｙ_ｉ）_ｉ∈Ｎなどと略記する。

［情報公開サーバ］
第１実施形態における公開掲示板（情報公開サーバ）について説明する。
図１は、第１実施形態に係わる情報公開サーバ（１）のハードウェア構成を例示した構成ブロック図である。

図１に例示するように、情報公開サーバ（１）は、キーボードなどが接続可能な入力部（１１）、液晶ディスプレイなどが接続可能な出力部（１２）、情報公開サーバ（１）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（１３）、ＣＰＵ（Central Processing Unit）（１４）〔キャッシュメモリなどを備えていてもよい。〕、メモリであるＲＡＭ（１５）、ＲＯＭ（１６）やハードディスクである外部記憶装置（１７）並びにこれらの入力部（１１）、出力部（１２）、通信部（１３）、ＣＰＵ（１４）、ＲＡＭ（１５）、ＲＯＭ（１６）、外部記憶装置（１７）間のデータのやり取りが可能なように接続するバス（１８）を有している。また必要に応じて、情報公開サーバ（１）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。

情報公開サーバ（１）の外部記憶装置（１７）には、情報公開のためのプログラムおよびこのプログラムの処理において必要となるデータなどが保存記憶されている。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に保存記憶されるとする。

より具体的には、情報公開サーバ（１）の外部記憶装置（１７）〔あるいはＲＯＭなど〕には、情報公開サーバ（１）にアクセスした電子投票装置（後述する。）や開票装置（後述する。）などに対して外部記憶手段（１７）に保存記憶される情報を提供するためのプログラム、情報公開サーバ（１）にアクセスした電子投票装置や開票装置などから情報を取得して外部記憶手段（１７）に保存記憶するためのプログラムおよびこれらのプログラムの処理において必要となるデータなどが保存記憶されている。その他、これらのプログラムに基づく処理を制御するための制御プログラムなども適宜に保存しておく。

情報公開サーバ（１）では、外部記憶装置（１７）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭ（１５）に読み込まれて、ＣＰＵ（１４）で解釈実行・処理される。その結果、ＣＰＵ（１４）が所定の機能（情報提供部、情報取得部）を実現することで、情報公開が実現される。

情報公開サーバ（１）は、電子投票装置や開票装置からのアクセスを許可し、これらの装置に対して、情報公開サーバにおける所定の情報（後述する公開鍵や、開票装置によって得られた開票結果などが含まれる。）を提供し、あるいは、これらの装置から情報を取得するものであるが、投票の公正を保持するため、一旦（情報公開サーバ（１）の外部記憶装置に）保存記憶された情報については、これらの装置よる（情報内容の）変更要求を受け付けないものとし、また、第三者（装置）からの不正なアクセスに対して頑強な保守機能を有しているとする（つまり、情報の改竄ができないとする。）。

［電子投票装置］
第１実施形態における電子投票装置（以下、「投票装置」という。）について説明する。
図２は、第１実施形態に係わる投票装置（２）のハードウェア構成を例示した構成ブロック図である。

図２に例示するように、投票装置（２）は、キーボードなどが接続可能な入力部（２１）、液晶ディスプレイなどが接続可能な出力部（２２）、投票装置（２）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（２３）、ＣＰＵ（Central Processing Unit）（２４）〔キャッシュメモリなどを備えていてもよい。〕、メモリであるＲＡＭ（２５）、ＲＯＭ（２６）やハードディスクである外部記憶装置（２７）並びにこれらの入力部（２１）、出力部（２２）、通信部（２３）、ＣＰＵ（２４）、ＲＡＭ（２５）、ＲＯＭ（２６）、外部記憶装置（２７）間のデータのやり取りが可能なように接続するバス（２８）を有している。また必要に応じて、投票装置（２）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。

投票装置（２）の外部記憶装置（２７）には、電子投票のためのプログラムおよびこのプログラムの処理において必要となるデータなどが保存記憶されている。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に保存記憶される。

より具体的には、投票装置（２）の外部記憶装置（２７）〔あるいはＲＯＭなど〕には、後述する値ｈ、σ_ｉ、σ_ｊ、Ａ_０、Ａ_１、ａ_ｉ、ｂ_ｉ、ａ_ｊ、ｂ_ｊ、ｚ_ｉ、β_φを生成するためのプログラム、群の中から元を任意に選択するためのプログラム、署名を生成するためのプログラムおよびこれらのプログラムの処理において必要となるデータなどが保存記憶されている。その他、これらのプログラムに基づく処理を制御するための制御プログラムも適宜に保存しておく。

投票装置（２）では、外部記憶装置（２７）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭ（２５）に読み込まれて、ＣＰＵ（２４）で解釈実行・処理される。その結果、ＣＰＵ（２４）が所定の機能（ｈ生成部、σ_ｉ生成部、σ_ｊ生成部、Ａ_０生成部、Ａ_１生成部、ａ_ｉ生成部、ｂ_ｉ生成部、ａ_ｊ生成部、ｂ_ｊ生成部、ｚ_ｉ生成部、β_φ生成部、元選択部、署名生成部、制御部）を実現することで、電子投票における投票が実現される。

［開票装置］
第１実施形態における開票装置について説明する。
図３は、第１実施形態に係わる開票装置（３）のハードウェア構成を例示した構成ブロック図である。

図３に例示するように、開票装置（３）は、キーボードなどが接続可能な入力部（３１）、液晶ディスプレイなどが接続可能な出力部（３２）、開票装置（３）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（３３）、ＣＰＵ（Central Processing Unit）（３４）〔キャッシュメモリなどを備えていてもよい。〕、メモリであるＲＡＭ（３５）、ＲＯＭ（３６）やハードディスクである外部記憶装置（３７）並びにこれらの入力部（３１）、出力部（３２）、通信部（３３）、ＣＰＵ（３４）、ＲＡＭ（３５）、ＲＯＭ（３６）、外部記憶装置（３７）間のデータのやり取りが可能なように接続するバス（３８）を有している。また必要に応じて、開票装置（３）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。

開票装置（３）の外部記憶装置（３７）には、開票のためのプログラムおよびこのプログラムの処理において必要となるデータなどが保存記憶されている。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に保存記憶される。

より具体的には、開票装置（３）の外部記憶装置（３７）〔あるいはＲＯＭなど〕には、後述する値ｈ、σ_Ｎ、Ａ_０、ａ’_Ｎ、ｂ’_Ｎを生成するためのプログラム、元ｚを検証するためのプログラム、Ａ_１を検証するためのプログラム、β_φを検証するためのプログラム、β_φの個数を検証するためのプログラム、β_φ（φ＝０）と所定の値との一致を判定するためのプログラム、判定結果に応じて計数するためのプログラム、重複投票の有無を検証するためのプログラムおよびこれらのプログラムの処理において必要となるデータなどが保存記憶されている。その他、これらのプログラムに基づく処理を制御するための制御プログラムも適宜に保存しておく。

開票装置（３）では、外部記憶装置（３７）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭ（３５）に読み込まれて、ＣＰＵ（３４）で解釈実行・処理される。その結果、ＣＰＵ（３４）が所定の機能（ｈ生成部、σ_Ｎ生成部、Ａ_０生成部、ａ’_Ｎ生成部、ｂ’_Ｎ生成部、ｚ検証部、β_φ検証部、次数検証部、Ａ_１検証部、判定部、カウンタ部、フラッグ部、重複投票検証部、制御部）を実現することで、電子投票における開票が実現される。

［ネットワーク構成］
第１実施形態の電子投票システムにおけるネットワーク構成について説明する。
図４は、第１実施形態の電子投票システムにおけるネットワーク構成を示す図である。なお、図４では、電子投票が行われる前の状態を示している。

第１実施形態における電子投票システムは、公開鍵基盤の一例であるＰＫＩ（Public Key Infrastructure）を前提にしている。ＰＫＩは、日本国においても「電子署名及び認証業務に関する法律（平成１２年法律第１０２号）」が制定されたことなども相まって普及整備が進んでいる公知技術であるから（例えば参考文献１参照。）、その詳細の説明は省略する。なお、本発明は、日本国におけるＰＫＩを前提とすることに限定するものではなく、およそ公開鍵基盤が普及整備されているならば、諸外国やあるいは公開鍵基盤の規模・性質（国家・地方・地域のような比較的大きな規模や例えば企業・大学・自治体・団体のような比較的小さな規模、社会基盤としての公的性質や私企業内における私的性質）などを問わず適用可能である。なお、日本国における政府認証基盤（ＧＰＫＩ：Government Public Key Infrastructure）については、参考文献２を参照のこと。
（参考文献１）独立行政法人情報処理推進機構、”ＰＫＩ関連技術解説”、［平成１７年６月３０日検索］、
インターネット <URL : http://www.ipa.go.jp/security/pki/>
（参考文献２）日本国総務省行政管理局、”政府認証基盤（ＧＰＫＩ）”、［平成１７年６月３０日検索］、
インターネット <URL : http://www.gpki.go.jp/>

図４に示すＣＡ（Certification Authority）（４）は、ＰＫＩにおける認証局を表している。
情報公開サーバ（１）、１つ以上の投票装置（２−１），（２−２），・・・，（２−ｎ）、開票装置（３）、ＣＡ（４）は、ネットワーク（５）を介して相互に通信可能に接続されている。なお、少なくとも、各投票装置とネットワークとの間は、各投票装置を利用する投票者のプライバシーが保たれるように匿名通信路とするのがよい。

第１実施形態では、ｎ人の投票者各人には、それぞれ１つの投票装置が割り当てられている。つまり、各投票者は、各別の投票装置を用いて電子投票を行う。しかしながら後述のとおり、各投票者は、各投票者に固有の秘密鍵・公開鍵を用いることで電子投票を行うので、各投票者に各別の投票装置を割り当てることは必須ではない。同じ投票装置であっても、各投票者が、投票者に固有の秘密鍵・公開鍵を投票装置に入力する（例えば、秘密鍵・公開鍵が記録された記録媒体を投票装置に読み取らせる。）ことで、各投票者固有の電子投票が行える。

[準備]
第１実施形態における電子投票を実施するための準備について説明する（図４参照）。
まず、投票者ｉは、秘密鍵ｘ_ｉを群Ｚ_ｑの元から選択し、巡回群Ｇの生成元ｇを用いて、公開鍵ｙ_ｉ＝ｇ＾ｘ_ｉを生成する。記号＾は、べき乗を表す。投票者ｉは、投票者ｉに固有の公開鍵ｙ_ｉをＣＡ（４）に送信し、ＣＡ（４）に公開鍵ｙ_ｉを登録する。ＣＡ（４）は、公開鍵ｙ_ｉに対して公開鍵証明書Ｃｅｒｔ_ｉを発行する。このようにして、ＣＡ（４）は、各投票者の公開鍵ｙ_１，ｙ_２，・・・，ｙ_ｎに対して、公開鍵証明書Ｃｅｒｔ_１，Ｃｅｒｔ_２，・・・，Ｃｅｒｔ_ｎを発行する（公知技術）。

次に、情報公開サーバ（１）は、ＣＡ（４）にネットワーク（５）経由でアクセスし、各投票者の公開鍵ｙ_１，ｙ_２，・・・，ｙ_ｎおよびＣＡ（４）から発行された公開鍵証明書Ｃｅｒｔ_１，Ｃｅｒｔ_２，・・・，Ｃｅｒｔ_ｎを取得する。

情報公開サーバ（１）は、取得した各投票者の公開鍵ｙ_１，ｙ_２，・・・，ｙ_ｎおよびＣＡ（４）から発行された公開鍵証明書Ｃｅｒｔ_１，Ｃｅｒｔ_２，・・・，Ｃｅｒｔ_ｎを、各公開鍵と各公開鍵証明書とを対応付けて外部記憶装置（１７）に記憶保存する。これらは、いわば有権者名簿に相当するものであると云える。

また、情報公開サーバ（１）は、電子投票における投票内容ｍ_１，ｍ_２，・・・，ｍ_ｓも、外部記憶装置（１７）に保存記憶している。ここでｓは、投票内容の種類の数を表す。

情報公開サーバ（１）は、各投票装置や開票装置からアクセスがあった場合に、これらのデータ（公開鍵ｙ_１，ｙ_２，・・・，ｙ_ｎ、公開鍵証明書Ｃｅｒｔ_１，Ｃｅｒｔ_２，・・・，Ｃｅｒｔ_ｎ、投票内容ｍ_１，ｍ_２，・・・，ｍ_ｓ）を、情報提供部（８００）によって、その通信部（１３）を通じて、アクセスした装置に対して送信する。また、電子投票後においては、外部記憶装置（１７）に保存記憶されている署名も、情報提供部（８００）によって、その通信部（１３）を通じて、アクセスした開票装置に対して送信する。

以下、図４〜図１４を参照して、第１実施形態における電子投開票処理の処理を説明する。
図５は、情報公開サーバ（１）における処理フローを示す図である。
図６は、投票装置（２）の機能構成例を示す図である。
図７は、投票装置（２）における処理フローを示す図である（その１）。
図８は、投票装置（２）における処理フローを示す図である（その２）。
図９は、電子投票後における状態を示す図である。
図１０は、開票装置（３）の機能構成例を示す図である。
図１１は、開票装置（３）における処理フローを示す図である（その１）。
図１２は、開票装置（３）における処理フローを示す図である（その２）。
図１３は、開票装置（３）において重複投票を検証する処理における機能構成を例示した図である。
図１４は、開票装置（３）において重複投票を検証する処理フローを示す図である。

[投票]
まず、投票装置による電子投票について説明する。
以下では、投票者ｉは、投票装置ｉによって電子投票を行うとする。
投票装置ｉの外部記憶装置（２７）には、投票装置ｉのＩＤであるｉ、巡回群Ｇの生成元ｇ、投票者ｉに固有の秘密鍵ｘ_ｉが予め保存記憶されているとする。既述のとおり、投票装置ｉのＩＤであるｉ、巡回群Ｇの生成元ｇ、投票者ｉに固有の秘密鍵ｘ_ｉが記録された記録媒体をある投票装置に読み取らせることで、この投票装置を投票装置ｉとして用いることが可能になる。

投票装置ｉは、制御部（６１３）の制御によって、その通信部（２３）を通じて、情報公開サーバ（１）にアクセスし、情報公開サーバ（１）の通信部（１３）を通じて送信された（ステップＳ１ｓ）、情報公開サーバ（１）の外部記憶装置（１７）に記憶される全ての投票者（有権者）の公開鍵｛ｙ_１，…，ｙ_ｎ｝、全ての公開鍵証明書｛ｃｅｒｔ_１，・・・，ｃｅｒｔ_ｎ｝（これらは有権者名簿に相当するものである。）、投票内容ｍ（投票内容がｍ_１，ｍ_２，・・・，ｍ_ｓと複数ある場合は、これら全てについてｍと同様の投開票処理を行うことで複数の投票内容につき投票を行うことができる。）を受信し、これらを投票装置ｉの外部記憶装置（２７）に保存記憶する。また、全ての投票者（有権者）の公開鍵｛ｙ_１，…，ｙ_ｎ｝の個数ｎも、投票装置ｉの外部記憶装置（２７）に保存記憶する（ステップＳ２）。
次いで、投票装置ｉの図示しない検証部（所定のプログラムを解釈実行するＣＰＵ（２４）によって機能が実現する。）は、各公開鍵証明書を検証する（ステップＳ３）。この検証に全て合格したならば、下記の所定の処理を実行する。この検証に合格しなかったならば、取得した公開鍵の中に不正な公開鍵が含まれていることを示すものであるから、投票装置ｉは下記の処理を実行せずに終了する（ステップＳ４）。
なお、検証処理は、ＰＫＩにおける公知技術で達成されるから詳細な説明を省略する。また、相互に通信可能なサーバ（情報公開サーバ）−クライアント（投票装置）間で、サーバからクライアント（あるいは逆に、クライアントからサーバ）にアクセスして所定の情報（データ）を取得し、取得した情報（データ）を外部記憶装置に保存記憶することも公知技術で達成されるから、この明細書ではその詳細な説明を省略する。

なお、情報公開サーバ（１）において公開される情報に含まれる投票内容ｍに賛成か反対かを選択する所作は、人間によってのみ為しえるものであり、この点のみは投票装置（ハードウェア）による所作とは言えない。しかしながら、一旦投票内容が１つ選択されたならば、その後の処理は、投票装置（ハードウェア）による所定のプログラム（ソフトウェア）の解釈実行に従った情報処理が行われ、この情報処理によって電子投票が実現するものであることに留意しなければならない。

予め、制御部（６１３）の制御の下、外部記憶装置（２７）から、投票装置ｉのＩＤであるｉ、巡回群Ｇの生成元ｇ、投票者ｉに固有の秘密鍵ｘ_ｉ、全ての投票者（有権者）の公開鍵｛ｙ_１，…，ｙ_ｎ｝、投票内容ｍ、全ての投票者（有権者）の公開鍵｛ｙ_１，…，ｙ_ｎ｝の個数ｎを読み込み、それぞれをＲＡＭ（２５）の所定の格納領域に格納しておく。以後、全ての投票者（有権者）の公開鍵｛ｙ_１，…，ｙ_ｎ｝をｙ_Ｎと略記する。また、「ＲＡＭから○○を読み込む」旨の説明をした場合は、「ＲＡＭにおいて○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。

まず、ｈ生成部（６００）は、ＲＡＭ（２５）からｎ、ｍ、ｙ_Ｎをそれぞれ読み込み、ｈ＝Ｈ（ｎ，ｙ_Ｎ，ｍ）を演算し、この演算結果ｈをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ５）。ここでハッシュ演算Ｈ（ｎ，ｙ_Ｎ，ｍ）は、バイナリ系列で結合した値ｎ‖ｙ_Ｎ‖ｍ（＝ｎ‖ｙ_１‖ｙ_２‖・・・‖ｙ_ｎ‖ｍ）〔記号‖はバイナリ系列同士の結合を表す。〕を入力として、ハッシュ関数Ｈを演算することを表す。その他のハッシュ関数Ｈ’、Ｈ”についても同様である。なお、ｈは巡回群Ｇの元、即ちｈ∈Ｇであることに留意する。なお、ハッシュ関数Ｈの入力は、値ｎ‖ｙ_Ｎ‖ｍに限定するものではないが、電子投票における安全性確保の観点からは、少なくともｙ_Ｎおよびｍを用いたバイナリ系列の結合値を用いるのがよい。

次に、σ_ｉ生成部（６０１）は、ＲＡＭ（２５）からｈ、ｘ_ｉをそれぞれ読み込み、σ_ｉ＝ｈ＾ｘ_ｉを演算し、この演算結果σ_ｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ６）。なお、σ_ｉは巡回群Ｇの元、即ちσ_ｉ∈Ｇであることに留意する。このσ_ｉは、端末装置ｉに固有の固有臨時公開鍵に相当する。

続いて、Ａ_０生成部（６０２）は、ＲＡＭ（２５）からｎ、ｍ、ｙ_Ｎをそれぞれ読み込み、Ａ_０＝Ｈ’（ｎ，ｙ_Ｎ，ｍ）を演算し、この演算結果Ａ_０をＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ７）。なお、Ａ_０は巡回群Ｇの元、即ちＡ_０∈Ｇであることに留意する。また、ハッシュ関数Ｈ’の入力は、ハッシュ関数Ｈの入力と同じにする必要はないが、この実施形態では同じものを入力としている。

次に、Ａ_１生成部（６０３）は、ＲＡＭ（２５）からｉ、Ａ_０、σ_ｉをそれぞれ読み込み、Ａ_１＝（σ_ｉ／Ａ_０）＾（１／ｉ）を演算し、この演算結果Ａ_１をＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ８）。Ａ_１は巡回群Ｇの元、即ちＡ_１∈Ｇであることに留意する。このＡ_１は、撹乱因子に相当する。

次に、σ_ｊ生成部（６０４）は、ＲＡＭ（２５）からＡ_０、Ａ_１、ｎ、ｉをそれぞれ読み込み、σ_ｊ＝Ａ_０（Ａ_１＾ｊ）を演算し、この演算結果σ_ｊをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ９）。ここでｊは、ｊ∈Ｎ−｛ｉ｝、即ち、ｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎである。なお、σ_ｊは巡回群Ｇの元、即ちσ_ｊ∈Ｇであることに留意する。このσ_ｊは、撹乱臨時公開鍵に相当する。

さらに、Ａ_０＝ｈ＾α（０）かつσ_ｆ＝ｈ＾α（ｆ）〔但し、ｆ∈Ｎ〕を満足する次数１の多項式α（ｘ）∈Ｚ_ｑ［ｘ］が存在することに留意しなければならない。
なお、記号α（ｘ）∈Ｚ_ｑ［ｘ］は、多項式α（ｘ）が、群Ｚ_ｑの元を係数に有する多項式であることを表す。

続いて、元選択部（６０５）は、群Ｚ_ｑの元の中から任意に１つの元ｗ_ｉを選択し、この元ｗ_ｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１０）。

次に、ａ_ｉ生成部（６０６）は、ＲＡＭ（２５）からｇ、ｗ_ｉをそれぞれ読み込み、ａ_ｉ＝ｇ＾ｗ_ｉを演算し、この演算結果ａ_ｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１１）。なお、ａ_ｉは巡回群Ｇの元、即ちａ_ｉ∈Ｇであることに留意する。

次に、ｂ_ｉ生成部（６０７）は、ＲＡＭ（２５）からｈ、ｗ_ｉをそれぞれ読み込み、ｂ_ｉ＝ｈ＾ｗ_ｉを演算し、この演算結果ｂ_ｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１２）。なお、ｂ_ｉは巡回群Ｇの元、即ちｂ_ｉ∈Ｇであることに留意する。

続いて、元選択部（６０５）は、ＲＡＭ（２５）からｉ、ｎをそれぞれ読み込み、ｊ∈Ｎ−｛ｉ｝、即ちｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎについて、群Ｚ_ｑの元の中から任意に２つの元ｚ_ｊ、ｃ_ｊを選択し、これらの元ｚ_ｊ、ｃ_ｊをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１３）。

次に、ａ_ｊ生成部（６０８）は、ｊ∈Ｎ−｛ｉ｝、即ちｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎについて、ＲＡＭ（２５）からｇ、ｚ_ｊ、ｃ_ｊ、ｙ_ｊをそれぞれ読み込み（ｙ_ｊは、ｙ_Ｎからｙ_ｉを除いたものである。）、ａ_ｊ＝（ｇ＾ｚ_ｊ）×（ｙ_ｊ＾ｃ_ｊ）を演算し、この演算結果ａ_ｊをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１４）。なお、ａ_ｊは巡回群Ｇの元、即ちａ_ｊ∈Ｇであることに留意する。

次に、ｂ_ｊ生成部（６０９）は、ｊ∈Ｎ−｛ｉ｝、即ちｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎについて、ＲＡＭ（２５）からｈ、ｚ_ｊ、ｃ_ｊ、σ_ｊをそれぞれ読み込み、ｂ_ｊ＝（ｈ＾ｚ_ｊ）×（σ_ｊ＾ｃ_ｊ）を演算し、この演算結果ｂ_ｊをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１５）。なお、ｂ_ｊは巡回群Ｇの元、即ちｂ_ｊ∈Ｇであることに留意する。

続いて、β_φ生成部（６１０）は、次数（ｎ−１）の多項式β（ｘ）∈Ｚ_ｑ［ｘ］の係数β_φ（φ＝０，１，２，・・・，ｎ−１）を求める。つまり、多項式β（ｘ）＝β_ｎ−１ｘ＾（ｎ−１）＋β_ｎ−２ｘ＾（ｎ−２）＋・・・＋β_１ｘ＋β_０とすると、ｎ個の係数β_ｎ−１，β_ｎ−２，・・・，β_１、β_０の値を求めるのである（β_０はｘ＾（０）の係数とする。）。これら係数は、ｘに０，１，・・・，ｉ−１，ｉ＋１，・・・，ｎを代入したｎ個の連立方程式を解くことで求めることができる。連立方程式を解くアルゴリズムは公知であるからその説明は省略する。
β_φ生成部（６１０）は、ＲＡＭ（２５）からｎ、ｙ_Ｎ、ｍ、ｈ、Ａ_０、Ａ_１、ａ_ｉ、ａ_ｊ、ｂ_ｉ、ｂ_ｊ、ｃ_ｊをそれぞれ読み込み、β（０）＝Ｈ”（ｎ，ｙ_Ｎ，ｍ，ｈ，Ａ_０，Ａ_１，ａ_Ｎ，ｂ_Ｎ）、β（ｊ）＝ｃ_ｊ（ｊ∈Ｎ−｛ｉ｝）からなるｎ個の連立方程式を公知のアルゴリズムで解いてｎ個の係数β_ｎ−１，β_ｎ−２，・・・，β_１、β_０の値を求め、これらの係数β_ｎ−１，β_ｎ−２，・・・，β_１、β_０をＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１６）。ここで、ｊ∈Ｎ−｛ｉ｝、即ちｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎであり、ａ_Ｎは、ａ_Ｎ＝（ａ_１，ａ_２，・・・，ａ_ｎ）であり、ｂ_Ｎは、ｂ_Ｎ＝（ｂ_１，ｂ_２，・・・，ｂ_ｎ）であるとする。なお、β（０）、β（ｊ）は群Ｚ_ｑの元であることに留意する。

続いて、ｚ_ｉ生成部（６１１）は、ＲＡＭ（２５）からｎ、ｉ、ｗ_ｉ、ｘ_ｉ、β_φ（φ＝０，１，２，・・・，ｎ−１）をそれぞれ読み込み、ｚ_ｉ＝ｗ_ｉ−β（ｉ）×ｘ_ｉを演算し、この演算結果ｚ_ｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１７）。β（ｉ）は、読み込んだβ_φを用いて、β（ｉ）＝β_ｎ−１×ｉ＾（ｎ−１）＋β_ｎ−２×ｉ＾（ｎ−２）＋・・・＋β_１×ｉ＋β_０によって求めることができる。なお、ｚ_ｉは群Ｚ_ｑの元、即ちｚ_ｉ∈Ｚ_ｑであることに留意する。

続いて、署名生成部（６１２）は、ＲＡＭ（２５）からＡ_１、ｍ、ｚ_ｉ、ｚ_ｊ、β_φ（φ＝０，１，２，・・・，ｎ−１）をそれぞれ読み込み、このうち、Ａ_１、ｚ_ｉ、ｚ_ｊ、β_φの組み合わせを、投票装置ｉにおける投票内容ｍに対する署名ξ_ｉとする（ステップＳ１８）。即ち、ξ_ｉ＝（Ａ_１、β、ｚ_Ｎ）とする。ここでβは、β＝（β_０，β_１，・・・，β_ｎ−１）、ｚ_Ｎは、ｚ_Ｎ＝（ｚ_１，ｚ_２，・・・，ｚ_ｎ）である。

続いて、投票装置ｉは、制御部（６１３）の制御によって、通信部（２３）を通じて、ステップＳ１８で生成された署名ξ_ｉおよび投票内容ｍを、匿名通信路を経由して情報公開サーバ（１）に送信する（ステップＳ１９）。これが「電子投票」に相当する。

情報公開サーバ（１）は、情報取得部（８０１）によって、その通信部(１３）を通じて、ステップＳ１９で送信された署名ξ_ｉおよび投票内容ｍを受信し、署名ξ_ｉおよび投票内容ｍを対応付けて外部記憶装置（１７）に保存記憶する（ステップＳ２ｓ）。

各投票装置からも同様の電子投票が行われ、結果として、情報公開サーバ（１）の外部記憶装置（１７）には、各投票装置から電子投票された投票結果が保存記憶される（図１０参照）。

［開票］
続いて、開票装置（３）による電子投票の開票処理について説明する。
開票装置（３）の外部記憶装置（３７）には、巡回群Ｇの生成元ｇが予め保存記憶されているとする。

開票装置（３）は、制御部（７１１）の制御によって、その通信部（３３）を通じて、情報公開サーバ（１）にアクセスし、情報公開サーバ（１）の通信部（１３）を通じて送信された（ステップＳ３ｓ）、情報公開サーバ（１）の外部記憶装置（１７）に記憶される全投票者（有権者）の公開鍵｛ｙ_１，…，ｙ_ｎ｝、全公開鍵証明書｛ｃｅｒｔ_１，・・・，ｃｅｒｔ_ｎ｝（これらは有権者名簿に相当する。）を受信し、これらを開票装置（３）の外部記憶装置（３７）に保存記憶する。また、全投票者（有権者）の公開鍵｛ｙ_１，…，ｙ_ｎ｝の個数ｎも、開票装置（３）の外部記憶装置（３７）に保存記憶する（ステップＳ２１）。
次いで、開票装置（３）の図示しない検証部（所定のプログラムを解釈実行するＣＰＵ（３４）によって機能が実現する。）は、各公開鍵証明書を検証する（ステップＳ２２）。この検証に全て合格したならば、下記の所定の処理を実行する。この検証に合格しなかったならば、取得した公開鍵の中に不正な公開鍵が含まれていることを示すものであるから、開票装置（３）は下記の処理を実行せずに終了する（ステップＳ２３）。
なお、検証処理は、ＰＫＩにおける公知技術で達成されるから詳細な説明を省略する。また、相互に通信可能なサーバ（情報公開サーバ）−クライアント（投票装置）間で、サーバからクライアント（あるいは逆に、クライアントからサーバ）にアクセスして所定の情報（データ）を取得し、取得した情報（データ）を外部記憶装置に保存記憶することも公知技術で達成されるから、この明細書ではその詳細な説明を省略する。

まず、開票装置（３）は、制御部（７１１）の制御によって、その通信部（３３）を通じて、情報公開サーバ（１）にアクセスし、情報公開サーバ（１）の通信部（１３）を通じて送信された（ステップ４ｓ）、情報公開サーバ（１）の外部記憶装置（１７）に記憶される有効投票総数の計数処理を行う投票内容ｍおよびその投票内容ｍに対応付けられた署名を全て受信し、外部記憶装置（３７）に保存記憶する（ステップＳ２４）。ここでは、投票内容ｍに電子投票した投票総数（有効投票総数ではない。）をｅ（ｅ≦ｎ）とする。従って、受信する署名はｅ個である。

続いて、制御部（７１１）の制御によって、外部記憶装置（３７）から、巡回群Ｇの生成元ｇ、全投票者（有権者）の公開鍵｛ｙ_１，…，ｙ_ｎ｝、投票内容ｍ、ｅ個の署名から１個選択した署名ξ＝（Ａ_１、β、ｚ_Ｎ）、全投票者（有権者）の公開鍵｛ｙ_１，…，ｙ_ｎ｝の個数ｎを読み込み、それぞれをＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ２５）。また、制御部（７１１）の制御によって、ＲＡＭ（３５）に値ｖおよび値Ｆを格納する所定の格納領域を確保する。値ｖおよび値Ｆの初期値は０とする。

次に、ｈ生成部（７００）は、ＲＡＭ（３５）からｎ、ｍ、ｙ_Ｎをそれぞれ読み込み、ｈ＝Ｈ（ｎ，ｙ_Ｎ，ｍ）を演算し、この演算結果ｈをＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ２６）。なお、ｈは巡回群Ｇの元、即ちｈ∈Ｇであることに留意する。

次に、Ａ_０生成部（７０１）は、ＲＡＭ（３５）からｎ、ｍ、ｙ_Ｎをそれぞれ読み込み、Ａ_０＝Ｈ’（ｎ，ｙ_Ｎ，ｍ）を演算し、この演算結果Ａ_０をＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ２７）。なお、Ａ_０は巡回群Ｇの元、即ちＡ_０∈Ｇであることに留意する。

次に、Ａ_１検証部（７０２）は、ＲＡＭ（３５）からＡ_１を読み込み、Ａ_１が巡回群Ｇの元であるか否かを検証する（ステップＳ２８）。この検証に合格しなかった場合、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ２６以降の処理を行う（ステップＳ４５）。この検証に合格したら、制御部（７１１）は、以下の処理を実行するように制御する。

次に、σ_Ｎ生成部（７０３）は、ＲＡＭ（３５）からＡ_０、Ａ_１、ｎをそれぞれ読み込み、σ_ｆ＝Ａ_０（Ａ_１＾ｆ）〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果σ_Ｎ（＝（σ_１，σ_２，・・・，σ_ｎ））をＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ２９）。このσ_Ｎが、臨時公開鍵に相当する。なお、σ_Ｎ（＝（σ_１，σ_２，・・・，σ_ｎ））はそれぞれ巡回群Ｇの元、即ちσ_Ｎ∈Ｇであることに留意する。また、ステップＳ２９で生成されたσ_Ｎには固有臨時公開鍵と撹乱臨時公開鍵が含まれるが、いずれのσ_ｆが署名ξをもって電子投票した投票装置において生成された固有臨時公開鍵であるかは判別できないことにも留意すること（電子投票における匿名性の確保）。

続いて、β_φ検証部（７０４）は、ＲＡＭ（３５）からβ_φ（φ＝０，１，２，・・・，ｎ−１）をそれぞれ読み込み、各β_φ（φ＝０，１，２，・・・，ｎ−１）が群Ｚ_ｑの元であるか否かを検証する（ステップＳ３０）。この検証に合格しなかった場合、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ２６以降の処理を行う（ステップＳ４５）。この検証に合格したら、制御部（７１１）は、以下の処理を実行するように制御する。

続いて、次数検証部（７０５）は、ＲＡＭ（３５）からｎ、β_φ（φ＝０，１，２，・・・，ｎ−１）をそれぞれ読み込み、β_φの個数がｎであるか否かを検証する（ステップＳ３１）。この検証に合格しなかった場合、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ２６以降の処理を行う（ステップＳ４５）。この検証に合格したら、制御部（７１１）は、以下の処理を実行するように制御する。

続いて、ｚ検証部（７０６）は、ＲＡＭ（３５）からｚ_Ｎ（＝（ｚ_１，ｚ_２，・・・，ｚ_ｎ））をそれぞれ読み込み、各ｚ_Ｎ（＝（ｚ_１，ｚ_２，・・・，ｚ_ｎ））が群Ｚ_ｑの元であるか否かを検証する（ステップＳ３２）。この検証に合格しなかった場合、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ２６以降の処理を行う（ステップＳ４５）。この検証に合格したら、制御部（７１１）は、以下の処理を実行するように制御する。

続いて、ａ’_Ｎ生成部（７０７）は、ＲＡＭ（３５）からｎ、ｇ、β_φ、ｚ_Ｎ、ｙ_Ｎをそれぞれ読み込み、ａ’_ｆ＝（ｇ＾ｚ_ｆ）×（ｙ_ｆ＾β（ｆ））〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果ａ’_Ｎ（＝（ａ’_１，ａ’_２，・・・，ａ’_ｎ））をＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ３３）。β（ｆ）は、読み込んだβ_φを用いて、β（ｆ）＝β_ｎ−１×ｆ＾（ｎ−１）＋β_ｎ−２×ｆ＾（ｎ−２）＋・・・＋β_１×ｆ＋β_０によって求めることができる。なお、ａ’_Ｎ（＝（ａ’_１，ａ’_２，・・・，ａ’_ｎ））はそれぞれ巡回群Ｇの元、即ちａ’_Ｎ∈Ｇであることに留意する。

続いて、ｂ’_Ｎ生成部（７０８）は、ＲＡＭ（３５）からｎ、ｈ、β_φ、ｚ_Ｎ、σ_Ｎをそれぞれ読み込み、ｂ’_ｆ＝（ｈ＾ｚ_ｆ）×（σ_ｆ＾β（ｆ））〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果ｂ’_Ｎ（＝（ｂ’_１，ｂ’_２，・・・，ｂ’_ｎ））をＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ３４）。β（ｆ）は、読み込んだβ_φを用いて、β（ｆ）＝β_ｎ−１×ｆ＾（ｎ−１）＋β_ｎ−２×ｆ＾（ｎ−２）＋・・・＋β_１×ｆ＋β_０によって求めることができる。なお、ｂ’_Ｎ（＝（ｂ’_１，ｂ’_２，・・・，ｂ’_ｎ））はそれぞれ巡回群Ｇの元、即ちｂ’_Ｎ∈Ｇであることに留意する。

続いて、判定部（７０９）は、ＲＡＭ（３５）からｎ、ｙ_Ｎ、ｍ、ｈ、Ａ_０、Ａ_１、ａ’_Ｎ、ｂ’_Ｎ、β_φをそれぞれ読み込み、β（０）＝Ｈ”（ｎ，ｙ_Ｎ，ｍ，ｈ，Ａ_０，Ａ_１，ａ’ _Ｎ，ｂ’ _Ｎ）が成立するか否かを判定し、この判定結果ＲをＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ３５）。この判定が成立しなかった場合（判定不成立）、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ以降の処理を行う。この判定が成立した場合（判定成立）、制御部（７１１）は、以下の処理を実行するように制御する。

続いて、カウンタ部（７１０）は、ＲＡＭ（３５）からｖを読み込み、この値に１を加えた値ｖ＋１を、ＲＡＭ（３５）の値ｖが格納されている格納領域に上書きで格納する（ステップＳ３６）。ここで上書きとは、予め格納されている値を消除して新たな値を格納することをいう。

続いて、フラッグ部（７１２）は、フラッグ値Ｆ＝１をＲＡＭ（３５）の値Ｆが格納されている格納領域に上書きで格納する（ステップＳ３７）。

制御部（７１１）の制御によって、以上の処理で求められた値Ｆおよびσ_Ｎを、外部記憶装置（３７）に保存記憶される署名ξに対応付けて保存記憶する（ステップＳ３８）。なお、ステップＳ３７の処理が実行されなかった署名ξには、フラッグ値Ｆ＝０が対応付けられる。

以上の処理をｅ個の署名全てについて行うことで（ステップＳ３９）、投票内容ｍに対応付けられたｅ個の署名のうち、有権者による投票の総数を計数することができる。つまり、ｅ個の署名全てについて以上の処理を行った後に、ＲＡＭ（３５）の所定の格納領域に格納されているｖの値が、有権者による（投票内容ｍの）投票の総数を表している。そこで、制御部（７１１）の制御によって、以上の処理で求められた値ｖを、外部記憶装置（３７）に保存記憶する（ステップＳ４０）。

続いて、重複投票の有無を検証する処理を行う。
ステップＳ２９で生成されたσ_Ｎには固有臨時公開鍵と撹乱臨時公開鍵が含まれるが、この固有臨時公開鍵は投票装置（投票者）に固有のものであるから、複数の署名に同一の固有臨時公開鍵が含まれないことを利用する（もし、同一の固有臨時公開鍵が含まれれば、重複投票と看做すことができる。）。なお、既述のとおり、いずれのσ_ｆが投票装置（投票者）に固有の固有臨時公開鍵であるかは不明であるが、投票装置ｉから電子投票された署名から求められたσ_Ｎにおいては、ｉ番目のσ_ｉが固有臨時公開鍵であるから、各署名から求められたσ_Ｎそれぞれのｉ番目のσ_ｉの値を比較し、同一の値が存在すれば、この同一値を与えるσ_ｉを含むσ_Ｎを生成した署名は不正な電子投票に基づくものとして、計数から除外することが可能になる（電子投票における一人一票の確保）。

まず、制御部（７１１）の制御によって、値Ｆ＝１が対応付けられた署名に対応付けられたσ_Ｎを外部記憶装置（３７）から読み込み、ＲＡＭ（３５）の所定の格納領域に格納する。また、制御部（７１１）の制御によって、値ｖも外部記憶装置（３７）から読み込み、ＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ４１）。ここでは説明の便宜から、投票内容ｍに対応付けられたｅ個の署名をξ_２、ξ_３、ξ_５、ξ_８、ξ_１０、ξ_１７、・・・とし、このうち値Ｆ＝１が対応付けられた署名をξ_３、ξ_５、ξ_８、ξ_１７、・・・とする。また、値Ｆ＝１が対応付けられた署名に対応付けられたσ_Ｎをσ_Ｎ（ξ_３）、σ_Ｎ（ξ_５）、σ_Ｎ（ξ_８）、σ_Ｎ（ξ_１７）、・・・とする。

次に、重複投票検証部（７１３）は、ＲＡＭ（３５）からσ_Ｎ（ξ_３）、σ_Ｎ（ξ_５）、σ_Ｎ（ξ_８）、σ_Ｎ（ξ_１７）、・・・およびｖを読み込み、ｆ＝１，２，・・・，ｎについて、σ_ｆ（ξ_３）、σ_ｆ（ξ_５）、σ_ｆ（ξ_８）、σ_ｆ（ξ_１７）、・・・に同一の値が存在するか否かを検証し、同一の値が存在する場合、その値が存在するσ_Ｎの数（τ）を計数する（ステップＳ４２）。重複投票検証部（７１３）は、ｖ−τを求めて、この値をＲＡＭ（３５）の値ｖが格納されている格納領域に上書きで格納する（ステップＳ４３）。

制御部（７１１）の制御によって、以上の処理で求められた値ｖを、外部記憶装置（３７）に保存記憶する。この値ｖが、重複投票による無効投票を排除した、有権者による（投票内容ｍに対する）電子投票の有効投票総数を表している。

以上の処理を、各投票内容ｍ_１，ｍ_２，・・・，ｍ_ｓについて行うことで、各投票内容に対する有効投票総数を計数できる。

開票装置（３）は、制御部（７１１）の制御によって、その通信部（３３）を通じて、情報公開サーバ（１）に対し、計数された各投票内容に対する有効投票総数を送信する。情報公開サーバ（１）は、開票装置（３）から各投票内容に対する有効投票総数を受信し、この各投票内容に対する有効投票総数を外部記憶装置（１７）に保存記憶する。
結果、各投票装置は、情報公開サーバに対してアクセスすることで、開票結果（各投票内容に対する有効投票総数）を取得することが可能になる。

＜第２実施形態＞
次に、本発明の第２実施形態について、図１５から図２０を参照しながら説明する。
第１実施形態では、多項式β（ｘ）の係数を用いた電子投票・開票処理を行ったが、第２実施形態では、多項式の係数を用いない電子投票・開票処理を説明する。これにより、電子投票における署名生成処理・開票における検証処理の演算量を低減することができる。
なお、第２実施形態では、第１実施形態と同一の機能・処理については同一の符号を与えるなどして説明を省略する。
図１５は、第２実施形態における投票装置（２’）の機能構成例を示す図である。
図１６は、投票装置（２’）における処理フローを示す図である（その１）。
図１７は、投票装置（２’）における処理フローを示す図である（その２）。
図１８は、第２実施形態における開票装置（３）の機能構成例を示す図である。
図１９は、開票装置（３’）における処理フローを示す図である（その１）。
図２０は、開票装置（３’）における処理フローを示す図である（その２）。

[投票装置]
第２実施形態における投票装置（２’）について説明する。
第２実施形態に係わる投票装置（２’）の外部記憶装置（２７）には、電子投票のためのプログラムおよびこのプログラムの処理において必要となるデータなどが保存記憶されている。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に保存記憶される。

第２実施形態に係わる投票装置（２’）の外部記憶装置（２７）〔あるいはＲＯＭなど〕には、値β_φを生成するプログラムに替えて値ｃ_ｉを生成するためのプログラムが保存記憶されている。その他のプログラムは第１実施形態と同様である。

第２実施形態に係わる投票装置（２’）では、外部記憶装置（２７）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭ（２５）に読み込まれて、ＣＰＵ（２４）で解釈実行・処理される。その結果、ＣＰＵ（２４）が所定の機能（ｈ生成部、σ_ｉ生成部、σ_ｊ生成部、Ａ_０生成部、Ａ_１生成部、ａ_ｉ生成部、ｂ_ｉ生成部、ａ_ｊ生成部、ｂ_ｊ生成部、ｚ_ｉ生成部、ｃ_ｉ生成部、元選択部、署名生成部、制御部）を実現することで、電子投票における投票が実現される。

［開票装置］
第２実施形態における開票装置について説明する。
第２実施形態に係わる開票装置（３’）の外部記憶装置（３７）〔あるいはＲＯＭなど〕には、β_φを検証するためのプログラム、β_φの個数を検証するためのプログラム、β_φ（φ＝０）と所定の値との一致を判定するためのプログラムに替えて、元ｃを検証するためのプログラム、元ｃと所定の値との一致を判定するためのプログラムが保存記憶されている。

開票装置（３’）では、外部記憶装置（３７）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭ（３５）に読み込まれて、ＣＰＵ（３４）で解釈実行・処理される。その結果、ＣＰＵ（３４）が所定の機能（ｈ生成部、σ_Ｎ生成部、Ａ_０生成部、ａ’_Ｎ生成部、ｂ’_Ｎ生成部、ｚ検証部、ｃ検証部、Ａ_１検証部、判定部、カウンタ部、フラッグ部、重複投票検証部、制御部）を実現することで、電子投票における開票が実現される。

[投票]
第１実施形態のステップＳ１からステップＳ１５までは同じ処理を行う。
第１実施形態における投票装置ｉのステップＳ１６では、β_φ生成部（６１０）が、次数（ｎ−１）の多項式β（ｘ）∈Ｚ_ｑ［ｘ］の係数β_φ（φ＝０，１，２，・・・，ｎ−１）を求めたが、第２実施形態では、ｃ_ｉ生成部（６１５）がｃ_ｉを求める。即ち、ｃ_ｉ生成部（６１５）は、ＲＡＭ（２５）からｎ、ｙ_Ｎ、ｍ、ｈ、Ａ_０、Ａ_１、ａ_ｉ、ａ_ｊ、ｂ_ｉ、ｂ_ｊ、ｃ_ｊをそれぞれ読み込み、式（１）の演算を行い、この演算結果ｃ_ｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１６’）。ここで、ｊ∈Ｎ−｛ｉ｝、即ちｊ＝１，２，・・・，ｉ−１，ｉ＋１，・・・，ｎであり、ａ_Ｎは、ａ_Ｎ＝（ａ_１，ａ_２，・・・，ａ_ｎ）であり、ｂ_Ｎは、ｂ_Ｎ＝（ｂ_１，ｂ_２，・・・，ｂ_ｎ）であるとする。なお、ｃ_ｉは群Ｚ_ｑの元、即ちｃ_ｉ∈Ｚ_ｑであることに留意する。

第１実施形態における投票装置ｉのステップＳ１７では、ｚ_ｉ生成部（６１１）が、ｚ_ｉ＝ｗ_ｉ−β（ｉ）×ｘ_ｉを演算し、この演算結果ｚ_ｉを求めたが、第２実施形態では、ｚ_ｉ生成部（６１６）が第１実施形態とは異なるｚ_ｉを求める。即ち、ｚ_ｉ生成部（６１６）は、ＲＡＭ（２５）からｗ_ｉ、ｘ_ｉ、ｃ_ｉをそれぞれ読み込み、ｚ_ｉ＝ｗ_ｉ−ｃ_ｉ×ｘ_ｉを演算し、この演算結果ｚ_ｉをＲＡＭ（２５）の所定の格納領域に格納する（ステップＳ１７’）。なお、ｚ_ｉは群Ｚ_ｑの元、即ちｚ_ｉ∈Ｚ_ｑであることに留意する。

第１実施形態における投票装置ｉのステップＳ１８では、署名生成部（６１２）が、Ａ_１、ｚ_ｉ、ｚ_ｊ、β_φの組み合わせを、投票装置ｉにおける投票内容ｍに対する署名ξ_ｉとしたが、第２実施形態では、署名生成部（６１７）が第１実施形態とは異なる署名を求める。即ち、署名生成部（６１７）は、ＲＡＭ（２５）からＡ_１、ｍ、ｚ_ｉ、ｚ_ｊ、ｃ_ｉ、ｃ_ｊをそれぞれ読み込み、このうち、Ａ_１、ｚ_ｉ、ｚ_ｊ、ｃ_ｉ、ｃ_ｊの組み合わせを、投票装置ｉにおける投票内容ｍに対する署名ξ_ｉとする（ステップＳ１８’）。即ち、ξ_ｉ＝（Ａ_１、ｃ_Ｎ、ｚ_Ｎ）とする。ここでｚ_Ｎは、ｚ_Ｎ＝（ｚ_１，ｚ_２，・・・，ｚ_ｎ）、ｃ_Ｎは、ｃ_Ｎ＝（ｃ_１，ｃ_２，・・・，ｃ_ｎ）である。ステップＳ１８’以降は、第１実施形態と同様の処理を行う。

[開票]
第１実施形態のステップＳ２０からステップＳ２３までは同じ処理を行う。
第１実施形態における開票装置（３）のステップＳ２４では、制御部（７１１）の制御によって、外部記憶装置（３７）から、巡回群Ｇの生成元ｇ、全投票者（有権者）の公開鍵｛ｙ_１，…，ｙ_ｎ｝、投票内容ｍ、ｅ個の署名から１個選択した署名ξ＝（Ａ_１、β、ｚ_Ｎ）、全投票者（有権者）の公開鍵｛ｙ_１，…，ｙ_ｎ｝の個数ｎを読み込み、それぞれをＲＡＭ（３５）の所定の格納領域に格納したが、第２実施形態では、制御部（７１１）の制御によって、外部記憶装置（３７）から、巡回群Ｇの生成元ｇ、全投票者（有権者）の公開鍵｛ｙ_１，…，ｙ_ｎ｝、投票内容ｍ、ｅ個の署名から１個選択した署名ξ＝（Ａ_１、ｃ_Ｎ、ｚ_Ｎ）、全投票者（有権者）の公開鍵｛ｙ_１，…，ｙ_ｎ｝の個数ｎを読み込み、それぞれをＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ２４’）。

ステップＳ２４’以降は、第１実施形態におけるステップＳ２５からステップＳ２９までと同様の処理を行う。

第１実施形態における開票装置（３）のステップＳ３０では、β_φ検証部（７０４）が、ＲＡＭ（３５）からβ_φ（φ＝０，１，２，・・・，ｎ−１）をそれぞれ読み込み、各β_φ（φ＝０，１，２，・・・，ｎ−１）が群Ｚ_ｑの元であるか否かを検証したが、第２実施形態では不要の処理となる。

また、第１実施形態における開票装置（３）のステップＳ３１では、次数検証部（７０５）は、ＲＡＭ（３５）からｎ、β_φ（φ＝０，１，２，・・・，ｎ−１）をそれぞれ読み込み、β_φの個数がｎであるか否かを検証したが、第２実施形態では不要の処理となる。

第２実施形態では、ステップＳ３２に続き、ｃ検証部（７１５）が、ＲＡＭ（３５）からｃ_Ｎ（＝（ｃ_１，ｃ_２，・・・，ｃ_ｎ））をそれぞれ読み込み、各ｃ_Ｎ（＝（ｃ_１，ｃ_２，・・・，ｃ_ｎ））が群Ｚ_ｑの元であるか否かを検証する（ステップＳ３２ａ）。この検証に合格しなかった場合、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ２６以降の処理を行い（ステップＳ４５）、この検証に合格したら、制御部（７１１）は、以下の処理を実行するように制御することは第１実施形態と同様である。

第１実施形態における開票装置（３）のステップＳ３３では、ａ’_Ｎ生成部（７０７）がａ’_Ｎを求めたが、第２実施形態では、第１実施形態と異なるａ’_Ｎを求める。即ち、ａ’_Ｎ生成部（７１６）は、ＲＡＭ（３５）からｎ、ｇ、ｃ_Ｎ、ｚ_Ｎ、ｙ_Ｎをそれぞれ読み込み、ａ’_ｆ＝（ｇ＾ｚ_ｆ）×（ｙ_ｆ＾ｃ_ｆ）〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果ａ’_Ｎ（＝（ａ’_１，ａ’_２，・・・，ａ’_ｎ））をＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ３３’）。なお、ａ’_Ｎ（＝（ａ’_１，ａ’_２，・・・，ａ’_ｎ））はそれぞれ巡回群Ｇの元、即ちａ’_Ｎ∈Ｇであることに留意する。

第１実施形態における開票装置（３）のステップＳ３４では、ｂ’_Ｎ生成部（７０８）がｂ’_Ｎを求めたが、第２実施形態では、第１実施形態と異なるｂ’_Ｎを求める。即ち、ｂ’_Ｎ生成部（７１７）は、ＲＡＭ（３５）からｎ、ｈ、ｃ_Ｎ、ｚ_Ｎ、σ_Ｎをそれぞれ読み込み、ｂ’_ｆ＝（ｈ＾ｚ_ｆ）×（σ_ｆ＾ｃ_ｆ）〔但しｆ＝１，２，・・・，ｎとする。〕を演算し、この演算結果ｂ’_Ｎ（＝（ｂ’_１，ｂ’_２，・・・，ｂ’_ｎ））をＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ３４’）。なお、ｂ’_Ｎ（＝（ｂ’_１，ｂ’_２，・・・，ｂ’_ｎ））はそれぞれ巡回群Ｇの元、即ちｂ’_Ｎ∈Ｇであることに留意する。

第１実施形態における開票装置（３）のステップＳ３５では、判定部（７０９）が、β（０）＝Ｈ”（ｎ，ｙ_Ｎ，ｍ，ｈ，Ａ_０，Ａ_１，ａ_Ｎ，ｂ_Ｎ）が成立するか否かを判定したが、第２実施形態では異なる判定を行う。即ち、判定部（７１８）は、ＲＡＭ（３５）からｎ、ｙ_Ｎ、ｍ、ｈ、Ａ_０、Ａ_１、ａ’_Ｎ、ｂ’_Ｎ、ｃ_Ｎをそれぞれ読み込み、式（２）が成立するか否かを判定し、この判定結果ＲをＲＡＭ（３５）の所定の格納領域に格納する（ステップＳ３５’）。この判定が成立しなかった場合（判定不成立）、この署名は不正な署名であるから、制御部（７１１）は、この署名が付与された電子投票を無効投票として計数しないで（つまり、以下の処理を実行しないで）、ｅ個の署名から新たに１個の署名ξを選択してステップＳ２６以降の処理を行い（ステップＳ４５）、この判定が成立した場合（判定成立）、制御部（７１１）は、以下の処理を実行するように制御することは第１実施形態と同様である。ステップＳ３５’以降は、第１実施形態と同様の処理を行う。

本発明である電子投票装置、開票装置、情報公開サーバ、電子投開票システム・方法は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。例えば、署名生成方法や投票署名の検証方法は適宜に変更可能である。また、上記電子投開票システム・方法において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。

また、上記電子投票装置、開票装置、情報公開サーバにおける処理機能をコンピュータによって実現する場合、電子投票装置、開票装置、情報公開サーバが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記電子投票装置、開票装置、情報公開サーバにおける処理機能がコンピュータ上で実現される。

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。

また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。

また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、電子投票装置、開票装置、情報公開サーバを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

本発明は電子投開票に有用である。

第１実施形態に係わる情報公開サーバ（１）のハードウェア構成を例示した構成ブロック図。第１実施形態に係わる投票装置（２）のハードウェア構成を例示した構成ブロック図である。第１実施形態に係わる開票装置（３）のハードウェア構成を例示した構成ブロック図。第１実施形態の電子投票システムにおけるネットワーク構成を示す図（但し、電子投票が行われる前の状態を示している。）。情報公開サーバ（１）における処理フローを示す図。投票装置（２）の機能構成例を示す図。投票装置（２）における処理フローを示す図（その１）。投票装置（２）における処理フローを示す図（その２）。電子投票後における状態を示す図。開票装置（３）の機能構成例を示す図。開票装置（３）における処理フローを示す図（その１）。開票装置（３）における処理フローを示す図（その２）。開票装置（３）において重複投票を検証する処理における機能構成を例示した図。開票装置（３）において重複投票を検証する処理フローを示す図。第２実施形態における投票装置（２’）の機能構成例を示す図。投票装置（２’）における処理フローを示す図（その１）。投票装置（２’）における処理フローを示す図（その２）。第２実施形態における開票装置（３）の機能構成例を示す図。開票装置（３’）における処理フローを示す図（その１）。開票装置（３’）における処理フローを示す図（その２）。

符号の説明

１情報公開サーバ
２投票装置
３開票装置
４ＣＡ（認証局）
５ネットワーク
６０１ σ_ｉ生成部
６０３Ａ_１生成部
６０４ σ_ｊ生成部
６１２署名生成部
７０２Ａ_１検証部
７０３ σ_Ｎ生成部
７０９判定部
７１０カウンタ部

Claims

巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の秘密鍵ｘ _ｉを群Ｚ _ｑの元とし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙ _ｉ＝ｇ＾ｘ _ｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝が記憶されている情報公開サーバに対して電子投票を行う電子投票装置であって、
投票者ｉに固有の秘密鍵ｘ _ｉを記憶する記憶手段と、
上記情報公開サーバから、投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝を受信する受信手段と、
投票者ｉに固有の固有臨時公開鍵σ _ｉ＝Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｘ _ｉを求める固有臨時公開鍵生成手段と、
撹乱因子Ａ _１＝（σ _ｉ／Ｈ’（ｎ，ｙ _Ｎ，ｍ））＾（１／ｉ）を求める撹乱因子生成手段と、
ｎ−１個の撹乱臨時公開鍵σ _ｊ＝Ｈ’（ｎ，ｙ _Ｎ，ｍ）（Ａ _１＾ｊ）[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を求める撹乱臨時公開鍵生成手段と、
任意に選択した元ｗ _ｉ ∈Ｚ _ｑについてａ _ｉ＝ｇ＾ｗ _ｉとｂ _ｉ＝Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｗ _ｉを求め、各ｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]について任意に選択した２つの元ｚ _ｊ、ｃ _ｊ ∈Ｚ _ｑを用いて、ａ _ｊ＝（ｇ＾ｚ _ｊ）×（ｙ _ｊ＾ｃ _ｊ）とｂ _ｊ＝（Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｚ _ｊ）×（σ _ｊ＾ｃ _ｊ）を求め、β（０）＝Ｈ”（ｎ，ｙ _Ｎ，ｍ，Ｈ（ｎ，ｙ _Ｎ，ｍ），Ｈ’（ｎ，ｙ _Ｎ，ｍ），Ａ _１，ａ _１，ａ _２，…，ａ _ｎ，ｂ _１，ｂ _２，…，ｂ _ｎ）、β（ｊ）＝ｃ _ｊ [ｊ∈｛１，…，ｎ｝−｛ｉ｝]を満たす次数（ｎ−１）の多項式β（ｘ）＝β _ｎ−１ｘ＾（ｎ−１）＋β _ｎ−２ｘ＾（ｎ−２）＋…＋β _１ｘ＋β _０ ∈Ｚ _ｑ［ｘ］の係数β _φ （φ＝０，１，２，…，ｎ−１）を求め、さらに、ｚ _ｉ＝ｗ _ｉ −β（ｉ）×ｘ _ｉを求め、ξ _ｉ＝（Ａ _１，β _０，β _１，…，β _ｎ−１，ｚ _１，ｚ _２，…，ｚ _ｎ）を投票内容ｍに対する署名とする署名情報生成手段と、
投票内容ｍおよび当該投票内容ｍに対する署名ξ _ｉを電子投票として上記情報公開サーバに送信する送信手段と
を備えた電子投票装置。
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の秘密鍵ｘ _ｉを群Ｚ _ｑの元とし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙ _ｉ＝ｇ＾ｘ _ｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝が記憶されている情報公開サーバに対して電子投票を行う電子投票装置であって、
投票者ｉに固有の秘密鍵ｘ _ｉを記憶する記憶手段と、
上記情報公開サーバから、投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝を受信する受信手段と、
投票者ｉに固有の固有臨時公開鍵σ _ｉ＝Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｘ _ｉを求める固有臨時公開鍵生成手段と、
撹乱因子Ａ _１＝（σ _ｉ／Ｈ’（ｎ，ｙ _Ｎ，ｍ））＾（１／ｉ）を求める撹乱因子生成手段と、
ｎ−１個の撹乱臨時公開鍵σ _ｊ＝Ｈ’（ｎ，ｙ _Ｎ，ｍ）（Ａ _１＾ｊ）[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を求める撹乱臨時公開鍵生成手段と、
任意に選択した元ｗ _ｉ ∈Ｚ _ｑについてａ _ｉ＝ｇ＾ｗ _ｉとｂ _ｉ＝Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｗ _ｉを求め、各ｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]について任意に選択した２つの元ｚ _ｊ、ｃ _ｊ ∈Ｚ _ｑを用いて、ａ _ｊ＝（ｇ＾ｚ _ｊ）×（ｙ _ｊ＾ｃ _ｊ）とｂ _ｊ＝（Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｚ _ｊ）×（σ _ｊ＾ｃ _ｊ）を求め、ｃ _ｉ＝Ｈ”（ｎ，ｙ _Ｎ，ｍ，Ｈ（ｎ，ｙ _Ｎ，ｍ），Ｈ’（ｎ，ｙ _Ｎ，ｍ），Ａ _１，ａ _１，ａ _２，…，ａ _ｎ，ｂ _１，ｂ _２，…，ｂ _ｎ）−Σ _{j∈{1,…,n}-{i}} ｃ _j を求め、さらに、ｚ _ｉ＝ｗ _ｉ −ｃ _ｉ ×ｘ _ｉを求め、ξ _ｉ＝（Ａ _１，ｃ _０，ｃ _１，…，ｃ _ｎ，ｚ _１，ｚ _２，…，ｚ _ｎ）を投票内容ｍに対する署名とする署名情報生成手段と、
投票内容ｍおよび当該投票内容ｍに対する署名ξ _ｉを電子投票として上記情報公開サーバに送信する送信手段と
を備えた電子投票装置。
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙ _ｉ＝ｇ＾ｘ _ｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝と請求項１に記載の電子投票装置から送信された投票内容ｍに対する署名（以下、投票署名という）ξ _ｉ＝（Ａ _１，β _０，β _１，…，β _ｎ−１，ｚ _１，ｚ _２，…，ｚ _ｎ）とが記憶されている情報公開サーバから、少なくとも全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝および投票内容ｍに対する全ての投票署名ξ _１，…，ξ _ｅ（ｅ≦ｎ）を受信して、投票内容ｍに関する開票を行う開票装置であって、
上記情報公開サーバから、少なくとも全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝および投票内容ｍに対する全ての投票署名ξ _１，…，ξ _ｅを受信する受信手段と、
各投票署名ξ _１，…，ξ _ｅについてσ _ｆ＝Ｈ’（ｎ，ｙ _Ｎ，ｍ）（Ａ _１＾ｆ）[ｆ＝１，２，…，ｎ]を求める臨時公開鍵生成手段と、
各投票署名ξ _１，…，ξ _ｅについて、β（ｘ）＝β _ｎ−１ｘ＾（ｎ−１）＋β _ｎ−２ｘ＾（ｎ−２）＋…＋β _１ｘ＋β _０として、ａ’ _ｆ＝（ｇ＾ｚ _ｆ）×（ｙ _ｆ＾β（ｆ））[ｆ＝１，２，…，ｎ]とｂ’ _ｆ＝（Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｚ _ｆ）×（σ _ｆ＾β（ｆ））[ｆ＝１，２，…，ｎ]を求め、β（０）＝Ｈ”（ｎ，ｙ _Ｎ，ｍ，Ｈ（ｎ，ｙ _Ｎ，ｍ），Ｈ’（ｎ，ｙ _Ｎ，ｍ），Ａ _１，ａ’ _１，ａ’ _２，…，ａ’ _ｎ，ｂ’ _１，ｂ’ _２，…，ｂ’ _ｎ）が成立するか否かを判定する検証手段と、
上記判定に合格した投票署名の数ｖを計数し、さらに、上記判定に合格した投票署名に対応する各｛σ _１，…，σ _ｎ｝を比較して同一の値が含まれる投票署名を重複投票とし、当該重複投票の数τを上記計数結果ｖから引いて得られるｖ−τを有効投票総数とする計数手段と
を備えた開票装置。
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙ _ｉ＝ｇ＾ｘ _ｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝と請求項２に記載の電子投票装置から送信された投票内容ｍに対する署名（以下、投票署名という）ξ _ｉ＝（Ａ _１，ｃ _０，ｃ _１，…，ｃ _ｎ，ｚ _１，ｚ _２，…，ｚ _ｎ）とが記憶されている情報公開サーバから、少なくとも全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝および投票内容ｍに対する全ての投票署名ξ _１，…，ξ _ｅ（ｅ≦ｎ）を受信して、投票内容ｍに関する開票を行う開票装置であって、
上記情報公開サーバから、少なくとも全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝および投票内容ｍに対する全ての投票署名ξ _１，…，ξ _ｅを受信する受信手段と、
各投票署名ξ _１，…，ξ _ｅについてσ _ｆ＝Ｈ’（ｎ，ｙ _Ｎ，ｍ）（Ａ _１＾ｆ）[ｆ＝１，２，…，ｎ]を求める臨時公開鍵生成手段と、
各投票署名ξ _１，…，ξ _ｅについて、ａ’ _ｆ＝（ｇ＾ｚ _ｆ）×（ｙ _ｆ＾ｃ _ｆ）[ｆ＝１，２，…，ｎ]とｂ’ _ｆ＝（Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｚ _ｆ）×（σ _ｆ＾ｃ _ｆ）[ｆ＝１，２，…，ｎ]を求め、Σ _{j∈{1,…,n}} ｃ _j ＝Ｈ”（ｎ，ｙ _Ｎ，ｍ，Ｈ（ｎ，ｙ _Ｎ，ｍ），Ｈ’（ｎ，ｙ _Ｎ，ｍ），Ａ _１，ａ’ _１，ａ’ _２，…，ａ’ _ｎ，ｂ’ _１，ｂ’ _２，…，ｂ’ _ｎ）が成立するか否かを判定する検証手段と、
上記判定に合格した投票署名の数ｖを計数し、さらに、上記判定に合格した投票署名に対応する各｛σ _１，…，σ _ｎ｝を比較して同一の値が含まれる投票署名を重複投票とし、当該重複投票の数τを上記計数結果ｖから引いて得られるｖ−τを有効投票総数とする計数手段と
を備えた開票装置。
電子投票装置と、開票装置と、情報公開サーバとを含む電子投開票システムであって、
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の秘密鍵ｘ _ｉを群Ｚ _ｑの元とし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙ _ｉ＝ｇ＾ｘ _ｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、
上記情報公開サーバは、
投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝、投票内容ｍに対する署名（以下、投票署名という）を記憶可能な記憶手段と、
上記電子投票装置に対して、上記情報公開サーバの記憶手段に記憶される投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝を送信可能な対電子投票装置送信手段と、
上記電子投票装置から送信された投票署名を受信可能な対電子投票装置受信手段と、
上記開票装置に対して、少なくとも、上記情報公開サーバの記憶手段に記憶される全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝および投票内容ｍに対する全ての投票署名を送信可能な対開票装置送信手段と
を備えており、
上記電子投票装置は、
投票者ｉに固有の秘密鍵ｘ _ｉを記憶する記憶手段と、
上記情報公開サーバから、投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝を受信する受信手段と、
投票者ｉに固有の固有臨時公開鍵σ _ｉ＝Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｘ _ｉを求める固有臨時公開鍵生成手段と、
撹乱因子Ａ _１＝（σ _ｉ／Ｈ’（ｎ，ｙ _Ｎ，ｍ））＾（１／ｉ）を求める撹乱因子生成手段と、
ｎ−１個の撹乱臨時公開鍵σ _ｊ＝Ｈ’（ｎ，ｙ _Ｎ，ｍ）（Ａ _１＾ｊ）[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を求める撹乱臨時公開鍵生成手段と、
任意に選択した元ｗ _ｉ ∈Ｚ _ｑについてａ _ｉ＝ｇ＾ｗ _ｉとｂ _ｉ＝Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｗ _ｉを求め、各ｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]について任意に選択した２つの元ｚ _ｊ、ｃ _ｊ ∈Ｚ _ｑを用いて、ａ _ｊ＝（ｇ＾ｚ _ｊ）×（ｙ _ｊ＾ｃ _ｊ）とｂ _ｊ＝（Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｚ _ｊ）×（σ _ｊ＾ｃ _ｊ）を求め、β（０）＝Ｈ”（ｎ，ｙ _Ｎ，ｍ，Ｈ（ｎ，ｙ _Ｎ，ｍ），Ｈ’（ｎ，ｙ _Ｎ，ｍ），Ａ _１，ａ _１，ａ _２，…，ａ _ｎ，ｂ _１，ｂ _２，…，ｂ _ｎ）、β（ｊ）＝ｃ _ｊ [ｊ∈｛１，…，ｎ｝−｛ｉ｝]を満たす次数（ｎ−１）の多項式β（ｘ）＝β _ｎ−１ｘ＾（ｎ−１）＋β _ｎ−２ｘ＾（ｎ−２）＋…＋β _１ｘ＋β _０ ∈Ｚ _ｑ［ｘ］の係数β _φ （φ＝０，１，２，…，ｎ−１）を求め、さらに、ｚ _ｉ＝ｗ _ｉ −β（ｉ）×ｘ _ｉを求め、ξ _ｉ＝（Ａ _１，β _０，β _１，…，β _ｎ−１，ｚ _１，ｚ _２，…，ｚ _ｎ）を投票内容ｍに対する署名とする署名情報生成手段と、
投票内容ｍおよび当該投票内容ｍに対する署名ξ _ｉを電子投票として上記情報公開サーバに送信する送信手段と
を備えており、
上記開票装置は、
電子投票後に投票内容ｍに対する全ての投票署名ξ _１，…，ξ _ｅ（ｅ≦ｎ）を記憶する上記情報公開サーバから、少なくとも全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝および投票内容ｍに対する全ての投票署名ξ _１，…，ξ _ｅを受信する受信手段と、
各投票署名ξ _１，…，ξ _ｅについてσ _ｆ＝Ｈ’（ｎ，ｙ _Ｎ，ｍ）（Ａ _１＾ｆ）[ｆ＝１，２，…，ｎ]を求める臨時公開鍵生成手段と、
各投票署名ξ _１，…，ξ _ｅについて、β（ｘ）＝β _ｎ−１ｘ＾（ｎ−１）＋β _ｎ−２ｘ＾（ｎ−２）＋…＋β _１ｘ＋β _０として、ａ’ _ｆ＝（ｇ＾ｚ _ｆ）×（ｙ _ｆ＾β（ｆ））[ｆ＝１，２，…，ｎ]とｂ’ _ｆ＝（Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｚ _ｆ）×（σ _ｆ＾β（ｆ））[ｆ＝１，２，…，ｎ]を求め、β（０）＝Ｈ”（ｎ，ｙ _Ｎ，ｍ，Ｈ（ｎ，ｙ _Ｎ，ｍ），Ｈ’（ｎ，ｙ _Ｎ，ｍ），Ａ _１，ａ’ _１，ａ’ _２，…，ａ’ _ｎ，ｂ’ _１，ｂ’ _２，…，ｂ’ _ｎ）が成立するか否かを判定する検証手段と、
上記判定に合格した投票署名の数ｖを計数し、さらに、上記判定に合格した投票署名に対応する各｛σ _１，…，σ _ｎ｝を比較して同一の値が含まれる投票署名を重複投票とし、当該重複投票の数τを上記計数結果ｖから引いて得られるｖ−τを有効投票総数とする計数手段と
を備えている
電子投開票システム。
電子投票装置と、開票装置と、情報公開サーバとを含む電子投開票システムであって、
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の秘密鍵ｘ _ｉを群Ｚ _ｑの元とし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙ _ｉ＝ｇ＾ｘ _ｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、
上記情報公開サーバは、
投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝、投票内容ｍに対する署名（以下、投票署名という）を記憶可能な記憶手段と、
上記電子投票装置に対して、上記情報公開サーバの記憶手段に記憶される投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝を送信可能な対電子投票装置送信手段と、
上記電子投票装置から送信された投票署名を受信可能な対電子投票装置受信手段と、
上記開票装置に対して、少なくとも、上記情報公開サーバの記憶手段に記憶される全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝および投票内容ｍに対する全ての投票署名を送信可能な対開票装置送信手段と
を備えており、
上記電子投票装置は、
投票者ｉに固有の秘密鍵ｘ _ｉを記憶する記憶手段と、
上記情報公開サーバから、投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝を受信する受信手段と、
投票者ｉに固有の固有臨時公開鍵σ _ｉ＝Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｘ _ｉを求める固有臨時公開鍵生成手段と、
撹乱因子Ａ _１＝（σ _ｉ／Ｈ’（ｎ，ｙ _Ｎ，ｍ））＾（１／ｉ）を求める撹乱因子生成手段と、
ｎ−１個の撹乱臨時公開鍵σ _ｊ＝Ｈ’（ｎ，ｙ _Ｎ，ｍ）（Ａ _１＾ｊ）[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を求める撹乱臨時公開鍵生成手段と、
任意に選択した元ｗ _ｉ ∈Ｚ _ｑについてａ _ｉ＝ｇ＾ｗ _ｉとｂ _ｉ＝Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｗ _ｉを求め、各ｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]について任意に選択した２つの元ｚ _ｊ、ｃ _ｊ ∈Ｚ _ｑを用いて、ａ _ｊ＝（ｇ＾ｚ _ｊ）×（ｙ _ｊ＾ｃ _ｊ）とｂ _ｊ＝（Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｚ _ｊ）×（σ _ｊ＾ｃ _ｊ）を求め、ｃ _ｉ＝Ｈ”（ｎ，ｙ _Ｎ，ｍ，Ｈ（ｎ，ｙ _Ｎ，ｍ），Ｈ’（ｎ，ｙ _Ｎ，ｍ），Ａ _１，ａ _１，ａ _２，…，ａ _ｎ，ｂ _１，ｂ _２，…，ｂ _ｎ）−Σ _{j∈{1,…,n}-{i}} ｃ _j を求め、さらに、ｚ _ｉ＝ｗ _ｉ −ｃ _ｉ ×ｘ _ｉを求め、ξ _ｉ＝（Ａ _１，ｃ _０，ｃ _１，…，ｃ _ｎ，ｚ _１，ｚ _２，…，ｚ _ｎ）を投票内容ｍに対する署名とする署名情報生成手段と、
投票内容ｍおよび当該投票内容ｍに対する署名ξ _ｉを電子投票として上記情報公開サーバに送信する送信手段と
を備えており、
上記開票装置は、
電子投票後に投票内容ｍに対する全ての投票署名ξ _１，…，ξ _ｅ（ｅ≦ｎ）を記憶する上記情報公開サーバから、少なくとも全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝および投票内容ｍに対する全ての投票署名ξ _１，…，ξ _ｅを受信する受信手段と、
各投票署名ξ _１，…，ξ _ｅについてσ _ｆ＝Ｈ’（ｎ，ｙ _Ｎ，ｍ）（Ａ _１＾ｆ）[ｆ＝１，２，…，ｎ]を求める臨時公開鍵生成手段と、
各投票署名ξ _１，…，ξ _ｅについて、ａ’ _ｆ＝（ｇ＾ｚ _ｆ）×（ｙ _ｆ＾ｃ _ｆ）[ｆ＝１，２，…，ｎ]とｂ’ _ｆ＝（Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｚ _ｆ）×（σ _ｆ＾ｃ _ｆ）[ｆ＝１，２，…，ｎ]を求め、Σ _{j∈{1,…,n}} ｃ _j ＝Ｈ”（ｎ，ｙ _Ｎ，ｍ，Ｈ（ｎ，ｙ _Ｎ，ｍ），Ｈ’（ｎ，ｙ _Ｎ，ｍ），Ａ _１，ａ’ _１，ａ’ _２，…，ａ’ _ｎ，ｂ’ _１，ｂ’ _２，…，ｂ’ _ｎ）が成立するか否かを判定する検証手段と、
上記判定に合格した投票署名の数ｖを計数し、さらに、上記判定に合格した投票署名に対応する各｛σ _１，…，σ _ｎ｝を比較して同一の値が含まれる投票署名を重複投票とし、当該重複投票の数τを上記計数結果ｖから引いて得られるｖ−τを有効投票総数とする計数手段と
を備えている
電子投開票システム。
電子投票装置と、開票装置と、情報公開サーバとを含む電子投開票システムにおける電子投票方法であって、
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の秘密鍵ｘ _ｉを群Ｚ _ｑの元とし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙ _ｉ＝ｇ＾ｘ _ｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、
上記情報公開サーバの対電子投票装置送信手段が、上記電子投票装置に対して、上記情報公開サーバの記憶手段に記憶される投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝を送信する対電子投票装置送信ステップと、
上記電子投票装置の受信手段が、上記対電子投票装置送信ステップにおいて送信された投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝を受信する電子投票装置受信ステップと、
上記電子投票装置の固有臨時公開鍵生成手段が、投票者ｉに固有の固有臨時公開鍵σ _ｉ＝Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｘ _ｉを求める固有臨時公開鍵生成ステップと、
上記電子投票装置の撹乱因子生成手段が、撹乱因子Ａ _１＝（σ _ｉ／Ｈ’（ｎ，ｙ _Ｎ，ｍ））＾（１／ｉ）を求める撹乱因子生成ステップと、
上記電子投票装置の撹乱臨時公開鍵生成手段が、ｎ−１個の撹乱臨時公開鍵σ _ｊ＝Ｈ’（ｎ，ｙ _Ｎ，ｍ）（Ａ _１＾ｊ）[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を求める撹乱臨時公開鍵生成ステップと、
上記電子投票装置の署名情報生成手段が、任意に選択した元ｗ _ｉ ∈Ｚ _ｑについてａ _ｉ＝ｇ＾ｗ _ｉとｂ _ｉ＝Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｗ _ｉを求め、各ｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]について任意に選択した２つの元ｚ _ｊ、ｃ _ｊ ∈Ｚ _ｑを用いて、ａ _ｊ＝（ｇ＾ｚ _ｊ）×（ｙ _ｊ＾ｃ _ｊ）とｂ _ｊ＝（Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｚ _ｊ）×（σ _ｊ＾ｃ _ｊ）を求め、β（０）＝Ｈ”（ｎ，ｙ _Ｎ，ｍ，Ｈ（ｎ，ｙ _Ｎ，ｍ），Ｈ’（ｎ，ｙ _Ｎ，ｍ），Ａ _１，ａ _１，ａ _２，…，ａ _ｎ，ｂ _１，ｂ _２，…，ｂ _ｎ）、β（ｊ）＝ｃ _ｊ [ｊ∈｛１，…，ｎ｝−｛ｉ｝]を満たす次数（ｎ−１）の多項式β（ｘ）＝β _ｎ−１ｘ＾（ｎ−１）＋β _ｎ−２ｘ＾（ｎ−２）＋…＋β _１ｘ＋β _０ ∈Ｚ _ｑ［ｘ］の係数β _φ （φ＝０，１，２，…，ｎ−１）を求め、さらに、ｚ _ｉ＝ｗ _ｉ −β（ｉ）×ｘ _ｉを求め、ξ _ｉ＝（Ａ _１，β _０，β _１，…，β _ｎ−１，ｚ _１，ｚ _２，…，ｚ _ｎ）を投票内容ｍに対する署名とする署名情報生成ステップと、
上記電子投票装置の送信手段が、投票内容ｍおよび当該投票内容ｍに対する上記署名（以下、投票署名という）ξ _ｉ＝（Ａ _１，β _０，β _１，…，β _ｎ−１，ｚ _１，ｚ _２，…，ｚ _ｎ）を電子投票として上記情報公開サーバに送信する対情報公開サーバ送信ステップと、
上記情報公開サーバの対電子投票装置受信手段が、上記対情報公開サーバ送信ステップにおいて送信された投票署名ξ _ｉ＝（Ａ _１，β _０，β _１，…，β _ｎ−１，ｚ _１，ｚ _２，…，ｚ _ｎ）を受信する対電子投票装置受信ステップと、
上記情報公開サーバの記憶手段が、投票内容ｍに対する電子投票として受信した投票署名ξ _１，…，ξ _ｅ（ｅ≦ｎ）を記憶する情報公開サーバ記憶ステップと、
上記情報公開サーバの対開票装置送信手段が、上記開票装置に対して、少なくとも、全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝および投票内容ｍに対する全ての投票署名ξ _１，…，ξ _ｅを送信する対開票装置送信ステップと、
上記開票装置の受信手段が、上記対開票装置送信ステップにおいて送信された全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝および投票内容ｍに対する全ての投票署名ξ _１，…，ξ _ｅを受信する開票装置受信ステップと、
上記開票装置の臨時公開鍵生成手段が、各投票署名ξ _１，…，ξ _ｅについてσ _ｆ＝Ｈ’（ｎ，ｙ _Ｎ，ｍ）（Ａ _１＾ｆ）[ｆ＝１，２，…，ｎ]を求める臨時公開鍵生成ステップと、
上記開票装置の検証手段が、各投票署名ξ _１，…，ξ _ｅについて、β（ｘ）＝β _ｎ−１ｘ＾（ｎ−１）＋β _ｎ−２ｘ＾（ｎ−２）＋…＋β _１ｘ＋β _０として、ａ’ _ｆ＝（ｇ＾ｚ _ｆ）×（ｙ _ｆ＾β（ｆ））[ｆ＝１，２，…，ｎ]とｂ’ _ｆ＝（Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｚ _ｆ）×（σ _ｆ＾β（ｆ））[ｆ＝１，２，…，ｎ]を求め、β（０）＝Ｈ”（ｎ，ｙ _Ｎ，ｍ，Ｈ（ｎ，ｙ _Ｎ，ｍ），Ｈ’（ｎ，ｙ _Ｎ，ｍ），Ａ _１，ａ’ _１，ａ’ _２，…，ａ’ _ｎ，ｂ’ _１，ｂ’ _２，…，ｂ’ _ｎ）が成立するか否かを判定する検証ステップと、
上記開票装置の計数手段が、上記判定に合格した投票署名の数ｖを計数し、さらに、上記判定に合格した投票署名に対応する各｛σ _１，…，σ _ｎ｝を比較して同一の値が含まれる投票署名を重複投票とし、当該重複投票の数τを上記計数結果ｖから引いて得られるｖ−τを有効投票総数とする計数ステップと
を有する電子投開票方法。
電子投票装置と、開票装置と、情報公開サーバとを含む電子投開票システムにおける電子投票方法であって、
巡回群Ｇの生成元をｇとし、投票者総数をｎとし、投票者ｉ（１≦ｉ≦ｎ）の秘密鍵ｘ _ｉを群Ｚ _ｑの元とし、投票者ｉ（１≦ｉ≦ｎ）の公開鍵をｙ _ｉ＝ｇ＾ｘ _ｉとし、Ｈ，Ｈ’，Ｈ”をそれぞれハッシュ関数とし、
上記情報公開サーバの対電子投票装置送信手段が、上記電子投票装置に対して、上記情報公開サーバの記憶手段に記憶される投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝を送信する対電子投票装置送信ステップと、
上記電子投票装置の受信手段が、上記対電子投票装置送信ステップにおいて送信された投票内容ｍと全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝を受信する電子投票装置受信ステップと、
上記電子投票装置の固有臨時公開鍵生成手段が、投票者ｉに固有の固有臨時公開鍵σ _ｉ＝Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｘ _ｉを求める固有臨時公開鍵生成ステップと、
上記電子投票装置の撹乱因子生成手段が、撹乱因子Ａ _１＝（σ _ｉ／Ｈ’（ｎ，ｙ _Ｎ，ｍ））＾（１／ｉ）を求める撹乱因子生成ステップと、
上記電子投票装置の撹乱臨時公開鍵生成手段が、ｎ−１個の撹乱臨時公開鍵σ _ｊ＝Ｈ’（ｎ，ｙ _Ｎ，ｍ）（Ａ _１＾ｊ）[ｊ∈｛１，…，ｎ｝−｛ｉ｝]を求める撹乱臨時公開鍵生成ステップと、
上記電子投票装置の署名情報生成手段が、任意に選択した元ｗ _ｉ ∈Ｚ _ｑについてａ _ｉ＝ｇ＾ｗ _ｉとｂ _ｉ＝Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｗ _ｉを求め、各ｊ[ｊ∈｛１，…，ｎ｝−｛ｉ｝]について任意に選択した２つの元ｚ _ｊ、ｃ _ｊ ∈Ｚ _ｑを用いて、ａ _ｊ＝（ｇ＾ｚ _ｊ）×（ｙ _ｊ＾ｃ _ｊ）とｂ _ｊ＝（Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｚ _ｊ）×（σ _ｊ＾ｃ _ｊ）を求め、ｃ _ｉ＝Ｈ”（ｎ，ｙ _Ｎ，ｍ，Ｈ（ｎ，ｙ _Ｎ，ｍ），Ｈ’（ｎ，ｙ _Ｎ，ｍ），Ａ _１，ａ _１，ａ _２，…，ａ _ｎ，ｂ _１，ｂ _２，…，ｂ _ｎ）−Σ _{j∈{1,…,n}-{i}} ｃ _j を求め、さらに、ｚ _ｉ＝ｗ _ｉ −ｃ _ｉ ×ｘ _ｉを求め、ξ _ｉ＝（Ａ _１，ｃ _０，ｃ _１，…，ｃ _ｎ，ｚ _１，ｚ _２，…，ｚ _ｎ）を投票内容ｍに対する署名とする署名情報生成ステップと、
上記電子投票装置の送信手段が、投票内容ｍおよび当該投票内容ｍに対する上記署名（以下、投票署名という）ξ _ｉ＝（Ａ _１，ｃ _０，ｃ _１，…，ｃ _ｎ，ｚ _１，ｚ _２，…，ｚ _ｎ）を電子投票として上記情報公開サーバに送信する対情報公開サーバ送信ステップと、
上記情報公開サーバの対電子投票装置受信手段が、上記対情報公開サーバ送信手段において送信された投票署名ξ _ｉ＝（Ａ _１，ｃ _０，ｃ _１，…，ｃ _ｎ，ｚ _１，ｚ _２，…，ｚ _ｎ）を受信する対電子投票装置受信ステップと、
上記情報公開サーバの記憶手段が、投票内容ｍに対する電子投票として受信した投票署名ξ _１，…，ξ _ｅ（ｅ≦ｎ）を記憶する記憶ステップと、
上記情報公開サーバの対開票装置送信手段が、上記開票装置に対して、少なくとも、全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝および投票内容ｍに対する全ての投票署名ξ _１，…，ξ _ｅを送信する対開票装置送信ステップと、
上記開票装置の受信手段が、上記対開票装置送信ステップにおいて送信された全投票者の公開鍵ｙ _Ｎ＝｛ｙ _１，…，ｙ _ｎ｝および投票内容ｍに対する全ての投票署名ξ _１，…，ξ _ｅを受信する開票装置受信ステップと、
上記開票装置の臨時公開鍵生成手段が、各投票署名ξ _１，…，ξ _ｅについてσ _ｆ＝Ｈ’（ｎ，ｙ _Ｎ，ｍ）（Ａ _１＾ｆ）[ｆ＝１，２，…，ｎ]を求める臨時公開鍵生成ステップと、
上記開票装置の検証手段が、各投票署名ξ _１，…，ξ _ｅについて、ａ’ _ｆ＝（ｇ＾ｚ _ｆ）×（ｙ _ｆ＾ｃ _ｆ）[ｆ＝１，２，…，ｎ]とｂ’ _ｆ＝（Ｈ（ｎ，ｙ _Ｎ，ｍ）＾ｚ _ｆ）×（σ _ｆ＾ｃ _ｆ）[ｆ＝１，２，…，ｎ]を求め、Σ _{j∈{1,…,n}} ｃ _j ＝Ｈ”（ｎ，ｙ _Ｎ，ｍ，Ｈ（ｎ，ｙ _Ｎ，ｍ），Ｈ’（ｎ，ｙ _Ｎ，ｍ），Ａ _１，ａ’ _１，ａ’ _２，…，ａ’ _ｎ，ｂ’ _１，ｂ’ _２，…，ｂ’ _ｎ）が成立するか否かを判定する検証ステップと、
上記開票装置の計数手段が、上記判定に合格した投票署名の数ｖを計数し、さらに、上記判定に合格した投票署名に対応する各｛σ _１，…，σ _ｎ｝を比較して同一の値が含まれる投票署名を重複投票とし、当該重複投票の数τを上記計数結果ｖから引いて得られるｖ−τを有効投票総数とする計数ステップと
を有する電子投開票方法。
請求項１または請求項２に記載された電子投票装置としてコンピュータを機能させるための電子投票プログラム。
請求項３または請求項４に記載された開票装置としてコンピュータを機能させるための開票プログラム。