(57)【要約】強制に耐性のある電子選挙を実施するための設備を説明している。本設備は、投票者から最初の投票者の確認値を受信する。後に、本設備は、投票者から暗号化された票および第２の投票者確認値を受信する。受信された第２の投票者の確認値の値にかまわずに、本設備は、投票された票の公的に使用可能なリストに、受信した票を加える。この付加の後、公衆のメンバーは、受信された票がカウントされるかどうか判断することはできないが、リストへの受信された票の付加を検証することができる。本設備は、票とともに受信された第２の投票者の確認値が第１の投票者の確認値に一致する場合に限って、この票をカウントする。
2005526307.tif 000002
【特許請求の範囲】
【請求項１】
強制に耐性のある電子選挙を実施する方法であって、
投票者から第１の投票者確認値を受信するステップと、
前記第１の投票者確認値を受信した後、投票者から暗号化された票および第２の投票者確認値を受信するステップと、
前記受信した第２の投票者確認値の値にかかわらず、公衆のメンバーが、票がカウントされるかどうか判断できないが前記リストへの前記受信した票の付加を検証できるように、公的に使用可能な、投票された票のリストに受信した票を加えるステップと、
前記票ととともに受信した前記第２の投票者確認値が前記受信した第１の投票者確認値に一致する場合に限り、前記票をカウントするステップと、
を備えることを特徴とする強制に耐性のある電子選挙を実施する方法。
【請求項２】
投票者から第１の投票者確認値を受信するステップと、
前記第１の投票者確認値を受信した後、投票者から暗号化された票および第２の投票者確認値を受信するステップと、
前記受信した第２の投票者確認値の値にかかわらず、公衆のメンバーが、票がカウントされるかどうか判断できないが前記リストへの前記受信した票の付加を検証できるように、公的に使用可能な、投票された票のリストに受信した票を加えるステップと、
前記票ととともに受信した前記第２の投票者確認値が前記受信した第１の投票者確認値に一致する場合に限り、前記票をカウントするステップと、
によりコンピューティングシステムに強制に耐性のある電子選挙を実施させるコンテンツを備えるコンピュータ読み取り可能な媒体。
【請求項３】
投票者によって構成される１つの投票された票のデータ構造をまとめて搬送する１または複数の生成されたデータ信号であって、
１つの暗号化された票の選択、および
１つの票の確認値であって、
前記票の確認値にかかわらず、公的に使用可能な、投票された票のリストに前記票を加えることができ、
前記票の確認値が前記投票者に対して先に格納されたオリジナルの票の確認値に一致するかどうかに基づき、前記投票された票をカウントするかどうか判断することができるような票の確認値を備えることを特徴とするデータ信号。
【請求項４】
投票される票を格納する投票箱データ構造をまとめて備える１または複数のコンピュータメモリであって、前記投票箱データ構造は、各格納される票に対し、
前記票を生成した投票者によって選ばれた票の選択を反映するデータ、および
前記投票者によって選ばれた確認値を反映するデータを備え、
前記データ構造の中身が、前記票をカウントするかどうか判断するために投票集計オーソリティによって使用することができ、
前記データ構造の中身が、前記票が投票箱に格納されたことを判断するために票集計オーソリティとは異なるサードパーティによって使用することができ、および
前記データ構造の中身が、前記票がカウントされるかどうか判断するために前記サードパーティによって使用することができないことを特徴とするコンピュータメモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、電子的に実施される選挙に対する安全な方法の技術分野を対象としている。
【背景技術】
【０００２】
投票者に対する暗号化プライバシーを提供する様々な電子的なおよび／またはデジタルの選挙プロトコルがある。これらの選挙プロトコルの多くを使用して、投票者は、ある種の情報シークレットを保つ必要がある。このような秘密情報の一例が、投票者のプライベートキーである。しかしながら、ある者が投票者を脅迫したり、（例えば、金融的に）誘惑したりして、秘密情報を手放すようにさせる場合、これらの実存する選挙プロトコルには問題がありうる。この種の強制（ｃｏｅｒｃｉｏｎ）が起こると、ある者は、投票者がどのように投票したか知ることも、彼や彼女に代わって投票することも可能となる。
【０００３】
同様の問題が、メールによる不在投票システムを使用すると発生する。例えば、夫が妻にある方法で投票するように強いるという場合があるかもしれない。強制の脅迫は、ネットワークの世界で増大している。そこでは、人々は、数千マイル離れたところから「互いに覗き込む」ことができる。この脅迫は、しばしば、遠隔電子投票を許可しない理由とされるのに十分なものである。
【０００４】
強制を含まない脅迫モデルの下で、例外なく検証できる選挙の概念（ｎｏｔｉｏｎ）は必須である。過去には、「コンピュータ装置に基づく」選挙スキームは、広い範囲に配置可能であることが考慮されるために、例外なく検証できることが重要であると考えられてきた。この種の選挙の間、最終集計を含む交信記録が発行される。キーの安全について妥当な仮定およびいくつかの計算問題の至難性の下で、これらの交信記録は、悪意のあるエージェントの任意の収集によって都合よく偽造することはできない。強制の脅迫の下で、選挙スキームにこの特性を持ち込むことが望ましいが、これは困難なものでありうる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
強制の脅迫の下での選挙スキームは、ある非常に基本的な、一般に選挙プロトコルの文献に当然のように採用されている特性を欠いているので、大規模の実施においては実用的でないかもしれない。
【課題を解決するための手段】
【０００６】
本明細書で説明するスキームは、投票者が、投票するために投票者によって使用される秘密情報を排他的に所有したままでいることを可能とする。これは、秘密情報を漏らすように強要された投票者が、発見されることなく誤った回答を提供することを可能とする。誤った回答を提供した後に、この投票者は手続きをすることができ、彼または彼女自身で「真の」投票をすることができる。これは、まだ良い電子選挙プロトコルの特性である選挙監査特性（ｅｌｅｃｔｉｏｎ  ａｕｄｉｔ  ｐｒｏｐｅｒｔｉｅｓ）を収集（ｃｏｌｌｅｃｔｉｏｎ）している間にも達成される。強制脅迫モデルにおいてさえ、一緒に投票集計をすることができないいかなるオーソリティの共謀によって交信記録を都合よく偽造することができないなら、選挙スキームは、強制に対し安全である。さらに、投票集計を計算することができる共謀の場合においても、偽造の程度は、強制された投票者の数によって制限される。
【０００７】
要約すると、本発明は以下のように機能する。
【０００８】
１．投票者は、選挙を開始する前に、秘密の「投票者登録」プロセスに参加する。このプロセスは、標準の物理的な方法によって投票者を強制から安全にしなければならない。実際にはこれは、投票者が、物理的なプライバシーが保証される、郡（ｃｏｕｎｔｙ）の登録センターに報告しなければならないことを意味する。しかし、投票者は、この登録手続きにおいて一度だけ参加する必要があるだけである。その後、本発明の方法は、複数の選挙を通じて投票者を強制から保護するであろう。
【０００９】
２．登録プロセスの間、各投票者は、秘密の「確認コード」または「確認パスフレーズ（ｃｏｎｆｉｒｍａｔｉｏｎ  ｐａｓｓ  ｐｈｒａｓｅ）」を選択する。
【００１０】
３．「確認パスフレーズ」は、投票者によって暗号化される。そして、暗号化された形態（ｆｏｒｍ）がその投票者に対して公的に登録される。
【００１１】
４．投票するために、各投票者は、添付の（暗号化された）パスフレーズを提供しなければならない。添付のパスフレーズは、票が受け入れられるか否かに関してはいかなる効果ももたない。このため、投票者が、強制者によって「管理されている」場合、投票者は、それがこの投票者の登録されたパスフレーズに一致しようがしまいが、まだ任意のパスフレーズを自由に提供することができる。強制者は、この相違を見分けることができないであろう。しかし、添付のパスフレーズは、このパスフレーズが付随する票がカウントされるか否かに影響を与えるであろう。（次に説明する）このためのメカニズムは、いずれにせよ、以下のことを保証する。
【００１２】
（ａ）  強制者を含む何人も、投票集計が正確であろうがなかろうが、確定するために投票箱の中身および投票集計を調べることができる（すなわち、選挙は例外なく検証可能である）。
【００１３】
（ｂ）  選挙データが十分に使用可能であっても、投票者による任意の投票が実際にカウント（ｃｏｕｎｔ）に含まれているなら、暗号化計数メカニズム（ｔｈｅ  ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  ｃｏｕｎｔ  ｍｅｃｈａｎｉｓｍｓ）により、強制者はまだ何の投票であるかを判断することができないであろうことを保証される。
【００１４】
５．暗号化された票の集計（カウント）は、投票された票（暗号化パスフレーズ対ならびにオリジナルの登録データ）をランダムに混ぜることによって大雑把に遂行される。ランダム化の後、適切なデータが、暗号化キーを共有している選挙オーソリティによって復号化される。ランダム化された票データ中のパスフレーズにおける一致（ａ  ｍａｔｃｈ）がランダム化された登録データ中のパスフレーズに一致するときのみ、その票をカウントする。このマッチングは、どちらのパスフレーズも復号化することなしになされる。すべてのランダム化は、暗号化検証可能シャッフルの方法でなされるので、結果は、まだ、正確を期して何人によっても検査を受けることができ、検証されることができる。
【発明を実施するための最良の形態】
【００１５】
図１および以下の説明は、本発明の態様を実施することができる好適なコンピューティング環境の簡略化された一般的な説明を提供する。必須ではないが、本発明の態様および実施形態は、サーバまたはパーソナルコンピュータなどの汎用コンピュータによって実行されるルーチンなどのコンピュータ実行可能な命令の一般的なコンテキストで記述されるであろう。当業者は、インターネット機器、ハンドヘルド装置、ウェアラブルコンピュータ、セルラー電話または携帯電話、マルチプロセッサシステム、マイクロプロセッサベースのまたはプログラム可能な家庭用電化製品、セットトップボックス、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータなどを含む、他のコンピュータシステム構成で実施することができることを理解されよう。本発明は、以下に詳細を説明するコンピュータ実行可能命令の１つまたは複数を実行するために、特にプログラムされ、構成されまたは構築される専用のコンピュータまたはデータプロセッサにおいて実施することができる。実際には、「コンピュータ」という用語は、一般に用いられているように本明細書では、任意の上記装置ならびに任意のデータプロセッサを言う。
【００１６】
本発明は、分散コンピューティング環境においても実施することができる。この環境では、タスクまたはモジュールは、ローカルエリアネットワーク（「ＬＡＮ」）、ワイドエリアネットワーク（「ＷＡＮ」）、またはインターネットなどの通信ネットワークを介してリンクされる遠隔処理装置によって実行される。分散コンピューティング環境では、プログラムモジュールまたはサブルーチンは、ローカルメモリ記憶装置および遠隔メモリ記憶装置の両方に置くことができる。以下に説明する本発明の態様は、磁気的および光学的読み取り可能、および、取り出し可能なコンピュータディスクを含むコンピュータ読み取り可能な媒体に格納または配信することができ、チップ（ＥＥＰＲＯＭチップなど）にファームウェアとして格納することができ、ならびに、インターネットや（無線ネットワークを含む）他のネットワークを介して電子的に配信することができる。当業者は、本発明の一部は、サーバコンピュータに置くことができ、一方、対応する部分をクライアントコンピュータに置くことができることを理解されよう。本発明の態様に特有のデータ構造およびデータ伝送もまた、本発明の範囲に含まれる。
【００１７】
図１を参照すると、本発明の一実施の形態は、１または複数のユーザ入力装置１０２およびデータ記憶装置１０４に接続される１または複数のプロセッサ１０１を有する、パーソナルコンピュータまたはワークステーションなどのコンピュータ１００を使用する。コンピュータはまた、表示装置１０６および１または複数の任意追加の出力装置１０８（例えば、プリンタ、プロッタ、スピーカ、触覚または嗅覚出力装置）などの少なくとも１つの出力装置に接続される。コンピュータは、任意追加のネットワーク接続１１０、無線トランシーバ１１２または両方を介してなど、外部のコンピュータに接続することができる。
【００１８】
入力装置１０２は、キーボードおよび／またはマウスなどのポインティング装置を含むことができる。他の入力装置は、マイクロフォン、ジョイスティック、ペン、ゲームパッド、スキャナ、デジタルカメラ、ビデオカメラなどがありうる。データ記憶装置１０４は、磁気ハードディスクドライブおよびフロッピー（登録商標）ディクスドライブ、光ディスクドライブ、磁気カセット、テープドライブ、フラッシュメモリカード、デジタルビデオディスク（ＤＶＤｓ）、ベルヌーイカートリッジ、ＲＡＭ、ＲＯＭ、スマートディスクなど、コンピュータ１００によってアクセス可能なデータを格納することができる、任意の種類のコンピュータ読み取り可能な媒体を含むことができる。実際には、コンピュータ読み取り可能な命令およびデータを格納または伝送するための任意の媒体を使用することができ、この媒体は、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）またはインターネット（図１にて図示せず）などのネットワークへの接続ポートを含む。本発明の態様は、様々な他のコンピューティング環境でも実施することができる。
【００１９】
図２は、本スキームにより典型的に実行されるステップを示すフロー図である。これらのステップは、以下にて詳細に説明する。ステップ２０１では、投票する資格のある、登録された投票者のリストに加えるため、および彼らに投票の証明書を提供するために、投票者が登録される。ステップ２０２では、候補者達に票の選択値を割り当てるために、選挙が初期化される。２０３では、投票者は、暗号化された票を提出することによって投票する。２０４では、ステップ２０３で投票された票が集計され、受信された票の有効性が検証できた場合のみ票の合計に加えられる。
【００２０】
１  分割可能な集計に関する強制の影響
このセクションの目的は、
１つめは、先に検討された莫大な大多数のスキームを含む、大規模に対して「実用的」であるすべてのスキームを含むようにも見える、選挙スキームのクラスを特徴づけることにある。  
２つめは、強制脅迫モデルの下でこのクラスのスキームによって達成されうるものに関するいくつかの限界（ｂｏｕｎｄ）を確立することにある。
【００２１】
［定義１］
これからは、選挙プロセスにおける任意の参加者を、または、選挙プロセス上の影響を与えるまたは与えようと試みる任意の個人を、プレーヤーと呼ぶ。したがって、投票者、選挙管理人、および集計者は、すべてプレーヤーである。しかし、たとえその中に公的役割をもつことができないとしても、選挙結果に影響しようとするすべての個人もプレーヤーである。
【００２２】
［定義２］
プレーヤーＰ２に、プレーヤーＰ１に対して漏らすことを選挙プロトコルが要求しない任意の情報をＰ１がＰ２から得ている場合、プレーヤーＰ１はプレーヤーＰ２を強制する。同一の用語が、強制者が実際に複数のプレーヤーからなるグループである場合に使用される。すなわち、本発明の態様は、その実用を、強制者が単一の個人である場合に制限するものではない。したがって、以降は、個人による強制と行動を共にする複数の個人からなるグループによる強制との間で明確に区別することはしない。
【００２３】
［定義３］
強制的な情報とは、真偽が強制者によって「検証」できるすべての情報のことである。もし真偽が検証できない場合、投票者（または、強制されている個人）は、強制者に対してそれについて自由にうそをつくことができる。
【００２４】
［定義４］
投票集計は、関数
【００２５】
【数１】
2005526307.tif 000003
【００２６】
ただし、Г＝｛ｃ１，・・・，ｃｌ｝は「候補者名簿」、であることを思い出されたい。これを以下のように書き表す。
【００２７】
【数２】
2005526307.tif 000004
【００２８】
本発明は、概ねデジタル投票ボックスのようなものを必要とする。最低でも、これは投票者にオープンにアクセス可能なネットワークまたは他のものに接続される記憶装置である。標準のｗｅｂサーバおよびデータベースアプリケーションは、このような装置の一実施形態を提供する。実際には、さらに安全な方法が、悪意のある力または自然の力によって引き起こされる損傷や破壊に対して保護するために、この装置に組み込まれるかこの装置を中心に組み立てられるであろう。本発明はまた、投票者が彼らの選択をデジタル表現に変換することができ、さらに本発明の残りに提示される方法によってこのデジタル表現を暗号化することができることを要求する。一般のＰＣはこのような装置の一実施の形態を提供する。
【００２９】
［定義５］
情報の伝送および記憶は、伝送および記憶を容易にする特定の技術というよりむしろ本発明のキー要素であるので、オープンにアクセス可能な記憶装置を示すさらに一般的な用語である“掲示板”を採用するであろう。また掲示板上に（または中に）情報を記録する行為を投稿（ｐｏｓｔｉｎｇ）と表す。（選挙コンテキストにおいて、これは直感的に「投票」の行為に該当する。）さらに、文字列、またはポストとして掲示板に投稿される情報の記録を意味する。（選挙コンテキストにおいて、これらは直感的に投票された票に該当する。）
【００３０】
今、選挙プロトコルの広いクラス（ｂｒｏａｄ  ｃｌａｓｓ）を特徴付ける非常に一般的な特性の一組を考えるとする。特性は、強制を除外して考えられる。すなわち、特定のプロトコルについて所定の特性を検証する際には、プレーヤー間で交換される唯一の情報がそのプロトコルによって明記される情報である、すべての考えられるプロトコルの執行（ｐｏｔｅｎｔｉａｌ  ｐｒｏｔｏｃｏｌ  ｅｘｅｃｕｔｉｏｎｓ）が考慮される。（これらの特性に、ＰＰ−１、ＰＰ−２などのようにして順次番号を付ける。）
【００３１】
ＰＰ−１．  投稿メッセージ（ｐｏｓｔｓ）は常に掲示板ＢＢに付け足される。すなわち削除は許可されない。投稿は、自動のトランザクションであり、すなわち、任意の所定時刻に、ＢＢは、ある非負の整数ｋについて、正確にｋ個の投稿メッセージを含むであろう。
【００３２】
ＰＰ−２．  任意のプレーヤーは、ＢＢの状態（コンテンツ）にかかわらず投稿メッセージ付け足すことができる。
【００３３】
ＰＰ−３．  任意の所定時刻に、投票集計を形成することができ、この投票集計は一つしか存在しない。すなわち、ＢＢがある状態で、集計について「無効」であるＣ（ＢＢ）、および投票集計（ｔａｌｌｙ）、
【００３４】
【数３】
2005526307.tif 000005
【００３５】
が明確（ｗｅｌｌ  ｄｅｆｉｎｅｄ）であることはありえない（または、少なくとも「圧倒的に起こりそうもない」）。
【００３６】
ＰＰ−４．  プレーヤーの収集（ｃｏｌｌｅｃｔｉｏｎ）は、ＢＢの状態から独立した投票集計を計算することができるかできないかである。
【００３７】
投票者の役割（ｖｏｔｅｒ  ｒｏｌｅ）Ｏは、本質的にはプレーヤー（資格のある投票者）の公的なリスト｛ｖ１，・・・，ｖｋ｝であることを思い出されたい。また、任意の時刻にＢＢの中身、すなわち、投稿メッセージｐ１，・・・，ｐｔのシーケンスを示すＣ（ＢＢ）を使用する。Ｐがこのプロトコルですべてのプレーヤーの集合であるとすると、Ｏ⊂Ｐである。
【００３８】
簡単に表すため、票が１つの発行物からなり、候補者Γが｛ｃ１，・・・，ｃｌ｝によって与えられ、各投票者は、「高々１人の」候補者を選ぶ（のために投票する）ことができると仮定する。さらに一般的な投票の形式（ｂａｌｌｏｔ  ｔｙｐｅｓ）（「書き込み（Ｗｒｉｔｅ−ｉｎｓ）」を含めず）を含むものにこの設定を一般化することは、かなり容易である。
【００３９】
［定義６］
Ｃ＝Ｃ（ＢＢ）が、ＢＢ（投稿メッセージのシーケンス）の任意の状態であるとする。もしρが投稿メッセージである場合、
【００４０】
【数４】
2005526307.tif 000006
【００４１】
によって、単一の投稿メッセージρを付加後のＢＢの状態を示す。投票集計ｔａｌｌｙ（Ｃ）を示すために表記ｔＣも使用する。
【００４２】
［定義７］
（ＢＢ上の）投票関数は、写像
【００４３】
【数５】
2005526307.tif 000007
【００４４】
であり、以下によって特徴付けられる。  
Ｖｆ−１．  すべてのｐ∈Ｐに対して、
【００４５】
【数６】
2005526307.tif 000008
【００４６】
ｖｆ−２．  すべてのＣ（ＢＢ）に対して、
【００４７】
【数７】
2005526307.tif 000009
【００４８】
であるとき、（「圧倒的に起こりえない」が）
【００４９】
【数８】
2005526307.tif 000010
【００５０】
直感的には、これは、このプロトコルが、「投票者の役目（資格のある投票者）のメンバーが投票することを許可されるだけである」ことを言っている。
【００５１】
Ｖｆ−３  すべてのｐ∈Ｐに対し、ｐがρを投稿する場合、すべてのｑ∈Ｐに対して下式を保つ（「圧倒的に起こりえないが」）、
【００５２】
【数９】
2005526307.tif 000011
【００５３】
直感的には、これは、このプロトコルが、「投票者が自分自身のために投票することを許可するだけである」ことを言っている。これは、複数の投票者が彼らの票を１または複数の投稿メッセージに結合することを可能とするスキームを除外する。
【００５４】
Ｖｆ−４  すべての１≦ｉ≦ｌ、およびすべての１≦ｊ≦ｋに対して、｜χ（ｖｉ，Ｃ（ＢＢ））｜＝０である場合、ｖｉは、下式が成り立つような投稿メッセージρを（確率１で）計算することができる。
【００５５】
【数１０】
2005526307.tif 000012
【００５６】
直感的には、これは単純に、ｖｉが「まだ投票していない」場合、ｖｉは任意の候補者に対して「票」を付加することができる。しかし、ｖｉが「投票をし」その後に「それを変更する」ことをこのプロトコルが許可することができるという可能性を、この記述は排除しない。（それにもかかわらず、文字通りプロトコルの多くは、本質的には、各投票者に「投票する唯一のチャンス」を許可するものであり、この基準を満足する。）
Ｖｆ−５．  すべての１≦ｉ≦ｌに対して、｜χ（ｖｉ，Ｃ（ＢＢ））｜＝１である場合、ｖｉは、最大でも無視できる程度の確率で、
【００５７】
【数１１】
2005526307.tif 000013
【００５８】
を満たす投稿メッセージρを計算することができる。
【００５９】
直感的には、これは、単純に、どの投票者も「１度より多く投票する」ことができないことを言っている。しかし、この場合もやはり、この記述は、プロトコルが投票者に「投票を変更する」または「投票を撤回する」ことを許可することができる可能性を排除しない。（前述と同様に、文字通りプロトコルの多くは、この基準を満たす。）
【００６０】
Ａｉｊを、
【００６１】
【数１２】
2005526307.tif 000014
【００６２】
を満たす投稿メッセージρを、ｖｉが計算するイベントであるとする。
【００６３】
Ｂｉｊを、χ（ｖｉ，Ｃ（ＢＢ））（ｃｊ）＝１であるイベントであるとする。
【００６４】
Ｖｆ−６．  すべての１≦ｉ≦ｌ、およびすべての１≦ｊ≦ｋに対して、条件付確率Ｐ（Ａｉｊ｜Ｂｉｊ）が、ｉ，ｊの値および掲示板の状態から独立した
【００６５】
【数１３】
2005526307.tif 000015
【００６６】
を満たすような定数α（０≦α≦１）が存在する。
【００６７】
直感的には、これは、プロトコルが「１人の投票者がときどき投票を変更すること」を許可するなら、プロトコルは「任意の投票者がいつでも投票を変更すること」を許可するということを言っている。しかしながら、これは、文字通りもっと一般的である、プロトコルが投票の変更を禁じることを防がない。
【００６８】
Ｖｆ−７．  すべての１≦ｉ≦１、およびすべての１≦ｊ≠η≦ｋに対して、条件付確率Ｐ（Ａｉｊ｜Ｂｉη）は、
【００６９】
【数１４】
2005526307.tif 000016
【００７０】
ここで、ε  ≧  ０は無視できる。
【００７１】
直感的には、これは、プロトコルが、「その投票者がその立候補者に対して投票した」場合に限り、「投票者が立候補者に対してカウントを減らすこと」を許可するということを言っている。これもまた、このプロトコルが投票の変更を禁じることを防がない。
【００７２】
ＰＰ−５．  このプロトコルは、投票関数を認める。（これは、投票関数が、任意のプレーヤーによって計算可能であるということを要求するものではなく、ただそれが存在することを必要とするだけであることに注意されたい。）
［定義８］
選挙プロトコルは、ＰＰ−１〜ＰＰ−５を満たすときに限り分割集計をもつと言われている。簡単のために、分割集計をもつ任意の選挙プロトコルを説明するために分割集計プロトコルという用語もまた使用するであろう。
【００７３】
［定理１］
もし、ある選挙プロトコルが分割集計をもつ場合、かつ強制者が投票集計を計算することができるプレーヤーのコレクションを含む場合、任意の１≦ｉ≦ｌに対して、χ（ｖｉ，Ｃ（ＢＢ））の値は、強制的である。
【００７４】
［証明］
（概略）強制者は、投票ボックスのイメージのシーケンスを通して、各ポイントで、投票集計を計算するステップと（ＰＰ−４の仮定を参照されたい）、ｖｉが特定値の「票に加える」ことを要求するステップとを進めることができる。添付されたｖｉの投稿メッセージを使って投票集計を再計算することによって、強制者はどの投稿メッセージが、ｖｉおよび投票集計の蓄積効果によって加えられたかを判断することができる。
【００７５】
これは、「事後に」強制が許されるモデルを仮定することに注意されたい。すなわち、掲示板が閉ざされた後に、強制者は投票者と互いに交流できる。しかし、この仮定は、投票者の演算能力に関して合理的な仮定で排除することができる。特に、強制者が、単一の強制イベントを手段として、
１．選挙の経過の間、投票者のふりをすることができ（これによって、「任意の選択された投票を掲示板（投票箱）に加えること」、および続けて選挙の写しの「一部」を偽造すること）、
２．投票を独立して変更するために投票者による任意の試みを検出することができる、ことを示すことができる。
【００７６】
［定義９］
分割可能選挙プロトコルは、投票集計を独立して計算することができる強制者が存在しないという仮定の下で、もし、
ＣＳ−１．  ｐ∈Ｐかつｖｉ∈Ｏ、ｖｉ≠ｐの場合、ｐは、「あてずっぽう（ｒａｎｄｏｍ  ｇｕｅｓｓ）＋ε」より高い確率でχ（ｖｉ，  Ｃ（ＢＢ））を計算することができない。  
ＣＳ−２．  選挙結果は、公的に検証可能である、
ならば、強制の耐性（ｃｏｅｒｃｉｏｎ  ｒｅｓｉｓｔａｎｔ）がある。
【００７７】
［定義１０］
分割可能選挙プロトコルは、それが強制の耐性がありかつ、すべての共謀のシナリオのもとで、もし、
ＣＳ−３．  ｔＩが、「本当の投票集計」である場合、選挙の検証が、
【００７８】
【数１５】
2005526307.tif 000017
【００７９】
を保証する、ならば、強制に安全（ｃｏｅｒｃｉｏｎ  ｓａｆｅ）である。
【００８０】
２  強制に安全な選挙プロトコル
標準のエルガマル（ＥｌＧａｍａｌ）暗号化設定を仮定する。すなわち、ｐおよびｑは、ｑ｜ｐ−１を満たす大きな素数である。Ａはサブグループジェネレータ（ｓｕｂｇｒｏｕｐ  ｇｅｎｅｒａｔｏｒ）、｜ｇ｜＝ｑを満たす
【００８１】
【数１６】
2005526307.tif 000018
【００８２】
およびｎ個の集計オーソリティーＡ１，・・・，Ａｎ間のａ（ｔ，ｎ）スレッショルドスキーム（ｔｈｒｅｓｈｏｌｄ  ｓｃｈｅｍｅ）によって共有されるｓに関しｈ＝ｇｓである。
【００８３】
次に説明するプロトコルは、強制の耐性がある。それがどのようにして、強制に安全なプロトコルを与えるために、簡単に拡大することができるか後で説明する。最初により弱いバージョンを説明するのは、その構成中に多くの困難性があることから好都合である。
【００８４】
２．１  登録
登録セッションの間、投票者が強制から安全であることを仮定していることを思い出されたい。登録の間に交換される情報がその後強制的でないことを保証するようにまだ注意しなければならない。  
投票者をｖｉによって表す。
【００８５】
Ｒ−１．  ｖｉは、１つのランダムなｒｉ∈＜ｇ＞および１つのランダムな
【００８６】
【数１７】
2005526307.tif 000019
【００８７】
を選択し、
【００８８】
【数１８】
2005526307.tif 000020
【００８９】
を形成する。
【００９０】
Ｒ−２．  各１≦ｊ≦ｎに対し、
Ｒ−２．１．  ｖｉは、Ａｊから、（１２）式によって与えられる対（Ｕｉｊ，  Ｗｉｊ）を得る。
【００９１】
【数１９】
2005526307.tif 000021
【００９２】
ここで、βｉｊ∈＜ｇ＞は、Ａｊによってランダムに選択される。  
Ｒ−２．２．  ｖｉおよびＡｊは、関係ｌｏｇｇＵｉｊ＝ｌｏｇｈＷｉｊについて、対話型のチョム−ペダーセン（Ｃｈａｕｍ−Ｐｅｄｅｒｓｅｎ）の有効性の証明を実行する。すなわち、チャレンジ（ｃｈａｌｌｅｎｇｅ）が、ハッシュ関数（フィアット−シャミア（Ｆｉａｔ−Ｓｈａｍｉｒ）の経験則（ｈｅｕｒｉｓｔｉｃ）を介してというより、むしろｖｉによってランダムに生成される。これにより、ｖｉが、後に強制に直面して、シミュレートされた証明を作成することができる。
【００９３】
Ｒ−３．  各チョム−ペダーセン証明のチェックの後、ｖｉは、
【００９４】
【数２０】
2005526307.tif 000022
【００９５】
を計算する。
【００９６】
Ｒ−４．  各１≦ｊ≦ｎに対して、ｖｉは、受領証としてＡｊから（Ｕｉ，  Ｗｉ）の署名を得る。
【００９７】
Ｒ−５．  （Ｕｉ，  Ｗｉ）は、投票者の役割、Ｏに加えられる。登録期間が終了すると、各オーソリティは、Ｏにサインしなくてはならない。
【００９８】
［注釈１］
ｖｉは、１つの特定のオーソリティＡＪが強制者でなく、ｔより少ないオーソリティ（投票集計を計算するのに必要な数）しか、強制するために（ｖｉはかれらの身元を明確に知ることができない）共謀していないことを知っている限りは、ｒｉの値は、強制的ではない。これは、（ＵｉＪ，ＶｉＪ）の値について強制者にうそをつくことおよび偽造された（すなわち、シミュレートされた）チョム−ペダーセン証明を与えることによって、ｖｉが、任意のｒｉおよびαｉの有効性を証明することができるからである。
【００９９】
ｖｉが１人の特定の正直なＡｊを知っているという要求は、ｖｉが強制者にうそをつくことをキャッチされることを容認できると仮定する場合、緩めることができる。あるいは、もしｎ≫ｔの場合、ｖｉは１≦Ｊ≦ｎである１つのＪをランダムに拾うことができ、Ａｊが正直であると仮定すると、うそをつくことをキャッチされる確率がたかだか（ｔ−１）／ｎであることがわかる。
【０１００】
２．２  選挙の初期化
ＥＩ−１．  各１≦ｊ≦ｎに対して、および各１≦ｉ≦ｌ＝｜Ｏ｜に対して、オーソリティＡｊは、ランダムにかつ独立して＜ｇ＞中の要素の対（ξｉｊ，ηｉｊ）を生成する。
【０１０１】
【数２１】
2005526307.tif 000023
【０１０２】
この量は公的に計算される。これらは、すべて発行される（かつ署名される）。
【０１０３】
ＥＩ−２．  票の選択γμ∈＜ｇ＞、１≦μ≦ｋ＝｜Γ｜は、ある公的なランダムプロセスによって、またはシェアリングによって割り当てられる。（γμの値は、立候補者ｃμに対する票を示すであろう。）
２．３  投票
Ｖ−１．  ｖｉは、ランダムな
【０１０４】
【数２２】
2005526307.tif 000024
【０１０５】
を選択し、その票を（１５）式のエルガマル対として暗号化する。
【０１０６】
【数２３】
2005526307.tif 000025
【０１０７】
Ｖ−２．  次いで、ｖｉは、ランダムな
【０１０８】
【数２４】
2005526307.tif 000026
【０１０９】
を選択し、ｓｉ  ＝  ｒｉ／γ（ｉ）を計算し、それを（１６）式として暗号化する。
【０１１０】
【数２５】
2005526307.tif 000027
【０１１１】
Ｖ−３．  次いで、ｖｉは、（Ａｉ，Ｂｉ）対と（Ｃｉ，Ｄｉ）対の各々に対して非対話型の知識証明
【０１１２】
【数２６】
2005526307.tif 000028
【０１１３】
を構成する。これらの証明は、これらの組（ｐａｉｒｓ）が必要とされる形式からなり、ｖｉがｓｉおよびγ（ｉ）の値を知っているということを示す。
【０１１４】
Ｖ−４．  ｖｉは、暗号化され投票された票
【０１１５】
【数２７】
2005526307.tif 000029
【０１１６】
を投稿する。
【０１１７】
Ｖ−５．  「付加するだけの（ａｐｐｅｎｄ  ｏｎｌｙ）」掲示板モデルでは必要ないが、実際には、ｖｉは、Ｅｉに対する受領書を発行されるであろう。
【０１１８】
２．４  集計
このセクションでは、ｔ個のオーソリティの部分集合が固定されていると仮定する。一般性を失うことなしに、Ａ１，…，Ａｔが存在すると仮定することができる。
【０１１９】
Ｔ−１．  各１≦μ≦ｌに対し、（１８）式の量
【０１２０】
【数２８】
2005526307.tif 000030
【０１２１】
は、公的に計算される。
【０１２２】
Ｔ−２．  オーソリティは、エルガマル対の組
【０１２３】
【数２９】
2005526307.tif 000031
【０１２４】
のシーケンスの検証可能なシャッフルを実行する。その結果、（１９）式のエルガマル対の組の出力集合となる。
【０１２５】
【数３０】
2005526307.tif 000032
【０１２６】
ここで、
【０１２７】
【数３１】
2005526307.tif 000033
【０１２８】
である。この混合の特性は、復号化された値の対の集合、出力シーケンスの（ａｉ，ｂｉ）が、順序がランダムに変更されている点を除いて、入力シーケンスの復号化された値の対の集合と厳密に同じである。このような検証可能なシャッフルを実行することは、「ＶＥＲＩＦＩＡＢＬＥ，  ＳＥＣＲＥＴ  ＳＨＨＵＦＦＬＥＳ  ＯＦ  ＥＮＣＲＹＰＴＥＤ  ＤＡＴＡ，  ＳＵＣＨ  ＡＳ  ＥＬＧＡＭＡＬ  ＥＮＣＲＹＰＴＥＤ  ＤＡＴＡ  ＦＯＲ  ＳＥＣＵＲＥ  ＭＵＬＴＩ−ＡＵＴＨＯＲＩＴＹ  ＥＬＥＣＴＩＯＮＳ」という名称の、２００１年３月２４日出願の米国特許出願第０９／８１６，８６９号および「ＶＥＲＩＦＩＡＢＬＥ  ＳＥＣＲＥＴ  ＳＨＵＦＦＬＥＳ  ＡＮＤ  ＴＨＥＩＲ  ＡＰＰＬＩＣＡＴＩＯＮ  ＴＯ  ＥＬＥＣＴＯＲＯＮＩＣ  ＶＯＴＩＮＧ」という名称の、２００２年３月２５日出願のＰＣＴ出願第ＷＯ０２／７７９２９においてより詳細に説明されている。これらの出願を、引用することによりそれらの開示内容全体が本明細書に組み込まれる。
【０１２９】
Ｔ−３．
【０１３０】
【数３２】
2005526307.tif 000034
【０１３１】
を検証された有効な証明を伴うすべての投票された票による集合とする。オーソリティは、これらＭ個のエルガマル対の組のシーケンスについて、結果の出力集合が（２０）式となる他の検証可能なシャッフルを実行する。
【０１３２】
【数３３】
2005526307.tif 000035
【０１３３】
Ｔ−４．  各１≦ｍ≦Ｍに対して、ｌ個のエルガマル対
【０１３４】
【数３４】
2005526307.tif 000036
【０１３５】
１≦ｉ≦ｌ、が公的に計算される。
【０１３６】
Ｔ−５．  オーソリティは、
【０１３７】
【数３５】
2005526307.tif 000037
【０１３８】
の組のすべてを一緒に復号化する。これらを各々ａｍおよびｘｍｉとする。
【０１３９】
Ｔ−６．  各１≦ｍ≦Ｍに対して、
Ｔ−６．１．  ａｍ∈｛μ１，…，μｋ｝
Ｔ−６．２．  ある１≦ｉ≦ｌに対して、ｘｍｉ＝１
である場合に限り、投票集計にａｍを加える。
【０１４０】
２．５  集計（代替の実施形態）
このセクションでは、ｔ個のオーソリティの部分集合が固定されていると仮定する。一般性を失うことなく、Ａ１，…，Ａｔが存在すると仮定することができる。
【０１４１】
Ｔ２−１．  各１≦ｉ≦ｌに対して、（２２）式の量
【０１４２】
【数３６】
2005526307.tif 000038
【０１４３】
は、公的に計算される。
【０１４４】
Ｔ２−２．  オーソリティは、エルガマル対
【０１４５】
【数３７】
2005526307.tif 000039
【０１４６】
のシーケンスについて検証可能なシャッフルを実行する。結果、エルガマル対の出力集合は、
【０１４７】
【数３８】
2005526307.tif 000040
【０１４８】
となる。ただし、Φｉ，Ψｉ∈＜ｇ＞である。この混合の特性は、順序がランダムに変更されている点を除いて、出力シーケンスの復号化された値の集合が、入力シーケンスの復号化された値の集合と厳密に同一であるというものである。
【０１４９】
Ｔ２−３．  検証された有効な証明を伴う、各投票された票Ｅｍ、１≦ｍ≦Ｍに対して、エルガマル対
【０１５０】
【数３９】
2005526307.tif 000041
【０１５１】
は、公的に計算される。
【０１５２】
Ｔ２−４．  オーソリティは、Ｍ×１個のエルガマル対の組、（（Ａｍ，Ｂｍ），（Θｍｉ，Ωｍｉ））、のシーケンスについて検証可能なシャッフルを実行する。その結果、出力集合
【０１５３】
【数４０】
2005526307.tif 000042
【０１５４】
となる。
【０１５５】
Ｔ２−５．  オーソリティは、
【０１５６】
【数４１】
2005526307.tif 000043
【０１５７】
の対のすべてを一緒に復号化する。これらを各々φｉ、ａｍおよびｘｍｉとする。
【０１５８】
Ｔ２−６．  各１≦ｍ≦Ｍに対して、
Ｔ２−７．  ａｍ∈｛μ１，…，μｋ｝
Ｔ２−８．  ある１≦ｉ≦ｌおよび１≦ｊ≦ｌに対して、ｘｍｉ＝φｊ
である場合に限り、投票集計にａｍを加える。
【０１５９】
２．６  プロトコルを強制に対し安全にする
プロトコルは、説明したように、明らかに強制に対して安全でない。もし、ｔまたはそれ以上のオーソリティが共謀する場合、彼らは、オリジナルの投票者の秘密ｒｉを復号化することができる。そしてこれにより、かれらはすべての投票者のふりをすることができる。問題は、匿名の署名要求を投票操作に加えることによって解決することができる。（「オーソリティ無し（ａｕｔｈｏｒｉｔｙ  ｆｒｅｅ）」である匿名の署名プロトコルの詳細な説明について前述の特許出願を参照されたい。）この場合、悪意のあるエージェントが秘密ｒｉにアクセスした場合でさえ、これは、対応するプライベートサインキー（ｐｒｉｖａｔｅ  ｓｉｇｎｉｎｇ  ｋｅｙ）がなければ投票集計に影響を与えることはできないし、プライベートサインキーは強制なしに得ることはできない。これについての理由は、明白であるべきである。投票された票に関するオーソリティ無し、匿名の署名は、オーソリティが（共謀していても）オリジナルの暗号化された票（検証可能なシャッフルへの入力またはミックス）を、標準のデジタル署名を使ってできる方法で個人にリンクすることを妨げる。標準のデジタル署名は、署名されたデータを登録された個人に明白にリンクする。匿名の署名は、署名されたデータを、個人からなる集合またはグループの１メンバーにリンクするのみである。
【図面の簡単な説明】
【０１６０】
【図１】本スキームを実施するための適切な環境を示すブロック図である。
【図２】本スキームにより典型的に実行されるステップを示すフロー図である。
【図１】
2005526307.tif 000044
【図２】
2005526307.tif 000045
【国際調査報告】
2005526307.tif 000046
2005526307.tif 000047