(57)【要約】投票者によって選択された（３０１）投票選択を伝送するためのメカニズムを説明する。本メカニズムは、投票選択を、クライアントだけに知られている第１の秘密で暗号化して（３０２）、第１の暗号化された投票構成要素を生成する。また、本メカニズムは、第１の秘密とは独立に選択されたクライアントだけに知られている第２の秘密で投票選択を暗号化して（３０３）、第２の暗号化された投票構成要素を生成することも行う。次に、本メカニズムは、第１の暗号化された投票構成要素と第２の暗号化された投票構成要素が同一の投票選択から暗号化されたことを示す証明を生成する（３０４）。本メカニズムは、第１の暗号化された投票構成要素および第２の暗号化された投票構成要素、ならびに証明を投票収集コンピュータシステムに送信する（３１１）。
2004524759.tif 000002
【特許請求の範囲】
【請求項１】
投票者によって選択された投票選択の受領を確認するためのコンピューティングシステムにおける方法であって、
投票収集機関によって前記投票者に関して受領された投票選択の識別を確認する内容の第１の確認メッセージを第１のパーティから受信するステップと、
前記投票収集機関によって前記投票者に関して受領された前記投票選択の識別を独立に確認する内容の第２の確認メッセージを前記第１のパーティとは独立の第２のパーティから受信するステップと
を含むことを特徴とする方法。
【請求項２】
前記第１の確認メッセージの内容および前記第２の確認メッセージの内容を表示して、当該表示された第１の確認メッセージと前記表示された第２の確認メッセージとともに、前記投票者によって、前記投票者が選択した前記投票選択に対して予期される投票確認メッセージとを比較し、前記投票者が選択した前記投票選択以外の投票選択が、前記投票者に関して前記投票収集機関によって受領されたかどうかを判定可能なステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記第１の確認メッセージの内容と前記第２の確認メッセージの内容を結合して結合された確認メッセージを得るステップと、
前記結合された確認メッセージを表示し、前記表示された結合された確認メッセージを、前記投票者によって、前記投票者が選択した前記投票選択に対して予期される結合された投票確認メッセージと比較して、前記投票者が選択した前記投票選択以外の投票選択が、前記投票者に関して前記投票収集機関によって受領されたかどうかを判定可能なステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記結合された確認メッセージが、前記第１の確認メッセージおよび前記第２の確認メッセージのそれぞれからの連結内容を使用して得られることを特徴とする請求項３に記載の方法。
【請求項５】
前記結合された確認メッセージが、しきい値秘密再構成技術を使用して得られることを特徴とする請求項３に記載の方法。
【請求項６】
前記第１の確認メッセージおよび前記第２の確認メッセージのそれぞれは、値を含み、前記結合された確認メッセージが、前記第１の確認値に含まれる前記値と前記第２の確認値に含まれる前記値の積を決定することによって得られることを特徴とする請求項１に記載の方法。
【請求項７】
前記第１の確認メッセージおよび前記第２の確認メッセージのそれぞれは、第１の値および第２の値を含み、前記結合された確認メッセージが、
前記第１の確認メッセージに含まれる前記第１の値と前記第２の確認メッセージに含まれる前記第１の値の積を特定するステップ、および
前記第１の確認メッセージに含まれる前記第２の値と前記第２の確認メッセージに含まれる前記第２の値の積を特定するステップ
によって得られることを特徴とする請求項１に記載の方法。
【請求項８】
前記投票収集機関によって前記投票者に関して受領された前記投票選択の識別を独立に確認する内容の第３の確認メッセージを前記第１のパーティおよび前記第２のパーティとは独立の第３のパーティから受信するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項９】
コンピューティングシステムが、
投票収集機関によって投票者に関して受領された投票選択の識別を確認する内容の第１の確認メッセージを第１のパーティから受信するステップ、および
前記投票収集機関によって前記投票者に関して受領された前記投票選択の識別を独立に確認する内容の第２の確認メッセージを前記第１のパーティとは独立の第２のパーティから受信するステップによって前記投票者が選択した前記投票選択の受領を確認するようにさせる内容を有することを特徴とするコンピュータ可読媒体。
【請求項１０】
投票者が選択した投票選択の受領を確認するためのコンピューティングシステムであって、
投票収集機関によって前記投票者に関して受領された投票選択の識別を内容がそれぞれ独立に確認する第１のパーティからの第１の確認メッセージと、前記第１のパーティとは別個の第２のパーティからの第２の確認メッセージをともに受信する確認受信サブシステムを含むことを特徴とするコンピューティングシステム。
【請求項１１】
投票者が選択した投票選択の受領を確認するためのデータ構造を含む投票者の制御下にあるコンピュータメモリデバイスであって、
投票収集機関によって前記投票者に関して受領された投票選択の識別を確認する内容の第１のパーティから受信された第１の確認メッセージと、
前記投票収集機関によって前記投票者に関して受領された前記投票選択の識別を独立に確認する内容の前記第１のパーティとは独立の第２のパーティから受信された第２の確認メッセージとを含むことを特徴とするデバイス。
【請求項１２】
投票者が選択した投票選択の受領を確認するためのコンピューティングシステムにおける方法であって、
第１の順序に配列された投票選択確認メッセージのリストを含む第１の投票者向けの確認辞書を第１の通信チャネルを介して第１の受け手に送信するステップと、
複数の有効な投票選択のそれぞれに関して、前記有効な投票選択に対応する投票選択確認メッセージを含む前記第１の順序における位置を示す前記第１の投票者向けの確認辞書ガイドを前記第１の通信チャネルとは別個の第２の通信チャネルを介して前記第１の受け手に送信し、前記第１の受け手が、前記第１の投票者が選択した前記投票選択の識別を前記確認辞書ガイドとともに使用して、前記投票者が選択した前記投票選択に対応する前記投票選択確認メッセージを前記確認辞書の中で特定することができるようにするステップとを含むことを特徴とする方法。
【請求項１３】
前記第１の受け手は、前記第１の投票者であることを特徴とする請求項１２に記載の方法。
【請求項１４】
前記第１の順序をランダムに選択するステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１５】
第２の順序に配列された投票選択確認メッセージのリストを含む第２の投票者向けの第２の確認辞書を前記第１の通信チャネルを介して第２の受け手に送信するステップであって、
前記第２の投票者は、前記第１の投票者とは別個であり、前記第２の受け手は、前記第１の受け手とは別個であり、前記第２の順序は、前記第１の順序とは別個であるステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１６】
前記第２の受け手は、前記第２の投票者であることを特徴とする請求項１５に記載の方法。
【請求項１７】
前記確認辞書に含まれる投票選択確認メッセージの前記リストは、いずれの有効な投票選択にも対応しない投票選択確認メッセージを含むことを特徴とする請求項１２に記載の方法。
【請求項１８】
前記確認辞書に含まれる投票選択確認メッセージの前記リストは、区別された複数の投票選択確認メッセージを含み、前記区別された複数の投票選択確認メッセージのいずれも、有効な投票選択に全く対応しないことを特徴とする請求項１２に記載の方法。
【請求項１９】
投票収集エンティティにおいて前記投票者に関して受領された投票選択に対応する投票選択確認メッセージを受信するステップと、
前記受信された投票選択確認メッセージを表示して、前記受け手が、前記表示された投票選択確認メッセージを、前記投票者が選択した前記投票選択に対応する物として前記確認辞書の中で特定された投票選択確認メッセージと比較可能なステップとをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項２０】
コンピューティングシステムが、
第１の順序で配列された投票選択確認メッセージのリストを含む確認辞書を第１の通信チャネルを介して受け手に送信するステップ、および
複数の有効な投票選択のそれぞれに関して、前記有効な投票選択に対応する投票選択確認メッセージを含む前記第１の順序における位置を示す確認辞書ガイドを前記第１の通信チャネルとは別個の第２の通信チャネルを介して前記受け手に送信し、前記受け手が、投票者が選択した前記投票選択の識別を前記確認辞書ガイドとともに使用して、前記投票者が選択した前記投票選択に対応する前記投票選択確認メッセージを前記確認辞書の中で特定することができるようにするステップによって前記投票者が選択した前記投票選択の受領を確認するようにさせる内容を有することを特徴とするコンピュータ可読媒体。
【請求項２１】
コンピュータシステムが、
投票収集エンティティにおいて前記投票者に関して受領された投票選択に対応する投票選択確認メッセージを受信し、
前記受信された投票選択確認メッセージを表示して、前記受け手が、前記表示された投票選択確認メッセージを、前記投票者が選択した前記投票選択に対応する物として前記確認辞書の中で特定された投票選択確認メッセージと比較可能にすることをさらに行うようにさせる内容を有することを特徴とする請求項１８に記載のコンピュータ可読媒体。
【請求項２２】
投票者が選択した投票選択の受領を確認するためのコンピューティングシステムであって、
第１の順序に配列された投票選択確認メッセージのリストを含む確認辞書を第１の通信チャネルを介して受け手に送信するように結合された第１の伝送システムと、
複数の有効な投票選択のそれぞれに関して、前記有効な投票選択に対応する投票選択確認メッセージを含む前記第１の順序における位置を示す確認辞書ガイドを前記受け手に送信する前記第１の通信チャネルとは別個の第２の通信チャネルに結合され、前記第受け手が、前記投票者が選択した前記投票選択の識別を前記確認辞書ガイドとともに使用して、前記投票者が選択した前記投票選択に対応する前記投票選択確認メッセージを前記確認辞書の中で特定することができるようにする第２の伝送システムとを含むことを特徴とするコンピューティングシステム。
【請求項２３】
前記第２の伝送システムは、音声メッセージを介して前記確認辞書ガイドを送信することを特徴とする請求項２２に記載のコンピューティングシステム。
【請求項２４】
前記第２の伝送システムは、郵便メールメッセージを介して前記確認辞書ガイドを送信することを特徴とする請求項２２に記載のコンピューティングシステム。
【請求項２５】
異なる有効な投票選択にそれぞれが対応する投票確認ストリングのサブセットである前記投票確認ストリングのシーケンスを含むランダム化された確認辞書データ構造を集合として伝える１つまたは複数の生成されたデータ信号であって、
前記投票ストリングが前記シーケンスの中で出現する順序が、前記シーケンスの中の前記投票確認ストリングのどれがどの有効な投票選択に対応するかの別個の確認辞書ガイドなしには、特定することができないように、ランダムに選択されることを特徴とするデータ信号。
【請求項２６】
有効な投票選択に対応する前記投票確認ストリングは、前記シーケンスの中の前記投票確認ストリングの適切なサブセットであることを特徴とする請求項２５に記載の生成されたデータ信号。
【請求項２７】
投票者が選択した投票選択を送付するためのコンピューティングシステムにおける方法であって、
クライアントコンピュータシステムにおいて、
クライアントだけに知られている第１の秘密で前記投票選択を暗号化して第１の暗号化された投票構成要素を生成するステップと、
前記第１の秘密とは独立に選択されたクライアントだけに知られている第２の秘密で前記投票選択を暗号化して第２の暗号化された投票構成要素を生成するステップと、
前記第１の暗号化された投票構成要素と前記第２の暗号化された投票構成要素が同一の投票選択から暗号化されたことを示す証明を生成するステップと、
前記第１の投票構成要素および前記第２の投票構成要素、ならびに前記証明を投票収集コンピュータシステムに送信するステップと、
前記投票収集コンピュータシステムにおいて、
前記第１の暗号化された投票構成要素と前記第２の暗号化された投票構成要素が同一の投票選択から暗号化されたことを前記証明が示すかどうかを判定するステップと、
前記第１の暗号化された投票構成要素と前記第２の暗号化された投票構成要素が同一の投票選択から暗号化されたことを前記証明が示す場合にだけ、前記投票選択を受け入れるステップとを含むことを特徴とする方法。
【請求項２８】
前記第１の暗号化された投票構成要素が、ｇαおよびｈαｍを評価することによって生成され、ただし、ｐは素数であり、ｑがｐ−１の重複度１の除数であるという特性を有する素数乗法オーダ（ｐｒｉｍｅ  ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｏｒｄｅｒ）ｑを有するｇ∈Ｚｐであり、ｈ∈＜ｇ＞であり、α∈Ｚｐが投票ノードにおいてランダムに選択され、ｍは、前記投票選択であり、また前記第２の暗号化された投票構成要素が、数式
【数１】
2004524759.tif 000072
および数式
【数２】
2004524759.tif 000073
を評価することによって生成され、ただし、
【数３】
2004524759.tif 000074
であり、
【数４】
2004524759.tif 000075
が、投票ノードにおいてランダムに独立に選択され、ｍは、前記投票選択であることを特徴とする請求項２７に記載の方法。
【請求項２９】
前記投票収集コンピュータシステムにおいて、前記第１の暗号化された投票構成要素および前記第２の暗号化された投票構成要素に基づいて投票確認を前記クライアントコンピュータシステムに送信するステップと、
前記クライアントコンピュータシステムにおいて、前記第１の秘密および前記第２の秘密を使用して前記投票確認を解読するステップとをさらに含むことを特徴とする請求項２７に記載の方法。
【請求項３０】
ｐは素数であり、ｑがｐ−１の重複度１の除数であるという特性を有する素数乗法オーダｑを有するｇ∈Ｚｐであり、ｈ∈＜ｇ＞であり、
【数５】
2004524759.tif 000076
は、秘密として保持されるｄ乗にされたｈであり、α∈Ｚｑおよび
【数６】
2004524759.tif 000077
が、投票ノードにおいてランダムに、独立に選択され、Ｋｉ∈＜ｇ＞であり、βｉ∈Ｚｑであり、ｍは、前記投票選択である
数式
【数７】
2004524759.tif 000078
を評価すること、および
【数８】
2004524759.tif 000079
を評価することによって前記投票確認を生成するステップをさらに含み、以上２つの評価される数式が、前記投票確認として前記クライアントコンピュータシステムに送信されることを特徴とする請求項２９に記載の方法。
【請求項３１】
ｐは素数であり、ｑがｐ−１の重複度１の除数であるという特性を有する素数乗法オーダｑを有するｇ∈Ｚｐであり、ｈ∈＜ｇ＞であり、
【数９】
2004524759.tif 000080
は、秘密として保持されるｄ乗にされたｈであり、α∈Ｚｑおよび
【数１０】
2004524759.tif 000081
が、投票ノードにおいてランダムに、独立に選択され、Ｋｉ∈＜ｇ＞であり、
【数１１】
2004524759.tif 000082
であり、Ｖｉが前記投票確認の一部として受信される
【数１２】
2004524759.tif 000083
を評価することによって前記投票確認が解読されることを特徴とする請求項２９に記載の方法。
【請求項３２】
投票者が選択した投票選択を伝送するためのコンピューティングシステムにおける方法であって、
クライアントだけに知られている第１の秘密で前記投票選択を暗号化して第１の暗号化された投票構成要素を生成するステップと、
前記第１の秘密とは独立に選択された前記クライアントだけに知られている第２の秘密で前記投票選択を暗号化して第２の暗号化された投票構成要素を生成するステップと、
前記第１の暗号化された投票構成要素と前記第２の暗号化された投票構成要素が同一の投票選択から暗号化されたことを示す証明を生成するステップと、
前記第１の暗号化された投票構成要素および前記第２の暗号化された投票構成要素、ならびに前記証明を投票収集コンピュータシステムに送信するステップと
を含むことを特徴とする方法。
【請求項３３】
コンピューティングシステムが、
クライアントだけに知られている第１の秘密で投票選択を暗号化して第１の暗号化された投票構成要素を生成するステップ、
前記第１の秘密とは独立に選択されたクライアントだけに知られている第２の秘密で前記投票選択を暗号化して第２の暗号化された投票構成要素を生成するステップ、
前記第１の暗号化された投票構成要素と前記第２の暗号化された投票構成要素が同一の投票選択から暗号化されたことを示す証明を生成するステップ、および
前記第１の投票構成要素および前記第２の投票構成要素、ならびに前記証明を投票収集コンピュータシステムに送信するステップ
によって投票者が選択した前記投票選択を提出するようにさせる内容を有することを特徴とするコンピュータ可読媒体。
【請求項３４】
暗号化された投票データ構造を共同で伝送する１つまたは複数の生成されたデータ信号であって、
第１の暗号化された投票構成要素を生成するようにクライアントコンピュータシステムだけに知られている第１の秘密で暗号化された第１の暗号化された投票選択と、
前記第１の秘密とは独立に選択された前記クライアントコンピュータシステムだけに知られている第２の秘密で暗号化された第２の暗号化された投票選択と、
証明と
を含み、前記暗号化された投票データ構造によって表される投票が、前記第１の暗号化された投票選択と前記第２の暗号化された投票選択が同一の投票選択の暗号化であることを前記証明が示す場合にだけカウントされることが可能であるようにすることを特徴とするデータ信号。
【請求項３５】
投票者が選択した投票選択を受領するためのコンピューティングシステムにおける方法であって、
第１の暗号化された投票構成要素を生成するようにクライアントだけに知られている第１の秘密で暗号化された第１の暗号化された投票選択、
前記第１の秘密とは独立に選択されたクライアントだけに知られている第２の秘密で暗号化された第２の暗号化された投票選択、および
証明をクライアントコンピュータシステムから受領するステップと、前記第１の暗号化された投票選択および前記第２の暗号化された投票選択が同一の投票選択の暗号化であることを前記証明が示す場合にだけ、前記投票選択を受理するステップとを含むことを特徴とする方法。
【請求項３６】
コンピューティングシステムが、
第１の暗号化された投票構成要素を生成するようにクライアントだけに知られている第１の秘密で暗号化された第１の暗号化された投票選択、
前記第１の秘密とは独立に選択された前記クライアントだけに知られている第２の秘密で暗号化された第２の暗号化された投票選択、および
証明をクライアントコンピュータシステムから受領するステップと、前記第１の暗号化された投票選択と前記第２の暗号化された投票選択が同一の投票選択の暗号化であることを前記証明が示す場合にだけ、投票選択を受理するステップと
によって投票者が選択した前記投票選択を受領するようにさせる内容を有することを特徴とするコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、票決自動化、および票決自動化のための暗号技術の分野を対象とする。
【背景技術】
【０００２】
本出願は、２００１年２月２０日に出願した米国仮出願番号６０／２７０，１８２の恩典を主張し、２００２年２月１１日に出願した米国仮出願番号          （弁理士整理番号３２４６２−８００６ＵＳ０２）の恩典を主張し、２０００年３月２４日に出願した米国特許出願番号０９／５３４，８３６、２０００年３月２４日に出願した米国特許出願番号０９／５３５，９２７、および２００１年３月２４日に出願した米国特許出願番号０９／８１６，８６９それぞれの一部継続出願である。以上５つの出願のそれぞれは、参照により全体が組み込まれている。
【０００３】
従来の手作業で行われる票決には、長年、不正確、非効率という問題が付きまとってきた。コンピュータを使用して票決をより正確に、より効率的にすることが可能であると広く提案されてきたが、コンピュータには、コンピュータ独自の落とし穴が伴う。電子データを改変するのはとても容易なので、多くの電子投票システムは、従来の投票システムでは発生する可能性がはるかに低いいくつかのタイプの障害を生じやすい。
【０００４】
１つの部類のそのような障害は、投票者のコンピュータ、またはその他のコンピューティングデバイスの保全性が不明であることに関する。今日のネットワーク化されたコンピューティング環境では、どのマシンも悪意のあるソフトウェアから安全に保つことは極めて困難である。そのようなソフトウェアは、しばしば、悪意のある行為を実際に開始するまで、長期間にわたってコンピュータに隠れていることができる。その間、そのようなソフトウェアは、ネットワーク上の他のコンピュータに、またはそのネットワークと何らかの最小限のやり取りを行うコンピュータに自らを複製することができる。そのようなソフトウェアは、ユーザによって運ばれる永久媒体を介してネットワーク化されていないコンピュータに転送される可能性もある。
【０００５】
電子秘密投票票決の状況では、この種の悪意のあるソフトウェアは、特に危険である。というのは、ソフトウェアの悪意のある行為が起動された際にも、その行為が依然として検知されず、したがって、放置されて、将来のさらなる票決を混乱させる可能性があるからである。制御の論理および精度試験（「Ｌ＆Ａ試験」）は、試験投票の処理を監視して、投票システムが適切に動作しているかどうかを判定し、これを使用して、投票者のコンピュータ内部に存在する悪意のあるソフトウェアの検出を試みることができる。しかし、Ｌ＆Ａ試験は、効果的に行うのが極めて困難である。というのは、悪意のあるソフトウェアは、「現実の」票と「試験」票を区別し、すべての「試験」票に影響を与えないままにすることができる可能性があるからである。投票の秘匿性の要件が、「現実の」票をセキュリティの欠損（ｃｏｍｐｒｏｍｉｓｅ）に関して検査することを不可能にしているため、徹底的なＬ＆Ａ試験さえ、無駄に終わる可能性がある。この脅威と闘うという問題は、「クライアント信頼問題」として知られている。
【０００６】
【特許文献１】
米国特許出願番号０９／５３５，９２７
【非特許文献１】
ＣＤＳ９４
【非特許文献２】
ＣＧＳ９７
【非特許文献３】
R. Cramer, I. Damgard, B. Schoenmakers, Proofs of partial knowledge and simplified design of witness hiding protocols, Advances in Cryptology - CRYPTO '94, Lecture Notes in Computer Science, pp. 174-187, Springer-Verlag, Berlin, 1994
【発明の開示】
【発明が解決しようとする課題】
【０００７】
クライアント信頼問題を解決するためのほとんどの既存の方法は、投票プラットフォームのセキュリティを確保する方法に重点を置いており、これにより、投票者のコンピュータが「クリーン」である、または「感染していない」という確実性をもたらす。残念ながら、許容可能なレベルのそのような確実性を実現するのに必要とされる専門知識と継続した念入りの作業のため、電子投票システムは、通常、コンピュータ専門家およびネットワーク専門家がクライアントコンピュータシステムを維持し、監視することが可能な投票サイトの管理された環境に押し込められている。これらの投票サイトシステムは、それでも、構成の容易さ、使用の容易さ、集計の効率、および費用の点でいくつかの利点を提供する。ただし、この手法は、電子商取引の世界で活用されている分散通信の多大な可能性を世に出すことができない。
【０００８】
したがって、実質的にあらゆるコンピュータシステムをあらゆる場所で投票プラットフォームとして使用することを可能にする、投票プラットフォームを悪意のあるソフトウェアからセキュリティ保護することを必要としないクライアント信頼問題に対する解決策が、著しい有用性を有する。
【課題を解決するための手段】
【０００９】
悪意のあるプログラムによってセキュリティの損なわれた投票を検知するためのソフトウェアメカニズム（「本メカニズム」）を提供する。本メカニズムによって使用される手法は、通常、投票コンピュータ上の悪意のあるソフトウェアの存在を除去しようとする試み、または防止しようとする試みを全く行わない。代わりに、この手法は、投票者が、投票者の投票の内容を、投票収集センタ自体に内容（投票選択）を明かすことなく、収集センタにおいて受け取られた際に検証する暗号法上、セキュアな方法を提供する。つまり、投票収集センタは、明確にどのような選択が受け取られたかを、その選択がどのようなものであるかを知ることなく、投票者に確証することができる。したがって、投票者は、投票者の意図する選択と、投票収集センタにおいて受け取られた実際の選択（伝送された投票済みの票のデジタルデータによって表される）の間に違いが存在すれば、それを検知することができる。さらに、各票決が、柔軟な１組のポリシー決定から選択を行い、受け取られた選択が意図する選択と異なる場合、投票者が、投票者の票を投票しなおすことが可能になる。
【００１０】
本メカニズムをほぼ標準の票決設定の文脈で説明する。説明を容易にするため、本メカニズムの最初の説明は、票の上に１つの質問だけが存在し、また１組のＫ個の許容可能な回答α１，．．．，αＫ（そのうち１つは、「棄権」とすることが可能である）が存在するものと想定する。この状況において与えられている解決策を一般化して現実世界の票構成の大多数を扱うことは、単純明快な事柄であることが当分野の技術者には理解されよう。
【００１１】
票決設定のいくつかの通常の暗号上の特徴は、以下のとおりである。
【００１２】
１．票構成：１組の暗号法上の票決パラメータが前もって票決役員によって合意され、一般への公布またはその他のそのような手段によって公表される。重要なパラメータは、暗号群、ジェネレータ、票決公開鍵（ｅｌｅｃｔｉｏｎ  ｐｕｂｌｉｃ  ｋｅｙ）、および決定符号化スキームである。より具体的には、これらは、以下のとおりである。
【００１３】
（ａ）暗号群、Ｇは、ｐが大きい素数、または楕円曲線群であるＺｐであることが可能である。
【００１４】
（ｂ）ジェネレータ、ｇ∈Ｇ。Ｇ＝Ｚｐである場合、ｇは、大きい素数オーダ（ｐｒｉｍｅ  ｏｒｄｅｒ）ｑを有するＧ＊の（乗法）部分群＜ｇ＞を生成しなければならない。楕円曲線の場合、＜ｇ＞＝Ｇであり、かつｑ＝ｐであるものと想定する。
【００１５】
（ｃ）票決公開鍵、ｈ∈＜ｇ＞。
【００１６】
（ｄ）決定符号化スキーム：＜ｇ＞の「回答代表（ａｎｓｗｅｒ  ｒｅｐｒｅｓｅｎｔａｔｉｖｅｓ）」への分割。つまり、＜ｇ＞＝Ｓ０∪Ｓ１∪．．．ＳＫであり、ただし、Ｓｋは、＜ｇ＞の２つ１組の互いに素な部分集合である。各１≦ｋ≦Ｋに関して、任意のメッセージｍ∈Ｓｋは、αｋに対する投票を表す。残りのメッセージｍ∈Ｓ０は、無効であると見なされる。通常、１≦ｋ≦Ｋである各Ｓｋは、単一の要素μｋから成る。ただし、これは、本質的には、要件ではない。ただし、スキームのセキュリティのため、μｋは、何らかの公開のランダムソースを使用して、または許容可能な共有スキームによって独立にランダムに生成されることが一般に必要とされる。
【００１７】
以下の説明は、統一性のために乗法群表記を使用するが、すべての構成は、楕円曲線を使用しても同等に良好に実施できることが明確であろう。
【００１８】
２．投票提出：各投票者ｖｉは、自らの投票、つまり決定を、ＥｌＧａｍａｌペア
【００１９】
【数１】
2004524759.tif 000003
【００２０】
として暗号化し、ただし、αｉ∈Ｚｑが、投票者によってランダムに選択され、ｖｉが回答αｋを選択することを所望する場合、ｍｉ∈Ｓｋである。この暗号化された値が、投票収集センタに伝送される（投票される）物であり、通常、ｖｉによって生成された付加されたデジタル署名を伴う。
【００２１】
投票者ｖｉが、例えば、紙と鉛筆を使用して、以上の値を自身で計算したとすれば、秘密投票の普遍的に検証可能な票決システムを実施するのに以上のプロトコルで、基本的に十分である。（使用される集計方法に応じて、投票者の有効性の証明などのいくらかの追加の情報が必要とされる。）しかし、実際には、ｖｉは、何らかのユーザインターフェースを介して選択を行うだけであるので、投票者ｖｉが、送信されたビットの実際の値を観察し、そのビットが自身の意図する選択と矛盾していないかを調べることを当てにするのは現実的ではない。要するに、投票クライアントは、投票者が実際には「μｋ票」を提出することを所望したにもかかわらず、投票者の意図を無視して「μｊ票」を提出する可能性がある。
【００２２】
投票者は、通常、投票収集センタにおいて受け取られた暗号化された投票が自身の選択と矛盾していないことを検証する何らかの手立てを必要とする。単に投票箱データを公開することは、妥当な解決策ではない。というのは、投票者ではなく、投票クライアントがαｉを選択するからである。投票の秘匿性、および強制の理由から、この値は、「喪失」されなければならない。したがって、ｖｉの暗号化された票は、ｖｉ自身にも、他の人にとってと同様に不分明である。投票収集センタからの一般的な確認も、明らかに十分ではない。必要とされていることの一般的な特性は、以下の特性である。
【００２３】
１．投票収集センタによって戻される確認ストリングは、受け取られたデータ（暗号化された票）に相関している必要がある。
【００２４】
２．投票者および投票クライアントは、投票者が、受け取られた選択（つまり票）μｋにＣを排他的に結び付けることを可能にする特定の１組のステップを実行することができなければならない。
【００２５】
３．投票者が「騙される」ような仕方で投票クライアントが振舞うことが不可能でなければならない。つまり、クライアントは、実際にはμ≠μｋであるにもかかわらず、μｋが受け取られたと投票者に思い込ませることができない。
【発明を実施するための最良の形態】
【００２６】
このセクションでは、ＳＶＣと呼ぶことにするそのようなスキームを基本的な形態で提示する。後続のセクションでは、いくつかの改良形態および拡張形態を提供する。
【００２７】
以下のステップが、通常、投票プロセスの一環として行われる。
【００２８】
ＣＣ−１．ｖｉ「によって操作される」投票クライアントＭｉが、以前と同様に、ｖｉに代わって暗号化された票を生成する。この暗号化された票を、何らかの値ｍｉ∈＜ｇ＞およびαｉ∈Ｚｑに関して、
【００２９】
【数２】
2004524759.tif 000004
【００３０】
で表す。
【００３１】
ＣＣ−２．Ｍｉも、ｍｉ∈｛μ１，．．．，μＫ｝であることのゼロ知識の証明（ｚｅｒｏｋｎｏｗｌｅｄｇｅ  ｐｒｏｏｆ）である有効性の証明Ｐｉを構成するのに必要とされる。（そのような証明は、（例えば、非特許文献１参照）の技術を使用する離散対数（ｄｉｓｃｒｅｔｅ  ｌｏｇａｒｉｔｈｍｓ）が等しいことの基本Ｃｈａｕｍ−Ｐｅｄｅｒｓｏｎ証明から容易に構成することができる。特定の例については、（例えば、非特許文献２参照）を参照。）
ＣＣ−３．次に、Ｍｉが、Ｐｉと（署名付きの）暗号化された票（Ｘｉ，Ｙｉ）をともに投票収集センタに提出する。
【００３２】
ＣＣ−４．暗号化された票を受け入れるのに先立って、投票収集センタは、まず、証明Ｐｉを検査する。Ｐｉの検証が失敗した場合、破損（ｃｏｒｒｕｐｔｉｏｎ）が既に検知され、投票収集センタは、確認のストリングを全く発行しないか、または何らかのデフォルトのランダムなストリングを発行することができる。
【００３３】
ＣＣ−５．Ｐｉの検証が成功したものと想定すると、投票収集センタは、値ＷｉおよびＵｉを以下のとおり計算する。
【００３４】
【数３】
2004524759.tif 000005
ただし、Ｋｉ∈Ｇおよびβｉ∈Ｚｑは、ランダムに独立に生成される（投票者ごとに）。
【００３５】
ＣＣ−６．投票収集センタは、次に、（Ｕｉ，Ｗｉ）をＭｉに戻す。
【００３６】
ＣＣ−７．クライアントＭｉが、
【００３７】
【数４】
2004524759.tif 000006
を計算し、このストリング（または、より高い可能性として、このストリングのハッシュＨ（Ｃｉ））を投票者ｖｉに表示する。
【００３８】
投票者は、どの確認ストリングを探すべきかを知っている必要がある。これは、２つの異なる仕方で達せられる。最も単純明快なのは、投票者ｖｉが、投票収集センタからＫｉおよびβｉを獲得するようにさせることである。これは、実行可能であり、ほとんどデータが転送されることを必要とせず、一部の実施形態によく適している可能性がある。しかし、他の状況では、Ｃｉ（またはＨ（Ｃｉ））を計算しなければならないため、魅力のない手法である可能性がある。この計算を行うようにＭｉに求めることは、本スキームのセキュリティを破壊するので、ｖｉは、さらなるコンピューティングデバイスにアクセスを有し、また独立の通信チャネルにもアクセスを有さなければならない。
【００３９】
別法は、投票収集センタが、ｖｉに関するすべての可能な確認ストリングを計算し、独立したチャネルを介して確認辞書に相当する物をｖｉに送信するようにさせることである。一般に、投票者ｖｉに関する確認辞書は、任意の妥当なフォーマットでレイアウトされた以下のテーブルから成る。
【００４０】
【表１】
2004524759.tif 000007
【００４１】
ただし、Ｈは、票決の公開（公表された）ハッシュ関数（場合により、恒等関数）であり、
【００４２】
【数５】
2004524759.tif 000008
【００４３】
である。
【００４４】
もちろん、独立したチャネルが本当に独立していることを確実にするように、独立のチャネルを設計する際に注意が払われなければならない。理想的には、独立したチャネルは、投票ネットワークに接続されたデバイスからはアクセス不可能でなければならない。ただし、解決策が用意されている。Ｋｉおよびβｉは、票決に先立って生成することができるので、陸上便（ｓｕｒｆａｃｅ  ｍａｉｌ）などの遅い配達方法さえ、辞書を伝送するのに使用することができる。
【００４５】
本メカニズムをより完全に説明するため、本メカニズムの実施形態の一部の動作を示す例を説明する。以下は、秘密値確認交換（Ｓｅｃｒｅｔ  Ｖａｌｕｅ  Ｃｏｎｆｉｒｍａｔｉｏｎ  ｅｘｃｈａｎｇｅ）の詳細な例である。
【００４６】
この例を最大限に明確にするため、使用するいくつかの基本的なパラメータ、例えば、票の上の質問の数や暗号パラメータのサイズは、実際に、通常、使用されるパラメータよりも相当に少ない。また、例示的な交換の態様を特定の順序で以下に説明するが、これらの態様は、様々な他の順序で行ってもよいことが、当分野の技術者には理解されよう。
【００４７】
一部の電子票決プロトコルは、以下のような追加の特徴を含む。すなわち、
認証および監査のための投票者と当局の証明書（公開鍵）情報、
票ページスタイルパラメータ、
データ符号化の標準、
集計プロトコルおよび集計パラメータである。
【００４８】
以上の特徴は、秘密値確認の実施とは独立なので、以上の特徴の詳細な説明は、この例には含めない。
【００４９】
この例は、投票者の応答（回答）を単一のＥｌＧａｍａｌペアとして符号化する票決プロトコルを想定する。ただし、本明細書で見られる説明から、投票された票に対してＥＬＧａｍａｌ暗号化を使用する他の票決プロトコルに合った秘密値確認交換を構成することも、自明な事柄である。例えば、本メカニズムの一部の実施形態は、（例えば、特許文献１参照）に説明される準同形の票決プロトコルを組み込んでいる。そのプロトコルでは、投票者の応答は、複数のＥｌＧａｍａｌペアによって表される。この例で使用される確認辞書は、それぞれの確認ストリングの連結を表示するように、または確認ストリングのシーケンスのハッシュを表示するように容易に変更される。
【００５０】
管轄機関（ｊｕｒｉｓｄｉｃｔｉｏｎ）はまず、票決初期設定データについて合意しなければならない。票決初期設定データは、少なくとも、基本暗号化数値パラメータ、票（すなわち、１組の質問と許容可能な回答等）、および決定符号化スキームを含む。（使用される特定の票決プロトコルに妥当な追加のデータも含まれることが可能である。）
暗号パラメータ
群の算法（Ｇｒｏｕｐ  Ａｒｉｔｈｍｅｔｉｃ）：整数乗算的なモジュラー算法（Ｉｎｔｅｇｅｒ  ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｍｏｄｕｌａｒ  ａｒｉｔｈｍｅｔｉｃ）
素数モジュラス：ｐ＝４７
部分群モジュラス：ｑ＝２３
ジェネレータ：ｇ＝２
公開鍵：ｈ＝ｇｓ、ただし、ｓは秘密である。当該の例では、ｈ＝ｇ１２＝７であるものとする。
【００５１】
票
１つの質問
質問１テキスト：我々の旗をどの色にするべきですか（１つだけ選択してください）
回答／選択の数：４
＊回答１テキスト：青
＊回答２テキスト：緑
＊回答３テキスト：赤
＊回答４テキスト：私は棄権します
決定符号化スキーム
【００５２】
【表２】
2004524759.tif 000009
【００５３】
確認を発行するのに先立ち、投票者に確認辞書を配布するのに先立つ何らかの時点で、投票収集センタ（または代理）が、各投票者Ｖｉに関してランダムで独立したβｉおよびＫｉを生成する。確認辞書が、票の受取りより後に送られる場合、以上のパラメータは、投票者ごとに、それぞれの投票された票が受理された直後に生成されることが可能である。代替として、以上のパラメータは、票決に先立って生成されることが可能である。この例では、票収集代理が、投票された票を受理した直後と、それぞれの投票者の確認辞書を送る直前の両方で、以上のパラメータにアクセスを有する。
【００５４】
公式の投票時間中の何らかの時点で、各投票者Ｖが、前述した票決初期設定データを獲得し、認証する。票決初期設定データは、何らかの票サーバに「票要求」を提出することによって獲得することができる。代替として、管轄機関は、票決初期設定データを「公表する」、つまり票決初期設定データがすべての投票者に都合よく利用可能であるようにする何らかの好都合な手段を有することが可能である。
【００５５】
票決初期設定データから、Ｖは、期待されている応答が、２つの別個のデータ要素の特定のシーケンスの標準の符号化であることを決定することができる。２つの別個のデータ要素は、以下のとおりである（厳密な順序で）。
【００５６】
選択暗号化
投票者の選択、つまり回答を示す（暗号化された形態で）０≦Ｘ、Ｙ＜４７である１対の整数（Ｘ，Ｙ）。回答は、妥当であるには、０≦α＜２３であり、かつμ∈｛９，２１，３６，１７｝である（Ｘ，Ｙ）＝（２α，７αμ）の形態になっていなければならない。
【００５７】
有効性の証明
（Ｘ，Ｙ）が、前述した選択暗号化ステップにおいて説明した形態になっていることを示す有効性の証明。（この例では、この証明は、特定のシーケンスに配列された１５個のモジュラー整数から成ることを以下に見る。）
この例では、Ｖは、「緑」に票を投じることを所望しているものと想定する。
【００５８】
１．Ｖは、α∈Ｚ２３をランダムに生成する。この例では、α＝５である。「緑」の符号化は２１であるので、Ｖの選択の暗号化は、以下のとおり計算される。
【００５９】
【数６】
2004524759.tif 000010
このペアが、投票収集センタに送られなければならない物である。潜在的な脅威は、Ｖのコンピュータが、これらの値を改変しようと試みる可能性があることである。
【００６０】
投票者Ｖ（または、より正確には、Ｖのコンピュータ）は、以下の条件のうちどれが実際に成立するかを明らかにすることなく、αの何らかの不特定の値に関して、以下の条件のうち１つが成立することを証明しなければならない。
【００６１】
１．（Ｘ，Ｙ）＝（２α，７α×９）、すなわち、選択（投じられた票）が「青」である
２．（Ｘ，Ｙ）＝（２α，７α×２１）、すなわち、選択（投じられた票）が「緑」である
３．（Ｘ，Ｙ）＝（２α，７α×３６）、すなわち、選択（投じられた票）が「赤」である
４．（Ｘ，Ｙ）＝（２α，７α×１７）、すなわち、選択（投じられた票）が「私は棄権します」である
これを達するのに使用することができる様々な標準の方法が存在する。例えば、（例えば、非特許文献３参照）を参照されたい。本メカニズムによって使用される秘密値確認技術は、前段落の抽象基準を満たすいずれの方法を使用しても同等に良好に機能する。そのような有効性証明方法の詳細を以下に提供しているが、本メカニズムの実施形態は、以下のタイプ以外のタイプの有効性証明を使用することも可能である。
【００６２】
有効性証明の構成
（以下で、Ｖが行う必要があるそれぞれの行為または計算が、実際には、Ｖのコンピュータによって行われる。）
１．Ｖが、α２＝α＝５に設定する。
【００６３】
２．Ｖが、ω２∈ＲＺ２３，ｒ１，ｒ３，ｒ４∈ＲＺ２３，ｓ１，ｓ３，ｓ４∈ＲＺ２３をすべてランダムに、独立に生成する。この例の場合、
【００６４】
【数７】
2004524759.tif 000011
であるものとする。
【００６５】
３．Ｖが、対応する値を計算する。
【００６６】
【数８】
2004524759.tif 000012
【００６７】
【数９】
2004524759.tif 000013
４．Ｖが、公に指定されたハッシュ関数Ｈを使用してｃ∈Ｚ２３を以下のとおり計算する。
【００６８】
【数１０】
2004524759.tif 000014
ハッシュ関数の多くの選択が可能であるため、この例では、単にランダムな値、例えば、
【００６９】
【数１１】
2004524759.tif 000015
を選択することができる。（実際には、ＳＨＡ１、またはＭＤ５、または他のそのような標準のセキュアなハッシュ関数を使用してＨを計算することができる。）
５．Ｖが、次数４−１＝３の補間の多項式Ｐ（ｘ）を計算する。Ｐを規定する特性は以下のとおりである。
【００７０】
【数１２】
2004524759.tif 000016
【００７１】
【数１３】
2004524759.tif 000017
【００７２】
は、標準の多項式補間理論を使用して計算され、以下がもたらされる。
【００７３】
【数１４】
2004524759.tif 000018
または
【００７４】
【数１５】
2004524759.tif 000019
６．Ｖが、以下の値を計算する。
【００７５】
【数１６】
2004524759.tif 000020
７．Ｖの有効性証明は、以下の１２個の数
【００７６】
【数１７】
2004524759.tif 000021
と以下の３つの数、
【００７７】
【数１８】
2004524759.tif 000022
の厳密なシーケンスから成る。（Ｚ０は、提出される必要がない。というのは、Ｚ０は、公開のハッシュ関数Ｈを使用して提出されたその他のデータ要素から計算可能なためである。）
必要とされる選択暗号化（Ｘ，Ｙ）、および対応する有効性の証明を計算した後、Ｖは、以上の要素を、標準の符号化フォーマットによって規定されるとおり、シーケンスで符号化する。結果のシーケンスが、Ｖの投票された票を形成する。（票を改変できないようにし、争う余地のないようにするため、Ｖは、自身の秘密署名鍵を使用してこの投票された票にデジタル署名を行うこともできる。Ｖの投票された票とＶのデジタル署名の結果の組合せ（より正確には、これら２つの要素の標準の符号化）が、Ｖの署名済みの投票された票を形成する。最後に、各投票者が、自身の（オプションとして署名付きの）投票された票を、票を収集するデータセンタに返送する。
【００７８】
前述したとおり、Ｖ（βおよびＫ）に関する投票者特有のランダムなパラメータが、投票収集センタにおいて用意されている。この例では、ランダムなパラメータは、以下のとおりである。
【００７９】
【数１９】
2004524759.tif 000023
投票者の（オプションとして署名付きの）投票された票が投票収集センタにおいて受け取られた際、以下のステップが実行される。
【００８０】
１．デジタル署名が検査されて、票の真正性、ならびに投票者の適格性が判定される。
【００８１】
２．ステップ１において署名が正しく検証された場合、投票収集センタは、有効性の証明を検証する。この例で使用することを選択した特定のタイプの有効性証明の場合、この検証は、以下により構成される。
【００８２】
（ａ）公開ハッシュ関数Ｈを使用してＰ（０）＝Ｚ０の値を計算する。
【００８３】
【数２０】
2004524759.tif 000024
（Ｐの残りの係数ｚ１，ｚ２，ｚ３は、Ｖの（オプションとして署名付きの）投票された票の提出の一部であることを思い起されたい。）
（ｂ）各１≦ｊ≦４に関して、以下の数式
【００８４】
【数２１】
2004524759.tif 000025
の両辺が評価される。（この場合、前述したとおり、μｊは、決定符号化スキームからとられる。）以上のいずれかが等しくないとき、検証は失敗である。その票は、受理されず、何らかの任意の拒否ストリング（指示）がＶに送り返される。
【００８５】
３．先行するステップが成功裡に行われたものと想定すると、返答ストリング（Ｗ，Ｕ）は、以下のとおり計算される。
【００８６】
【数２２】
2004524759.tif 000026
このシーケンスにされたペアは、公開符号化フォーマットによって規定されるとおりに符号化され、Ｖに戻される。
【００８７】
４．Ｖのコンピュータが、
【００８８】
【数２３】
2004524759.tif 000027
を計算し、そのストリングをＶに表示する。（代替として、プロトコルは、公開ハッシュ関数がＣに対して計算され、結果のハッシュ値が表示されることを指定することができる。この例では、Ｃ自体が表示される。）Ｖのコンピュータが、「緑」以外の選択を提出しようと試みた場合、以上で計算されたＣの値は、異なる物になる。さらに、Ｃの正しい値は、ディフィ−ヘルマン（Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ）問題を解決せずに、誤った値から計算することはできない。（本明細書で使用したｐおよびｑの小さい値の場合、その計算は可能である。ただし、「現実の」暗号パラメータの場合、Ｖのコンピュータは、その計算を行うことができない。）したがって、Ｖのコンピュータが、Ｖの選択に対応しない暗号化された票を提出した場合、Ｖのコンピュータが、確認を表示するものと予期される時点で行うことができるのは、２つのことだけである。コンピュータは、何かを表示するか、または何も表示しないことが可能である。何も表示されない場合、Ｖは、それを票が破損を生じたことの指示として受け止めることができる。何かが表示される場合、表示される物は、ほぼ確実に誤っており、この場合も、Ｖは、それを票が破損を生じたことの指示として受け止めることができる。
【００８９】
５．次に、Ｖは、表示されたＣの値を、選択「緑」（Ｖの意図する選択）に対応してＶの確認辞書の中で見出される値と比較する。この時点で、Ｖは、自分の確認辞書をあらかじめ既に受け取っていること、または任意の独立したチャネルを介してコピーを獲得することが可能である。そのようなチャネルの例が、ファックス装置を使用することである。表示された値が、確認辞書の中の対応する確認ストリングに一致しない場合、破損が検知され、票決特有のポリシーに従って票が「投票しなおされる」ことが可能である。
【００９０】
各投票者確認辞書は、投票収集センタによって計算される。というのは、前述したとおり、投票収集センタは、αおよびＫという投票者特有の値の知識を有するエンティティだからである。考慮してきた投票者Ｖのケースでは、辞書は、以下のとおり計算される。
【００９１】
【表３】
2004524759.tif 000028
【００９２】
ＳＶＣスキームを使用する際に本メカニズムによって提供されるセキュリティのレベルについて以下に説明する。Ａを投票クライアント敵対者とし、∈０を、任意の所与のμ１，．．．，μＫに関してＡが有効性証明を偽造することができる確率の上限とする。（∈０は、取るに足らないことが分かっている。）
定理１  ＳＶＣスキームが、Ｈ＝Ｉｄで実行されたものと想定する。１≦ｋ１≠ｋ２≦Ｋに設定する。何らかの∈＞０に関して、Ａが、確率∈で、
【００９３】
【数２４】
2004524759.tif 000029
【００９４】
を提出し、
【００９５】
【数２５】
2004524759.tif 000030
【００９６】
を表示し、ただし、この確率は、μ１，．．．，μＫ，ｇ，ｈ，βｉおよびＫｉに関する値のすべての組合せを対象に一様にとられているものと想定する。すると、Ａは、確率∈で、Ｏ（Ｋ）のさらなる作業によりディフィ−ヘルマン問題のランダムな実例を解決することができる。
【００９７】
証明：Ａに、Ｘ，Ｙ，Ｚ∈Ｒ＜ｇ＞が与えられているものと想定する。Ａは、すべてのｋ≠ｋ２に関してＣｉｋ１∈＜ｇ＞およびμｋ∈＜ｇ＞を独立に、ランダムに選び、
【００９８】
【数２６】
2004524759.tif 000031
【００９９】
およびμｋ２＝μｋ１Ｚに設定することにより、票決およびＳＶＣ交換をシミュレートすることができる。票決パラメータおよび
【０１００】
【数２７】
2004524759.tif 000032
【０１０１】
の上の結果の分布は、明らかに現実の票決から生じる分布と同一である。確率∈で、Ａは、
【０１０２】
【数２８】
2004524759.tif 000033
【０１０３】
を表示することができ、したがって、
【０１０４】
【数２９】
2004524759.tif 000034
を計算することができる。したがって、ｌｏｇＸＣ＝βｉｌｏｇｈＺ＝ｌｏｇＸＹｌｏｇＸＺおよびＣが、トリプル（Ｘ，Ｙ，Ｚ）によって与えられるディフィ−ヘルマン問題の実例に対する解である。
【０１０５】
系１  やはり、ＳＶＣスキームがＨ＝Ｉｄで実行されるものと想定する。
【０１０６】
【数３０】
2004524759.tif 000035
【０１０７】
と定める。何らかの∈１＞０に関して、Ａが、確率∈１で、ｋ１≠ｋ２を選択し、
【０１０８】
【数３１】
2004524759.tif 000036
【０１０９】
を提出し、
【０１１０】
【数３２】
2004524759.tif 000037
【０１１１】
を表示し、ただし、この確率は、μ１，．．．，μＫ，ｇ，ｈ，βｉおよびＫｉに関する値のすべての組合せを対象に一様にとられているものと想定する。すると、Ａは、確率∈１／（Ｋ−１）で、Ｏ（Ｋ）のさらなる作業によりディフィ−ヘルマン問題のランダムな実例を解決することができる。
【０１１２】
証明：定理１の論証に従うが、Ｋ−１個の独立したディフィ−ヘルマン問題の少なくとも１つに対する解を見出す問題と比較する。
【０１１３】
系２  ∈ＤＨをＡがランダムなディフィ−ヘルマンの実例を解決することができる確率の上限とする。すると、Ｈ＝Ｉｄである場合、Ａが投票者の選択とは異なる票を提出するが、正しい確認ストリングを表示することができる確率の上限は、∈０＋（Ｋ−１）∈ＤＨである。
【０１１４】
ハッシュ関数Ｈが自明ではない場合、Ｈの特性についての相当な特定の知識なしに、計算上のディフィ−ヘルマン問題と比較することができる望みはない。Ｈの特定の選択でスキームのセキュリティを考慮するのではなく、Ｈは無視できるほどの衝突確率しか有さないものと想定し、代わりに、セキュリティを決定ディフィ−ヘルマン問題（Ｄｅｃｉｓｉｏｎ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ  Ｐｒｏｂｌｅｍ）と比較する。考慮するこの問題の変種は、次のとおりである。Ａにタプルのシーケンス（Ｘｎ，Ｙｎ，Ｚｎ，Ｃｎ）が与えられ、ただし、Ｘｎ，Ｙｎ，Ｚｎは、独立にランダムに生成される。確率１／２で、Ｃｎは、ディフィ−ヘルマンの実例（Ｘｎ，Ｙｎ，Ｚｎ）に対する解であり、確率１−１／２＝１／２で、Ｃｎは、ランダムに、独立に生成される。Ａは、確率１／２＋∈で、質問
【０１１５】
【数３３】
2004524759.tif 000038
【０１１６】
に回答できる場合、∈−ＤＤＨのアドバンテージを有するものとされる。
【０１１７】
定理１、ならびに系１および２は、Ｈ≠Ｉｄであるケースにおいて明白な類似物を有する（Ｈは無視できるほどの衝突確率しか有さないものとだけ想定して）。言明と証明はともに、わずかな違いだけで構成され、したがって、以下のとおりにだけ要約する。
【０１１８】
系３  ∈ＤＤＨをＡのＤＤＨアドバンテージの上限とする。すると、Ｈが無視できるほどの衝突確率しか有さない任意のハッシュ関数である場合、Ａが、投票者の選択とは異なる票を提出するが、正しい確認ストリングを表示することができる確率の上限は、∈０＋（Ｋ−１）∈ＤＤＨである。
【０１１９】
ＳＶＣは、敵対者Ａが、投票収集センタも支配している場合、全く保護を提供しない可能性がある。これが該当する場合、Ａは、Ｋｉおよびβｉにアクセスを有し、したがって、自ら選んだ任意の有効な確認ストリングを容易に表示することができる。これが生じる可能性は低いように思われる。というのは、投票収集センタは、そのような活動が露顕した場合、否認しがたく連座させられるからである。しかしながら、この点で投票収集センタを信頼することが容認できない場合、「確認の責任」を不定の多数の権限者の間で配分することが可能である。
【０１２０】
確認の責任を配分するのに、１≦ｊ≦Ｊである各権限者Ａｊが、（投票者ｖｉに関して
）独立したランダムなＫｉｊおよびβｉｊを生成する。権限者は、独立したランダムなＫ
ｉｊおよびβｉｊを２つの一般的な方法によって結合することができる。
【０１２１】
１．連結  投票者の確認ストリングが、Ｊ名の権限者の各名に対応する個々の確認ストリング（前のセクションの場合と同様に別々に計算された）のあらかじめ指定された順序の連結として計算される。この場合、確認は、サブストリングのすべてが正しく検証された場合にだけ、成功である。
【０１２２】
２．信頼されるサーバまたは信頼されるプリンタ  単一の集中サーバ、または単一の集中プリンタを信頼することが容認できる場合、複数の確認ストリングを単に計算することによって結合し、同一サイズの１つの確認ストリングにすることができる。
【０１２３】
【数３４】
2004524759.tif 000039
これは、投票者に伝送されなければならない確認データの量を削減するという利点を有するが、システムに関して攻撃の集中ポイントを生じさせるという代償を払う。
【０１２４】
独立したチャネルを介して投票者に送信されなければならないデータのサイズを小さくすることは、常に望ましい。セクション３で説明したとおり、確認辞書は、最新の通信技術の標準に照らして既に小さいが、伝送されるデータをさらに減らすことができれば、費用の点で有利である可能性がある。前述したとおり、１つの手法は、秘密のＫｉおよびβｉを投票者に直接に送ることであるが、これは、「投票者の頭脳で」または「紙の上で」実行されるには重すぎる計算上の負担を投票者に負わせるという欠点を有する。ＳＶＣスキームの以下の変種は、両方の目標、すなわち、独立した通信チャネルを介するデータと、投票者による「頭の中での計算」をともに少なくすることを達する。これには、代償、すなわち、クライアントの敵対者が投票者を欺くことができる確率が高まることが伴うが、これは、全体的な票決の観点からは全く容認できる可能性がある。敵対者が検知されない確率が、例えば、１／２である場合でも、敵対者が投票のかなりの割合を変更するには、統計的に有意な割合の投票者によって敵対者が検知される確率は、非常に高くなる。序論で説明したとおり、是正措置が可能である。
【０１２５】
その考えは、疑いのあるクライアントを介して投票者に確認ストリングの完全なセットを送り届けるが、ランダムに置換された順序でこれを行うことである。すると、投票者が必要とする追加の情報は、使用された順列だけである。これでは、このシナリオでは、完全に十分ではない。というのは、すべての確認ストリングが用意されているので、敵対者は、単に消去のプロセスによっていくらかのアドバンテージを得ることができる。（Ｋ＝２であるケースを考慮するのが特に役立つ。）セキュリティを高めるため、やはり置換されたいくつかのランダムな確認ストリングを辞書に含める。
【０１２６】
サブセクション３．１におけるステップは、前の場合と同様に実行される。さらに、投票収集が、クライアントＭｉに「ランダム化された辞書」Ｄｉを送る。以上は、投票収集センタＣによって以下のとおり生成される。
【０１２７】
ＲＤ−１．Ｋ（投票者特有の）確認ストリング
【０１２８】
【数３５】
2004524759.tif 000040
は、前の場合と同様に計算される。
【０１２９】
ＲＤ−２．さらに、Ｌ個の追加のストリングが以下のとおり生成され、
【０１３０】
【数３６】
2004524759.tif 000041
ただし、ｅ１，．．．，ｅＬは、Ｚｑにおいて独立に、ランダムに生成される。
【０１３１】
ＲＤ−３．ランダムな順列、σｉ∈ΣＫ＋Ｌが生成される。
【０１３２】
ＲＤ−４．Ｃが、１≦ｊ≦Ｋ＋Ｌに関して、Ｑｉｊ＝Ｓｉσｉ（ｊ）に設定し、Ｄｉをストリングのシーケンス（Ｑｉ１，．．．Ｑｉ（Ｋ＋Ｌ））になるように設定する。
【０１３３】
Ｃが、独立したチャネルを介して、σｉの何らかの「人間が読むことができる」表現をｖｉに送った場合、ｖｉは、単に適切な索引で確認ストリングを見つけることによって自身の票を検証することができる。このスキームをＳＶＣＯで表す。
【０１３４】
ＳＶＣＯのセキュリティのレベルに関して、次の形態のディフィ−ヘルマン決定問題を考慮されたい。Ａに、タプルのシーケンス（Ｘｎ，Ｙｎ，Ｚｎ，Ｃｎ，Ｄｎ）が与えられ、ただし、Ｘｎ，Ｙｎ，Ｚｎは、独立にランダムに生成される。Ｒｎが、独立にランダムに生成されるものとし、またＯｎを
【０１３５】
【数３７】
2004524759.tif 000042
【０１３６】
に対する解とする。確率１／２で、（Ｃｎ，Ｄｎ）＝（Ｏｎ，Ｒｎ）であり、また確率１−１／２＝１／２で、（Ｃｎ，Ｄｎ）＝（Ｒｎ，Ｏｎ）である。Ａは、確率１／２＋∈で、質問
【０１３７】
【数３８】
2004524759.tif 000043
【０１３８】
に回答することができる場合、∈−ＤＤＨＰのアドバンテージを有するとされる。つまり、Ａは、問題の最初のバージョンと同じ質問に回答しなければならないが、より多くの情報を利用できるため、問題はより容易である可能性がある。
【０１３９】
定理２  ∈ＤＤＨＰをＡのＤＤＨＰアドバンテージの上限とし、またＨを無視できるほどの衝突確率しか有さない任意のハッシュ関数とする。ＳＶＣＯスキームの下で、Ａが、投票者の選択とは異なる票を提出するが、正しい確認ストリングを表示することができる確率の上限は、以下のとおりである。
【０１４０】
【数３９】
2004524759.tif 000044
証明：定理１の証明の場合と同様に、Ａは、票決およびＳＶＣＯ交換をシミュレートすることができる。ただし、この場合、Ａは、ＳＶＣスキームにおいては用意されていなかった確認ストリングのリストもシミュレートしなければならない。固定されたｋ１、ｋ２に関して、Ａは、
【０１４１】
【数４０】
2004524759.tif 000045
【０１４２】
をランダムに選ぶことができ、またすべてのｋ≠ｋ２に関して、θｋ∈Ｚｑを独立にランダムに選ぶことができる。次に、Ａは、
【０１４３】
【数４１】
2004524759.tif 000046
【０１４４】
に設定する。ｋ≠ｋ１，ｋ２に関して、Ａは、
【０１４５】
【数４２】
2004524759.tif 000047
【０１４６】
に設定する。Ａは、
【０１４７】
【数４３】
2004524759.tif 000048
【０１４８】
に設定し、Ｌ個の追加のランダムなμｌおよびｌ−１個の追加のＣｉｌをランダムに生成する。最後に、Ａは、
【０１４９】
【数４４】
2004524759.tif 000049
【０１５０】
に設定し、最後に残っている
【０１５１】
【数４５】
2004524759.tif 000050
【０１５２】
に設定する。前の場合と同様に、正しい確認ストリングを見出すことは、値Ｃｎ、Ｄｎのどれが正しいディフィ−ヘルマン解であるかを決定することと等価である。すべての順列を一様の確率で平均すると、次の結果がもたらされる。
【０１５３】
以下に、以上に説明した秘密投票確認スキームに対する１つの可能な代案を説明する。２つのスキーム間のセキュリティのレベルは基本的に等価である。
【０１５４】
１．票決公開鍵ｈに加えて、投票収集が、
【０１５５】
【数４６】
2004524759.tif 000051
【０１５６】
の形態の別の公開鍵を公表し、ただし、ｄ∈Ｚｑは、投票収集センタだけに知られている秘密である。
【０１５７】
２．クライアントＭｉが、前の場合と同様に、ｖｉに代わって暗号化された票を提出するが、票は、ｈと
【０１５８】
【数４７】
2004524759.tif 000052
【０１５９】
で冗長に暗号化される。第２の暗号化を
【０１６０】
【数４８】
2004524759.tif 000053
で表す。ただし、
【０１６１】
【数４９】
2004524759.tif 000054
【０１６２】
は、αｉとは独立に選択される。
【０１６３】
３．Ｍｉは、２つが同一の値の暗号化であることの有効性の単純な証明（基本的に、単一のＣｈａｕｍ−Ｐｅｄｅｒｓｅｎ証明）も構成する。
【０１６４】
４．有効性の証明が投票収集センタにおいて合格しなかった場合、前の場合と同様に破損が検知される。
【０１６５】
５．投票収集センタが、ランダムなＫｉ∈＜ｇ＞を選択し、βｉ∈Ｚｑであり、以下を計算する。
【０１６６】
【数５０】
2004524759.tif 000055
６．投票収集センタが、
【０１６７】
【数５１】
2004524759.tif 000056
【０１６８】
およびＶｉをＭｉに戻す。
【０１６９】
７．Ｍｉが、
【０１７０】
【数５２】
2004524759.tif 000057
【０１７１】
を以下の数式
【０１７２】
【数５３】
2004524759.tif 000058
によって計算し、その値（またはＨ（Ｓｉ））を投票者ｖｉに表示する。
【０１７３】
８．投票者が、前の場合と同様に確認辞書を要求し、表示された値に照らしてチェックする。
【０１７４】
破損が検知された場合、前の場合と同様に是正措置がとられる。
【０１７５】
前記の本メカニズムの説明は、すべての投票者に関して単一のｄ（したがって、単一の
【０１７６】
【数５４】
2004524759.tif 000059
【０１７７】
）を使用し、票決に先立ってこの値を公表することを述べている。
【０１７８】
代替として、投票収集センタ（または分散した１組の「確認権限者」）が、各投票者ｖｉに関して独立したランダムなｄｉ（また、したがって、
【０１７９】
【数５５】
2004524759.tif 000060
【０１８０】
も）発行する。値ｄｉは、常に秘密にしておかれるが、値
【０１８１】
【数５６】
2004524759.tif 000061
【０１８２】
は、ｖｉに伝えられる。
【０１８３】
一実施形態では、本メカニズムは、
【０１８４】
【数５７】
2004524759.tif 000062
【０１８５】
を以下のとおりｖｉに伝える。
【０１８６】
Ａ−１  ｖｉが、投票収集センタに接触し、ｖｉ自身を認証する。
【０１８７】
Ａ−２  認証が成功したものと想定すると、投票収集センタは、
１．ｄｉをランダムに生成し、
２．
【０１８８】
【数５８】
2004524759.tif 000063
【０１８９】
を計算し、
３．
【０１９０】
【数５９】
2004524759.tif 000064
【０１９１】
をｖｉに送る。
【０１９２】
Ａ−３  次に、投票者ｖｉが、
【０１９３】
【数６０】
2004524759.tif 000065
【０１９４】
の代わりに
【０１９５】
【数６１】
2004524759.tif 000066
【０１９６】
を使用して前述したとおりに事を進める。
【０１９７】
別の実施形態では、本メカニズムは、
【０１９８】
【数６２】
2004524759.tif 000067
【０１９９】
を以下のとおりｖｉに伝える。
【０２００】
Ｂ−１  ｖｉが、投票収集センタに接触する（また、オプションとして、ｖｉ自らを認証する）
Ｂ−２  ｖｉが、投票選択ｍｉを行い、暗号化された票
【０２０１】
【数６３】
2004524759.tif 000068
【０２０２】
を戻す。
【０２０３】
Ｂ−３  投票収集センタが、この時点で、
１．ｄｉをランダムに生成し、
２．
【０２０４】
【数６４】
2004524759.tif 000069
【０２０５】
を計算し、
３．
【０２０６】
【数６５】
2004524759.tif 000070
【０２０７】
をｖｉに送る。
【０２０８】
Ｂ−４  次に、投票者ｖｉが、
１．ｍｉの第２の暗号化を
【０２０９】
【数６６】
2004524759.tif 000071
【０２１０】
として生成し、
２．第１の暗号化および第２の暗号化が同一の投票選択ｍｉの暗号化であることを示す同じ有効性の証明を生成し、
３．第２の暗号化と有効性の証明をともに投票収集代理に送る。
【０２１１】
Ｂ−５  確認プロセスの残りは、前述したのと同様に進められる。
【０２１２】
図１〜３は、本メカニズムのある態様を示している。図１は、本メカニズムが動作する通常の環境を示す高レベルブロック図である。このブロック図は、いくつかの投票者コンピュータシステム１１０を示しており、コンピュータシステム１１０のそれぞれが、投票者により、票を提出し、票の破損されていない受領を検証するのに使用されることが可能である。投票者コンピュータシステムのそれぞれは、インターネット１２０を介して投票収集センタコンピュータシステム１５０に接続される。ただし、投票者コンピュータシステムは、インターネット以外のネットワークによって投票収集センタコンピュータシステムに接続することも可能であることが、当分野の技術者には理解されよう。本メカニズムは、投票者コンピュータシステムからの票を投票収集センタコンピュータシステムに伝送し、投票収集センタコンピュータシステムは、暗号化された投票確認を戻す。各投票者コンピュータシステムにおいて、本メカニズムは、この暗号化された投票確認を使用して、提出された票が破損しているかどうかを判定する。好ましい実施形態を前述した環境に関して説明しているが、本メカニズムは、単一のモノリシック（ｍｏｎｏｌｉｔｈｉｃ）コンピュータシステム、ならびに様々な仕方で接続されたコンピュータシステム群または同様のデバイス群の様々な他の組合せを含む様々な他の環境においても実施できることが、当分野の技術者には理解されよう。
【０２１３】
図２は、コンピュータシステム１１０および１３０などの、本メカニズムを実行するコンピュータシステムおよびその他のデバイスの少なくともいくつかに、通常、組み込まれる構成要素のいくつかを示すブロック図である。これらのコンピュータシステムおよびデバイス２００は、コンピュータプログラムを実行するための１つまたは複数の中央処理装置（「ＣＰＵ」）２０１と、プログラムおよびデータが使用されている間、そのプログラムおよびデータを記憶するためのコンピュータメモリ２０２と、プログラムおよびデータを持続的に記憶するためのハードドライブなどの持続記憶デバイス２０３と、コンピュータ可読媒体上に記憶されたプログラムおよびデータを読み取るためのＣＤ−ＲＯＭドライブなどのコンピュータ可読媒体ドライブ２０４と、インターネットを介するなどしてコンピュータシステムを他のコンピュータシステムに接続するためのネットワーク接続２０５とを含む。前述したとおりに構成されたコンピュータシステムが、好ましくは、本メカニズムの動作をサポートするのに使用されるが、本メカニズムは、様々なタイプおよび様々な構成の、様々な構成要素を有するデバイスを使用して実施できることが、当分野の技術者には理解されよう。
【０２１４】
図３は、セキュリティが損なわれた票を検知するために本メカニズムによって通常、行われるステップを示す流れ図である。本メカニズムは、これらのステップの適切なスーパーセットおよびサブセット、これらのステップの並べ替え、およびいくつかのステップが他のコンピューティングデバイスによって行われるセットのステップを含め、図示したステップとは相違する１組のステップを行うことも可能であることが、当分野の技術者には理解されよう。
【０２１５】
ステップ３０１で、投票者コンピュータシステム上で、本メカニズムは、票を形成するために、投票者によって選択された投票選択を符号化する。ステップ３０２で、本メカニズムは、この票を暗号化する。いくつかの実施形態では、暗号化された票は、票決公開鍵、および投票者コンピュータシステム上に保持される秘密を使用して生成されるＥｌＧａｍａｌペアである。ステップ３０３で、本メカニズムは、オプションとして、投票者に所属する秘密鍵で票に署名する。ステップ３０４で、本メカニズムは、暗号化された票が、有効な投票選択が選択された票の暗号化であることを示す有効性証明を構成する。ステップ３０５で、本メカニズムは、暗号化された署名付きの票、および有効性証明を投票収集センタコンピュータシステムに伝送する。
【０２１６】
ステップ３２１で、本メカニズムは、投票収集センタコンピュータシステムにおいてこの伝送を受信する。ステップ３２２で、本メカニズムは、受信された有効性証明を検証する。ステップ３２３で、有効性証明が成功裡に検証された場合、本メカニズムは、３２４に進み、成功裡に検証されなかった場合、本メカニズムは、ステップ３２４に進まない。ステップ３２４で、本メカニズムは、暗号化された票の暗号化された確認を生成する。本メカニズムは、票を解読することなく、この確認を生成する。票を解読することは、票を暗号化するのに使用された秘密が利用できない投票収集センタコンピュータシステムにおいては、通常、不可能である。ステップ３２５で、本メカニズムは、暗号化された確認３３１を投票者コンピュータシステムに伝送する。
【０２１７】
ステップ３４１で、本メカニズムは、投票者コンピュータシステムにおいて暗号化された投票確認を受信する。ステップ３４２で、本メカニズムは、投票者コンピュータシステム上に保持される秘密を使用して、暗号化された投票確認を解読する。ステップ３４３で、本メカニズムは、解読された投票確認をユーザが閲覧するために表示する。ステップ３４４で、表示された投票確認が、投票者が所有する確認辞書によって投票者が選択した投票選択に翻訳された場合、本メカニズムは、ステップ３４５に進み、翻訳されなかった場合、本メカニズムは、ステップ３４６に進む。ステップ３４５で、本メカニズムは、投票者の票が破損していないと判定し、一方、ステップ３４６で、本メカニズムは、投票者の票が破損していると判定する。破損している場合、本メカニズムの実施形態は、ユーザが、投票者の票を取り消し、提出しなおすのを助ける。
【０２１８】
前述した本メカニズムは、様々な仕方で簡単に適合させること、または拡張することが可能であることが、当分野の技術者には理解されよう。以上の説明は、好ましい実施形態を参照しているが、本発明の範囲は、特許請求の範囲、および特許請求の範囲に記載される構成要件だけによって規定される。
【図面の簡単な説明】
【０２１９】
【図１】本メカニズムが動作する通常の環境を示す高レベルブロック図である。
【図２】本メカニズムが実行されるコンピュータシステムおよびその他のデバイスの少なくともいくつかに、通常、組み込まれる構成要素のいくつかを示すブロック図である。
【図３】セキュリティが損なわれた票を検知するために本メカニズムによって通常、行われるステップを示す流れ図である。
【図１】
2004524759.tif 000084
【図２】
2004524759.tif 000085
【図３】
2004524759.tif 000086
【国際公開パンフレット】
2004524759.tif 000087
2004524759.tif 000088
2004524759.tif 000089
2004524759.tif 000090
2004524759.tif 000091
2004524759.tif 000092
2004524759.tif 000093
2004524759.tif 000094
2004524759.tif 000095
2004524759.tif 000096
2004524759.tif 000097
2004524759.tif 000098
2004524759.tif 000099
2004524759.tif 000100
2004524759.tif 000101
2004524759.tif 000102
2004524759.tif 000103
2004524759.tif 000104
2004524759.tif 000105
2004524759.tif 000106
2004524759.tif 000107
2004524759.tif 000108
2004524759.tif 000109
2004524759.tif 000110
2004524759.tif 000111
2004524759.tif 000112
2004524759.tif 000113
2004524759.tif 000114
2004524759.tif 000115
2004524759.tif 000116
2004524759.tif 000117
2004524759.tif 000118
2004524759.tif 000119
2004524759.tif 000120
2004524759.tif 000121
2004524759.tif 000122
2004524759.tif 000123
2004524759.tif 000124
2004524759.tif 000125
2004524759.tif 000126
【国際公開パンフレット（コレクトバージョン）】
2004524759.tif 000127
2004524759.tif 000128
【国際調査報告】
2004524759.tif 000129