(57)【要約】暗号化プロトコルを提供してモジュール整数（ｋ）のシーケンス（を検証可能にシャッフルする）数学的構成を提示し、安全で例外なく検証可能な複数機関選挙方式への応用について論じる。シャッフルオペレーションの出力は、モジュール整数（ｋ）の他のシーケンスであり、各々が対応する入力要素の同じ秘密の累乗であるが、出力内の要素の順序は秘密に保たれる。「シャッフラ」（適用される要素の並べ替えを選択する人）にとって、入力から出力を計算することは些細なことであるが、構成は、１人または複数の任意の検証者によってチェックすることができる出力シーケンスに関する正当性の線形サイズ証明（すなわち、請求された形であることの証明）を提供するので重要である。プロトコルは、特別の場合に公正な検証者のゼロ知識であることが示され、一般には計算上のゼロ知識である。最終結論に導く１つの方法として、離散対数式の知識に関してよく知られたChaum-Pedersenプロトコルの一般化も構築する（［３］、［２］）。実際に、一般化は（ｋ）＝２の場合、Chaum-Pedersenプロトコルに（正確に）特化される。この結果はそれ自体に関係がある場合がある。現在の最高のプロトコルの機能を重要な効率の改善に合致させる、電子投票への応用が与えられる。（例外なく検証可能な）選挙を達成するためのまったく新しい模範例を導入する、電子投票への代替の応用も与えられる。
2005524250.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ化されたネットワークと共に使用する電子投票システムであって、
コンピュータ化されたネットワークに結合された少なくとも第１、第２および第３の投票者コンピュータから要求を受け取るために結合された少なくとも１つのサーバコンピュータを備え、
前記第１の投票者コンピュータは、複数の投票者コンピュータから受け取った電子信用証明の集約体に対応する一連の電子信用証明を、前記サーバコンピュータから受け取るように構成され、各電子信用証明は、デジタル署名アルゴリズム（ＤＳＡ）またはElGamalペアであり、前記第１の投票者コンピュータは、少なくとも第１の秘密鍵を使用して、秘密の一方向暗号変換を適用して、前記一連の電子信用証明を匿名でシャッフルし、前記サーバコンピュータの一連の第１のシャッフル済み信用証明を生成するように構成され、前記第１の投票者コンピュータのみが、前記一連の第１のシャッフル済み信用証明と前記一連の電子信用証明との間の一致を知っており、前記第１の投票者コンピュータは、反復対数乗算証明に基づいて前記一連の第１のシャッフル済み信用証明に関する正当性の第１の線形サイズ証明を提供し、第１の無記名投票に第１の関連付けられた信用証明を提供するように構成され、
前記第２の投票者コンピュータは、前記サーバコンピュータから、前記一連の第１のシャッフル済み信用証明を受け取り、少なくとも第２の秘密鍵を使用して前記暗号変換を適用し、前記一連の第１のシャッフル済み信用証明を匿名でシャッフルし、前記サーバコンピュータの一連の第２のシャッフル済み信用証明を生成するように構成され、前記第２の投票者コンピュータのみが、前記一連の第１のシャッフル済み信用証明と前記一連の第２のシャッフル済み信用証明との間の一致を知っており、前記第２の投票者コンピュータは、第２の関連付けられた信用証明を有する第２の無記名投票と共に、反復対数乗算証明に基づいて前記一連の第２のシャッフル済み信用証明に関する正当性の第２の線形サイズ証明を第２のサーバコンピュータに提供するように構成され、
前記第３の投票者コンピュータは、前記一連の第２のシャッフル済み信用証明を受け取り、少なくとも第３の秘密鍵を使用して前記暗号変換を適用し、前記一連の第２のシャッフル済み信用証明を匿名でシャッフルし、前記サーバコンピュータの一連の第３のシャッフル済み信用証明を生成するように構成され、前記第３の投票者コンピュータのみが、前記一連の第２のシャッフル済み信用証明と前記一連の第３のシャッフル済み信用証明との間の一致を知っており、前記第３の投票者コンピュータは、第３の関連付けられた信用証明を有する第３の無記名投票と共に、反復対数乗算証明に基づいて前記一連の第３のシャッフル済み信用証明に関する正当性の第３の線形サイズ証明を提供するように構成され、
前記サーバコンピュータは、前記第１、第２および第３の投票者コンピュータから正当性の証明を受け取り、前記シャッフル済み信用証明の正当性を検証し、各々第１、第２および第３の関連付けられた信用証明を有する第１、第２および第３の無記名投票を受け取り、検証し、集計するように構成されたことを特徴とするシステム。
【請求項２】
前記コンピュータ化されたネットワークに結合された複数の機関コンピュータであって、前記第１、第２および第３の無記名投票は、しきい値、基礎となるグループＺｐまたは楕円曲線を使用する離散対数非対称暗号化プロセスの下で暗号化され、
次に前記複数の機関コンピュータの各々は、
少なくとも前記第１、第２および第３の暗号化された無記名投票を受け取り、
前記無記名投票を秘密にシャッフルし、
前記秘密にシャッフルされた無記名投票に暗号解除鍵の割り当てを適用して、前記秘密にシャッフルされた無記名投票を部分的に暗号解除し、
前記部分的に暗号解除され秘密にシャッフルされた無記名投票を、次の機関コンピュータに渡すことを特徴とする請求項１に記載のシステム。
【請求項３】
前記第１、第２および第３の投票者コンピュータは、少なくとも第１、第２および第３の公開鍵の識別を、前記第１、第２および第３の投票者コンピュータに各々すべて関連付けられた電子信用証明の集約体において、前記サーバコンピュータに提供するように構成され、
前記サーバコンピュータは、前記第１、第２および第３の公開鍵をそれに応答して除去するように構成されたことを特徴とする請求項１に記載のシステム。
【請求項４】
前記コンピュータ化されたネットワークは、ワールドワイドウェブを含み、前記第１、第２および第３の投票者コンピュータは、ウェブブラウザプログラムを含むことを特徴とする請求項１に記載のシステム。
【請求項５】
前記第１、第２および第３の投票者コンピュータのうちの少なくとも１つは、パームサイズコンピュータ、セル式電話、ウェアラブルコンピュータ、対話型テレビジョン端末、またはインターネット機器であることを特徴とする請求項１に記載のシステム。
【請求項６】
要素のシーケンスを受け取るためのコンピュータシステムであって、
コンピュータネットワークに結合され、
個々のデータファイルを表す電子データ要素のシーケンスを受け取り、
少なくとも第１の秘密値を使用して暗号化変換を適用して、前記電子データ要素のシーケンスを匿名で並び替え、電子データ要素の第１のシャッフル済みシーケンスを生成し、前記サーバコンピュータは、前記電子データ要素の第１のシャッフル済みシーケンスと前記電子データ要素のシーケンスとの間の一致を知っており、
２進演算子を使用する反復対数乗法証明に基づいて前記電子データ要素の第１のシャッフル済みシーケンスの正当性の第１の線形サイズ証明を生成し、前記データ要素のシーケンス内の前記データ要素の各々は、共通のベース値に関連付けられ、前記正当性の証明を検証することは、３ムーブ、パブリックコイン証明の知識を使用し、ここで、前記コンピュータは、検証要求に応答して関連付けられた一連の線形等式を解くことによって、一連の指数を計算するように構成されたコンピュータ
を備えたことを特徴とするシステム。
【請求項７】
前記受け取られた電子データ要素のシーケンスは、コンピュータが知らない鍵を使用するＺｐまたは楕円曲線グループを使用して暗号化され、前記コンピュータは、
検証者コンピュータからランダムに生成された値ｅｉを受け取り、
前記受け取られた一連の値ｅｉと秘密に生成された値とを使用する、秘密の一方向暗号化変換に基づいて、一連の値Ｄｉを秘密に生成し、
前記電子データ要素のシーケンスを並べ替え、前記一連の値Ｄｉおよび秘密値γに基づいて、前記要素の第１のシャッフル済みシーケンスを生成し、
前記暗号化変換に基づいて、前記サーバコンピュータが、前記暗号化変換がどのように前記電子データ要素のシーケンスを並べ替えたかのアクセスを有する知識の証明として、前記値Ｄｉおよび一連の証明値を提供し、前記暗号化変換を前記検証者コンピュータに対して明らかにすることなく、前記要素の第１のシャッフル済みシーケンスを生成するように構成されたことを特徴とする請求項６に記載のシステム。
【請求項８】
前記サーバコンピュータは、
対応する複数の個人から複数の公開鍵を受け取り、前記複数の個人の各々は、前記複数の公開鍵のうちの１つに対応する秘密鍵を有し、
１つの秘密鍵を有する前記複数の個人のうちの１人から要求を受け取り、
前記複数の公開鍵のうち少なくとも１つのサブセットを要求側の個人に提供し、
反復対数乗算証明および前記１つの秘密鍵に対応する値に基づいて、前記複数の公開鍵のファイルおよびシャッフルと、前記シャッフル済み公開鍵に関する正当性の線形サイズ証明とを受け取り、前記値は、前記ファイルに関連付けられ、前記１つの秘密鍵を明らかにすることなく、１人の個人が前記１つの秘密鍵の知識を有するという証明を提供し、
前記正当性の証明をチェックし、
前記値が前記公開鍵および前記ファイルのうちの１つに数学的に関係していることをチェックし、
前記複数の公開鍵から１つの公開鍵を減らすように
構成されたことを特徴とする請求項６に記載のシステム。
【請求項９】
前記電子要素のシーケンスは、公開鍵であり、前記サーバは、個人からの要求に応答して、個人が前記公開鍵のうちの１つに一意かつ数学的に関係する値を有することをチェックするように構成され、
そうであれば、前記１人の個人に対して証明書を発行することを特徴とする請求項６に記載のシステム。
【請求項１０】
コンピュータ実施方法であって、
複数の公開鍵のうちの１つに対応する秘密鍵を有する複数の個人のうちの１人からの要求を受け取ること、
前記複数の公開鍵のうちの少なくとも１つのシャッフル済みサブセットを、要求側個人に提供すること、
ファイルＦと、
（１）公開鍵の新しいシャッフル済みセットＳ、
（２）前記公開鍵の新しいシャッフル済みセットに関する正当性のシャッフル証明、および
（３）前記要求側個人からの署名値ｘからなる認証とを受け取ること、および
前記認証を、
（ａ）前記正当性のシャッフル証明の検証が成功し、および
（ｂ）Ｖ（Ｆ，ｘ，ｓ０）が真であり、ただし、Ｖは署名検証機能であり、ｓ０は前記公開鍵の新しいシャッフル済みセットＳからの１つの公開鍵である場合に受け取ること
を備えたことを特徴とする方法。
【請求項１１】
コンピュータ実施方法であって、
複数の公開鍵のうちの１つの公開鍵に対応する１つの秘密鍵に関連付けられたコンピュータから要求を受け取り、前記複数の公開鍵の各々は、複数の秘密鍵のうちの１つに対応すること、
前記複数の公開鍵のうちの少なくとも１つのシャッフル済みサブセットを前記要求側コンピュータに提供すること、
前記要求側コンピュータからファイルを受け取ること、
反復対数乗算証明および前記１つの秘密鍵に対応する値に基づいて、前記複数の公開鍵の新しいシャッフル済みサブセットと、前記公開鍵の新しいシャッフル済みサブセットに関する正当性の線形サイズ証明とを受け取り、前記値は、前記ファイルに関連付けられ、前記１つの秘密鍵を明らかにすることなく、１人の個人が前記１つの秘密鍵の知識を有するという証明を提供すること、
前記正当性の証明をチェックすること、および
前記値が前記公開鍵および前記ファイルのうちの１つに、実質的に一意の方法で数学的に関係していることをチェックすること
を備えたことを特徴とする方法。
【請求項１２】
前記要求側コンピュータから、前記公開鍵の新しいシャッフル済みサブセット内の前記１つの公開鍵の少なくとも１つの指示を受け取ることをさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記公開鍵の新しいシャッフル済みサブセットから前記１つの公開鍵を除去することをさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１４】
複数の公開鍵の少なくとも１つのサブセットＨ上で実行された秘密の暗号シャッフルオペレーションに基づいて、複数の公開鍵のシャッフル済みサブセットＨ’を複数の機関の各々から順番に受け取り、前記複数の公開鍵のシャッフル済みセットＨ’を生成すること、
前記暗号シャッフルオペレーションの検証写しを複数の機関の各々から順番に受け取ること、および
前記検証の写しに基づいて、前記暗号シャッフルオペレーションの正当性を検証し、検証された場合は、前記複数の公開鍵のシャッフル済みセットをＨ’からＨに設定すること
をさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１５】
前記複数の公開鍵の少なくとも一部を受け取った後に、前記受け取った複数の公開鍵のうち少なくとも１つのサブセットを前記複数の公開鍵のうち受け取ったシャッフル済みセットに設定し、前記複数の公開鍵のうちのシャッフル済みセットは、第三者から受け取られたことを特徴とする請求項１１に記載の方法。
【請求項１６】
前記チェックステップに従って、証明書を発行すること、
その後、複数の個人のうちの１人から前記発行された証明書を受け取ること、および
前記１人の個人に電子無記名投票を提供すること
をさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１７】
受け取った要求にデジタル署名して、公開鍵インフラストラクチャ（ＰＫＩ）証明書を生成することをさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１８】
複数のユーザコンピュータのうちの少なくとも一部から発行された証明書を受け取り、それに応答して初期の電子無記名投票を提供すること、および
前記複数のユーザコンピュータのうちの少なくとも一部から、暗号化されていない投票済みの無記名投票を受け取ること
をさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１９】
証明者コンピュータと検証者コンピュータとの間のコンピュータ実施暗号化方法であって、
電子データ要素の第２のシリーズに関して電子データ要素の第１のシリーズを秘密にシャッフルして、シャッフル済みセットを生成すること、および
第１の多項式に関する第１のルートセットが、第２の多項式に関する第２のルートセットの固定定数倍に等しいことの証明に基づいて、前記シャッフル済みセットに関する正当性の線形サイズ証明を生成することを備え、
前記第１のルートセットが前記第２のルートセットの固定倍に等しいことの正当性の前記線形サイズ証明は、第２の固定定数を指定すること、第１のランダムポイントで前記第１の多項式を評価して第１の値を得ること、前記第１のランダムポイントで前記第２の多項式を評価して第２の値を得ること、および前記第２の値が前記第１の値と前記第２の固定定数との積に等しいことを判定することによって得られることを特徴とする方法。
【請求項２０】
前記第１の要素シーケンス内の要素のうちの少なくとも一部は、電子無記名投票であることを特徴とする請求項１９に記載の方法。
【請求項２１】
前記シャッフル済みセット内の要素のうちの少なくとも一部は、ElGamalペアであることを特徴とする請求項１９に記載の方法。
【請求項２２】
秘密のシャッフルを反復すること、要素の入力シーケンスでｌ組の要素を生成して提供することをさらに備えたことを特徴とする請求項１９に記載の方法。
【請求項２３】
前記要素の第１のシリーズを秘密にシャッフルすることは、識別要素セットのサブセットを受け取ることを含み、前記セット内の各識別要素は、個人に対応し、前記方法は、
前記検証コンピュータが前記正当性の証明を検証した場合、匿名の証明書を受け取ることをさらに備えたことを特徴とする請求項１９に記載の方法。
【請求項２４】
コンピュータ化されたネットワークで使用するための電子投票システムであって、
前記コンピュータ化されたネットワークに結合され、しきい値と離散対数非対称暗号化プロセスの下で暗号化された複数の無記名投票を受け取る複数の機関のコンピュータを備え、
前記複数の機関のコンピュータの各々は、順に、
少なくとも前記暗号化された無記名投票を受け取り、
前記無記名投票を秘密にシャッフルし、
前記秘密にシャッフルされた無記名投票に暗号解除鍵の割り当てを適用し、前記秘密にシャッフルされた無記名投票を部分的に暗号解除し、
前記部分的に暗号解除された無記名投票に関する妥当性証明を生成し、
前記部分的に暗号解除され秘密にシャッフルされた無記名投票を、次の機関コンピュータに渡すように構成されたことを特徴とするシステム。
【請求項２５】
コンテンツが命令を提供し、コンピュータによって実施されると、電子データ要素のシーケンスのシャッフルを実行する、コンピュータ読取り可能媒体であって、
複数の公開鍵のうちの１つの公開鍵に対応する１つの秘密鍵に関連付けられたコンピュータからの要求を提供し、前記複数の公開鍵の各々は、複数の秘密鍵の１つに対応すること、
前記複数の公開鍵のうち少なくとも１つのシャッフル済みサブセットを受け取ること、
ファイルを提供すること、および
反復対数乗算証明および前記１つの秘密鍵に対応する値に基づいて、前記複数の公開鍵の新しいシャッフル済みサブセットと、前記公開鍵の新しいシャッフル済みサブセットに関する正当性の線形サイズ証明とを生成し、前記値は、前記ファイルに関連付けられ、前記１つの秘密鍵を明らかにすることなく前記１つの秘密鍵の知識の証明を提供し、前記正当性の線形サイズ証明は、第１および第２の多項式の計算を含み、前記第１の多項式に関して選択されたランダムポイントは、結果的に前記第２の多項式を解くための等価な一連のルートを発生させること
を備えたことを特徴とするコンピュータ読取り可能媒体。
【請求項２６】
前記コンピュータ読取り可能媒体は、前記電子データ要素のシーケンスおよび前記コンテンツを受け取るコンピュータネットワーク内の論理ノードであることを特徴とする請求項２５に記載のコンピュータ読取り可能媒体。
【請求項２７】
前記コンピュータ読取り可能媒体は、コンピュータ読取り可能ディスクであることを特徴とする請求項２５に記載のコンピュータ読取り可能媒体。
【請求項２８】
前記コンピュータ読取り可能媒体は、前記コンテンツを含む生成済みデータ信号を伝送するデータ伝送媒体であることを特徴とする請求項２５に記載のコンピュータ読取り可能媒体。
【請求項２９】
前記コンピュータ読取り可能媒体は、コンピュータシステムのメモリであることを特徴とする請求項２５に記載のコンピュータ読取り可能媒体。
【請求項３０】
前記コンピュータ読取り可能媒体は、投票機関のサーバコンピュータへのインターネット接続リンクであることを特徴とする請求項２５に記載のコンピュータ読取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子投票の応用に関する。
【発明の開示】
【０００２】
（１  はじめに）
オブジェクト、レコード、またはトークンの集まりのシャッフルという概念は、単純かつ直感的であり、人間の様々な日常活動の中に有用な例が数多く見られる。カジノのギャンブラーは、自分の手持ちカードの中のそれぞれが５２の一義的な値の１つであり、テーブルの誰も自分の手持ちとまったく同じカードを持っていないことを知っている。ただし、たとえディーラーがシャッフルする前のカードの正確な順序を記録しておくことができても、カードがどのように配られるかはまったくわからない。
【０００３】
電子データの文脈では、同種の入力シーケンスのランダムであるが検証可能な並べ替えを達成するという問題は、驚くほど困難である。問題は、データそれ自体が監査者（auditor）に常時見える、または見えないことである。見ることができる場合、入力レコードと出力レコードとの対応関係は、監査者または他の監視者が再構築するのはささいなことである。見ることができない場合、入力レコードと出力レコードとは、基礎となるデータが同一で、異なる表現でなければならない。しかし、監査者が対応関係を再構築できないほど出力が異なる（すなわち、十分に暗号化されている）場合、監査者は、シャッフラが基礎となるデータをシャッフルの過程で変更しなかったことをどのようにして確認できるであろうか。
【０００４】
本明細書のほとんどが、重要な状況、すなわちElGamalまたはDiffie-Hellman法で暗号化されたデータにあるこの問題を解決するための、効率的な（線形）方法を与えることに充てられている。説明をできる限り明確かつ簡潔にするために、明細書の大部分が、大きな素数ｐを法とした単位の乗法グループ
【０００５】
【数１】
2005524250.tif 000003
【０００６】
の素数サブグループで演算を実行する特定のケースについて明示的に言及している。ただし、ここで使用する基礎となる（乗法）グループの唯一のプロパティは、関連付けられたDiffie-Hellman問題が至難なことである。したがって、ElGamal暗号システムが楕円曲線などの他のグループを介して実施される場合は、シャッフルプロトコルも有用である。
【０００７】
［１］および［４］の一般的なブール証明技法を、同じプロパティを使用して証明を構成する際にも使用することができ、結果として生じる証明サイズ（複雑さ）は、入力シーケンスのサイズにおいて２次（quadratic）またはそれよりも悪い。
【０００８】
本明細書の技法は、［８］で使用された削除および選択（cut-and-choose）技法を介していくつかの利点も提供する。この方法では、証明のサイズは、すべての参加者を満足させるのに必要な不正行為の証明者（prover）の確率に依存する。本明細書のシャッフルプロトコルでは、この不正行為の確率は本質的にｋ／ｑであり、ここでｋはシャッフルされる要素の数、ｑは要素が暗号化されたサブグループ
【０００９】
【数２】
2005524250.tif 000004
【００１０】
のサイズである。［８］では不正行為の確率への証明サイズの依存は分析されていないが、同様に低い不正行為の確率を得るためには、本明細書で与えられた証明のサイズよりも何桁も大きい必要があることが明らかである。（さらに、［８］プロトコルが相互に作用し合わずに実施された場合、悪意ある参加者が徹底的な検索によって偽の証明を生成するためにかなりのオフライン計算を使用する可能性があるため、不正行為の確率が非常に小さくなるよう選択する必要がある。これはもちろん、本明細書のプロトコルを使用した場合でも同様であるが、ｋおよびｑがすべて実用的な値の場合、たとえオフライン攻撃であっても、確率ｋ／ｑは間違いなく十分に小さい。）
【００１１】
本明細書の結果は、例外なく検証可能な選挙プロトコルを実施するためのいくつかの方法を提供する。そのうちのいくつかが最終項に提示されている。この文脈では、［２］の明快な準同形選挙プロトコルに匹敵する。そのプロトコルは、無記名投票（ｂａｌｌｏｔ）が単なる「ｎのうち（多くとも）ｍを選択する」タイプの問題を有する場合、適切に働く。これは「書込み投票」応答、ならびに、投票者が優先順序で回答を示すことが予測され、この優先順序に従って問題が集計される場合の「比例タイプ」問題を除外する。（理論的には、比例タイプ問題は、選択の有効な並べ替えをそれぞれ単一のはい／いいえ応答にマッピングすることによって処理可能である。ただし、実際には、これは選択肢の数が非常に少ない場合でなければ実行不可能である。）［２］方式のそれほど重要でない２つの欠点は、これが投票データサイズをかなり拡大すること、および投票者の妥当性証明を必要とすることである。さらにこの証明は、投票データサイズをおよそ１０倍に拡大し、投票者のコンピュータ上で特定用途向けコードが実行されているものと想定するため、実用的な見地からは魅力がない。
【００１２】
本明細書のシャッフルプロトコルは、全体に初歩的な算術演算から構成される。したがって、実施するのは簡単であり、本明細書に記載された匿名の信用証明の応用にすぐにでも実施可能である。
【００１３】
（１．１  投票への応用）
即時に発生する投票への応用は、匿名を提供する通常の集計／混合センター方式を使用することである。この設定では、本明細書のプロトコルが重要な利点を提供する。これらはかなり効率的であり、混合センターを、無記名投票を暗号解除するのに必要な鍵の何らかの共有しておく機関から完全に独立させることができる。
【００１４】
ただし、新しいプロトコルのより価値ある刺激的な応用は、おそらく「匿名の信用証明」を作成するためのものである。ＤＳＡセットまたはDiffie-Hellman公開鍵によってのみ識別される認可済みグループのメンバは、グループの会員資格を認証し、かつ／または、自分の個人的なアイデンティティを明らかにすることなく、１回限りの方法で署名することができる。これにより、例外なく検証可能であるが、集計のためにどんな特殊な「機関」セットも必要としない、投票問題の新たな解決策につながる。また、より良いプライバシーモデルを投票者に提供し、無記名投票を暗号化／暗号解除する必要がないため、集計を桁違いに速くする。実際には、無記名投票が投票集計センターで受け取られた後に暗号化された投票暗号テキストを混合する代わりに、投票者の信用証明は、選挙開始前に混合される。この混合は、「匿名認証」を達成するために、当然、投票者自身によって実行することができる（７．１項を参照のこと）。（混合は、機関セットによって実行することもできるため、しきい値秘密選挙（threshold privacy election）を実施するためのより効率的な手段を提供することに留意されたい。ここでも、無記名投票の暗号化／暗号解除は必要でない。）
【００１５】
（２  表記法）
以下では、特に明示的に述べていない限り、ｎは正の整数であり、ｐおよびｑは素の整数であることが公に知られる。算術演算はモジュールリングＺp（または時にはＺn）内で実行され、ｇ∈Ｚpは（素の）乗法順序ｑを有することになる。（したがって、自明的にはｑ｜（ｐ−１）である。）各証明プロトコルでは、Ｐは証明者（シャッフラ）でありＶは検証者（verifier）（監査者）となる。
【００１６】
離散対数の等式についてのChaum-Pedersen証明を想起する。Ｇ、Ｘ、Ｈ、Ｙ∈Ｚpの場合、これは  
ｌｏｇGＸ＝ｌｏｇHＹ            （１）  
の関係に関する認識の証明である。
【００１７】
これはゼロ知識であるとは知られていないが、公正な検証者のゼロ知識であると知られている。次の項では、これらのプロパティも備えたこのプロトコルの自然の多変数一般化が得られる。これらは、検証者がFiat-Shamirの発見的方法を介して実施される場合、主要な応用に十分である。（［５］および［２］を参照のこと。）
【００１８】
（定義１）上記のように、この証明の一例は以下によって示される。
ＣＰ（Ｇ，Ｘ，Ｈ，Ｙ）  
【００１９】
（定義２）固定された  
【００２０】
【数３】
2005524250.tif 000005
【００２１】
【数４】
2005524250.tif 000006
【００２２】
によって定義された<g>×<g>の２進演算子であるものとし、この場合はすべてｘ，ｙ∈<g>である。あるいは、すべてａ，ｂ∈Ｚpの場合、  
【００２３】
【数５】
2005524250.tif 000007
【００２４】
である。加算および乗算に使用される規則に従い、以下の表記法も使用する。  
【００２５】
【数６】
2005524250.tif 000008
【００２６】
この演算を、対数乗算底ｇと呼ぶ。
【００２７】
上記定義における各表記法では、状況から値が明らかな場合、添え字ｇを省略することができる。  
【００２８】
（注釈１）以下に留意されたい。  
【００２９】
【数７】
2005524250.tif 000009
【００３０】
以下のよく知られた結果の集まりは、本明細書の以下の部分で頻繁に使用されることになるので、留意されたい。  
【００３１】
（補助定理１）ｆ（ｘ）∈Ｚg［ｘ］を次数ｄの多項式とする。すると、多くともｄ個の値、ｚ1，．．．，ｚd∈Ｚpとなり、その結果ｆ（ｚi）＝０となる。  
【００３２】
（推論１）ｆ（ｘ），ｇ（ｘ）∈Ｚg［ｘ］を、ｆ≠ｇで多くとも次数ｄの、最高次の係数が１に等しい２つの多項式とする。そこで多くともｄ−１個の値、ｚ1，．．．，ｚd-1∈Ｚgとなり、その結果ｆ（ｚi）＝ｇ（ｚi）となる。  
【００３３】
（推論２）ｆ（ｘ），ｇ（ｘ）∈Ｚg［ｘ］を、ｆ≠ｇで多くとも次数ｄの、最高次の係数が１に等しい２つの多項式とする。ｔ∈RＺq（ｔはＺqから無作為に選択される）の場合、以下のようになる。  
【００３４】
【数８】
2005524250.tif 000010
【００３５】
（推論３）ｆ（ｘ），ｇ（ｘ）∈Ｚg［ｘ］を、多くとも次数ｄの、任意の２つの多項式とする。そこで、あらゆる定数Ｒ≠０について、多くともｄ個の値、ｚ1（Ｒ），．．．，ｚd（Ｒ）となり、その結果ｆ（ｚi（Ｒ））＝Ｒｇ（ｚi（Ｒ））となる。  
【００３６】
（定義３）ｆ（ｘ）をＺg［ｘ］内の多項式とする。ｆのすべての根の（順不同の）セットをＸfで示す。  
【００３７】
【数９】
2005524250.tif 000011
【００３８】
（定義４）Λ⊂Ｚq、およびＲ∈Ｚqの場合、以下のようになる。  
【００３９】
【数１０】
2005524250.tif 000012
【００４０】
（推論４）ｆ（ｘ），ｇ（ｘ）∈Ｚg［ｘ］を、多くとも次数ｄの、任意の２つの多項式とする。定数Ｒ≠０、γ≠０、δ≠０を固定する。ｔ∈RＺqの場合、以下のようになる。  
【００４１】
【数１１】
2005524250.tif 000013
【００４２】
（補助定理２）
【００４３】
【数１２】
2005524250.tif 000014
【００４４】
を、Ｚqを介した標準のｋ次元のベクトル空間とし、  
【００４５】
【数１３】
2005524250.tif 000015
【００４６】
ｖ≠０およびａ∈Ｚqを固定する。  
【００４７】
【数１４】
2005524250.tif 000016
【００４８】
が無作為に選択されると、次のようになる。
【００４９】
【数１５】
2005524250.tif 000017
【００５０】
（３  反復対数乗算の証明）
本項の以下の部分では、すべての対数乗算が固定要素ｇに関して計算されることになるため、表記法での添え字は省略する。以下の問題は、後で登場するシャッフルプロトコルにとって基本的なものである。
【００５１】
（反復対数乗算問題）２つのシーケンス
【００５２】
【数１６】
2005524250.tif 000018
【００５３】
は、公的に知られている。証明者Ｐはすべてのｉについてｕi＝ｌｏｇgＸiおよびｖi＝ｌｏｇgＹiであることを知っているが、検証者Ｖは知らない。Ｐは、秘密対数ｕiおよびｖiに関してどんな情報も明らかにすることなく、関係
【００５４】
【数１７】
2005524250.tif 000019
【００５５】
をＶに確信させる必要がある。
【００５６】
本明細書で与えられるプロトコルは、精密には、第２項の始めで論じたChaum-Pedersenプロトコルの、より高次元の一般化である。実際は、ｋ＝２の場合に、プロトコルが厳密にChaum-Pedersenプロトコルであることがわかる。提示は、問題例を
Ｘi≠１，Ｙi≠１  ∀１≦ｉ≦ｋ            （６）
の場合に限定することによって、かなり簡略化される。明らかなことには、これら不等式のいずれかが保持されない場合、検査では数式（５）が保持されるか否かがわかならいため、証明を構成する意味がなくなる。（Ｘi＝１の場合、ｘi＝０であるため、何らかのｊでＹj＝１の場合およびその場合に限り、数式（５）が保持される。同様に、ＸおよびＹの役割が確保される。）
【００５７】
（反復対数乗算証明プロトコル（ＩＬＭＰＰ））
１．Ｐは、Ｚqからランダムに独立して、ｋ−１要素、θ1，．．．θk-1を秘密に生成する。次にＰは、
【００５８】
【数１８】
2005524250.tif 000020
【００５９】
を計算し、Ｖに対してシーケンスＡ1，．．．，Ａkを明らかにする。  
【００６０】
２．Ｖは、ランダムチャレンジ（challenge）、γ∈Ｚqを生成し、これをＰに対して明らかにする。  
【００６１】
３．Ｐは、
【００６２】
【数１９】
2005524250.tif 000021
【００６３】
を満たすＺqのｋ−１要素、ｒ1，．．．，ｒk-1を計算し、Ｖに対してシーケンスｒ1，．．．，ｒk-1を明らかにする（以下の完全性の証明で、これらの値がどのように計算されるかを示す）。  
【００６４】
４．Ｖは、数式（８）内のすべての等式が保持されている場合、およびその場合に限り、証明を受け入れる。
【００６５】
（定理１）ＩＬＭＰＰは、特別の公正な検証者ゼロ知識である、数式（５）の関係に関する知識の３ムーブ、パブリックコイン（three-move,public coin）証明である。証明の構成に必要な累乗の数はｋであり、それを検証するのに必要な累乗の数は２ｋである。Ｖがチャレンジをランダムに生成した場合、偽作の証明である確率は１／ｑである。  
【００６６】
（注釈２）証明の構成において、同じベースｇに対してすべての累乗が実行可能であるため、固定されたベースアルゴリズムが使用できることに留意されたい（［６］の６２３ページを参照のこと）。
【００６７】
（証明）証明は、明らかに３ムーブおよびパブリックコインである。証明の構成における累乗カウントは、２ｋ−２であるものと見られるが、実際にはｋ累乗のみで構成することができる。これは、Ｐが対数ｘiおよびｙiを知っており、すべての２≦ｉ≦ｋ−１の場合に、Ａiを
【００６８】
【数２０】
2005524250.tif 000022
【００６９】
として計算できるからである。
【００７０】
（完全性）
完全性とは、任意の
【００７１】
【数２１】
2005524250.tif 000023
【００７２】
およびγが与えられた場合、Ｐは常に、数式（８）の等式のシステムを満たす
【００７３】
【数２２】
2005524250.tif 000024
【００７４】
を見つけることができることを意味する。この例で確かめるには、数式（８）の両側のｌｏｇgを取り、１≦ｉ≦ｋ−１の場合に
【００７５】
【数２３】
2005524250.tif 000025
【００７６】
と設定する。  
【００７７】
【数２４】
2005524250.tif 000026
【００７８】
の場合、以下のようにＺqの線形式のｋ×（ｋ−１）システムが得られる。  
【００７９】
【数２５】
2005524250.tif 000027
【００８０】
（ｋ−１）×（ｋ−１）サブシステムである
【００８１】
【数２６】
2005524250.tif 000028
【００８２】
は、その行列式が、前提（６）によって非ゼロである、
【００８３】
【数２７】
2005524250.tif 000029
【００８４】
であるため、非特異である。したがって、これはいつでも
【００８５】
【数２８】
2005524250.tif 000030
【００８６】
として解くことができる。実際に、解は以下のようになる。  
【００８７】
【数２９】
2005524250.tif 000031
【００８８】
ただし、問題の仮説の下では、数式（１０）は実際に数式（９）を暗示する。これは
【００８９】
【数３０】
2005524250.tif 000032
【００９０】
【数３１】
2005524250.tif 000033
【００９１】
であることにより、数式（１０）の左側にある部分行列が非特異であるという事実と組み合わせて、数式（１２）のｋ×ｋ行列の第１列ベクトルが、残りのｋ−１列ベクトルの線形組合せでなければならないことを意味する。
【００９２】
（健全性）
数式（１２）の左側にある行列の第１列ベクトルが、残りのｋ−１列ベクトルの線形組合せでない場合、数式（９）が保持される、γ∈Ｚqのうちの多くとも１つの値が存在可能である。したがって、γがランダムに選択される場合、ＰがＶを納得させるｒ1，．．．，ｒk-1を生成できるチャンスがｑ内に多くとも１ある。
【００９３】
（特別の公正な検証者のゼロ知識）
ランダムγおよびランダム
【００９４】
【数３２】
2005524250.tif 000034
【００９５】
の場合、および
【００９６】
【数３３】
2005524250.tif 000035
【００９７】
の場合、３部の
【００９８】
【数３４】
2005524250.tif 000036
【００９９】
は受諾の会話（accepting conversation）であるため、公正な検証者のゼロ知識は保持される。したがって、ランダムで独立したγおよびｒiを生成し、数式（１３）のように
【０１００】
【数３５】
2005524250.tif 000037
【０１０１】
を設定することによってシミュレーションが構成される。
【０１０２】
そのようにして生成された
【０１０３】
【数３６】
2005524250.tif 000038
【０１０４】
に関する分布は、ここでも数式（１２）の行列の第１列ベクトルが残りの列ベクトルの固定された線形組合せであるため、数式（７）に従って生成されたものと同一であることが容易にわかる。したがって、Ｖが公正であれば、シミュレーションは完全である。チャレンジγは自由に選択することができるため、特別の公正な検証者のゼロ知識も有する。
【０１０５】
（注釈３）数式（１１）の
【０１０６】
【数３７】
2005524250.tif 000039
【０１０７】
の解は、形式上、以下のように表すこともできる。  
【０１０８】
【数３８】
2005524250.tif 000040
【０１０９】
ただし、ｙjのいくつかが０の場合、これは機能しない。数式（１１）の場合、この問題は前提（６）によって避けられた。もちろん、解の主要部分は、すべての１≦ｉ≦ｋ−１の場合ｙi≠０であるという前提の下に首尾よく設定されているだけであり、ｒiに関する式の選択は、前提の形式との一貫性を保つだけでよい。
【０１１０】
（注釈４）ｋ＝２の場合のチェックは読者にゆだねるものであり、ＩＬＭＰＰは、よく知られたChaum-Pedersenプロトコルにまで厳密に縮小される。これを実行する場合、注釈１の数式（２）を想起されるとよい。
【０１１１】
（注釈５）特別な健全性
Ｐがｓ＝ｌｏｇGＸ＝ｌｏｇHＹを知っていることを証明するChaum-Pedersenプロトコルの場合と同様に、ＩＬＭＰＰはＰがｓ1，．．．，ｓkを知っていることを証明し、その結果、ｌｏｇGＸi＝ｌｏｇHＹiおよび
【０１１２】
【数３９】
2005524250.tif 000041
【０１１３】
となる。これは、２つの受諾の会話
【０１１４】
【数４０】
2005524250.tif 000042
【０１１５】
から、同じ第１のムーブおよびγ≠γ’の場合、
【０１１６】
【数４１】
2005524250.tif 000043
【０１１７】
を満たす証拠
【０１１８】
【数４２】
2005524250.tif 000044
【０１１９】
を抽出できることから明らかである。
【０１２０】
ｗ＝γ−γ’≠０であるため、これは、すべての１≦ｉ≦ｋ−１の場合にｐi≠０に従う。したがって、問題のステートメントにわずかな修正を適切に加えると、特別な健全性を満たす。
【０１２１】
（４  単純なｋシャッフル）
発明者が構成する第１のシャッフル証明プロトコルは、限定的な条件セットを必要とする。これは２つの理由で有用である。第１にこれは、後で登場する、より一般的なシャッフル証明プロトコルの基本的な構成ブロックである。偶然にも、これは第２の重要な目的にもかなう。この証明の単一の例は、特定の並べ替えを本質的に「コミット」するように構成することができる。これは、シャッフルが、投票応用例での場合と同様、ElGamalペアをシャッフルする際に厳密に要求されるものである、Ｚp要素の組で実行される必要がある場合に重要である。
【０１２２】
（定義５）Ｚpのｋ要素の２つのシーケンス、Ｘ1，．．．，ＸkおよびＹ1，．．．，Ｙk、ならびに２つの追加要素ＣおよびＤが公に知られていると仮定する。さらに、証明者Ｐはｘi＝ｌｏｇgＸi、ｙi＝ｌｏｇgＹi、ｃ＝ｌｏｇgＣ、およびｄ＝ｌｏｇgＤを知っているが、これらの値はすべて検証者Ｖには知られていないとも仮定する。Ｐは、ｘi、ｙi、π、ｃ、またはｄに関するどんな情報も明らかにすることなく、すべての１≦ｉ≦ｋの場合に、
【０１２３】
【数４３】
2005524250.tif 000045
【０１２４】
のプロパティを備えた、何らかの並べ替え、π∈ΣkがあることをＶに納得させる必要がある。この問題を、単純なｋシャッフル問題と呼ぶ。
【０１２５】
（注釈６）この項および本明細書の残りの部分では、すべてのシャッフル構造において、
１．ｉ≠ｊの場合に、ｘi≠ｘj（したがって、もちろんｉ≠ｊの場合に、ｙi≠ｙj）
２．すべての１≦ｉ≦ｋの場合に、ｘi≠１
というように、前提を簡略化する。
【０１２６】
これらの特殊な場合を処理するための明らかな方法がある。さらに、実際には、要素が通常はランダムであるため、それらは「本質的に決して発生しない」。
【０１２７】
前項のプロトコルは、推論２と組み合わせると、かなりわかりやすい方法でこの問題を解くのに必要なツールを提供する。
【０１２８】
（単純なｋシャッフル証明プロトコル）
１．υはランダムなｔ∈Ｚqを生成し、これをチャレンジとしてＰに与える。  
２．ρおよびυは公に、Ｕ＝Ｄt＝ｇdt、Ｗ＝Ｃt＝ｇct、
【０１２９】
【数４４】
2005524250.tif 000046
【０１３０】
および
【０１３１】
【数４５】
2005524250.tif 000047
【０１３２】
を計算する。
【０１３３】
３．ρおよびυは、２つの長さｋベクトルについて、以下のようにＩＬＭＰＰを実行する。  
【０１３４】
【数４６】
2005524250.tif 000048
【０１３５】
υがこのＩＬＭＰＰを受け入れた場合、およびその場合に限り、プロトコルは成功する（υが証明を受け入れる）。
【０１３６】
（定理２）単純なｋシャッフル証明プロトコルは、数式（１５）の関係に関する知識の４ムーブ、パブリックコイン証明である。これは特別な健全性を満たすものであり、特別の公正な検証者のゼロ知識である。証明を構成するのに必要な累乗の数は２ｋであり、これを検証するのに必要な累乗の数は４ｋである。
【０１３７】
Ｖがチャレンジをランダムに生成する場合、偽作の証明である確率は、
(k-1)/q+(q-k+1)/q2 = (qk-q+q-k+1)/q2<k/q
より小さいかまたは等しい。
【０１３８】
（注釈７）注釈２の観察もこのケースにあてはまる。
【０１３９】
（証明）必要なすべてのプロパティは、前項の結果のすぐ後に続く。（特別な健全性は注釈５から論じることができる）。偽の証明は、２つの条件でのみ生成可能である。  
【０１４０】
１．チャレンジｔが、以下の場合の特別な値のうちの１つである。  
【０１４１】
【数４７】
2005524250.tif 000049
【０１４２】
２．チャレンジｔが上記１の特別な値のうちの１つでなく、ＩＬＭＰＰが偽せである。推論２によれば、前項の結果による１の確率は多くとも（ｋ−１）ｑであり、２の確率は（ｑ−ｋ＋１）／ｑ2である。
【０１４３】
（４．１  複雑さの向上）
単純なｋシャッフルプロトコルのサイズおよび複雑さの両方を、２倍に向上することができる。推論２を使用する代わりに、推論４を使用する。直感的に、数式（１６）におけるＤのｋ個のコピーおよびＣのｋ個のコピーを、それぞれ単一の項目
【０１４４】
【数４８】
2005524250.tif 000050
【０１４５】
に置き換えたくなる。残念ながら、そうするとプロトコルのゼロ知識プロパティを壊してしまう。そこで代わりに、プロトコルを次のように修正する。
【０１４６】
（単純なｋシャッフル証明プロトコルＩＩ）
１．ρは、Ｚqからβを、Ｚq−｛０｝からγを、ランダムに独立して生成し、
Ｂ＝ｇβ            （１７）
Ｔ＝ｇγ
を計算して、Ｖに対してＢおよびＴを明らかにする。  
【０１４７】
２．υはＺqからランダムλを生成し、これをρに対して明らかにする。  
【０１４８】
３．ρは、
【０１４９】
【数４９】
2005524250.tif 000051
【０１５０】
によってｓを計算し、υに対してｓを明らかにする。  
【０１５１】
４．υはランダムなｔ∈Ｚqを生成し、これをチャレンジとしてＰに与える。  
【０１５２】
５．ρおよびυは公に、Ｕ＝Ｄt＝ｇdt、Ｗ＝Ｃt＝ｇct、
【０１５３】
【数５０】
2005524250.tif 000052
【０１５４】
および
【０１５５】
【数５１】
2005524250.tif 000053
【０１５６】
を計算する。  
【０１５７】
６．ρはＺqから、ランダムに独立して、ｋ個の要素θ1，．．．，θkを秘密に生成する。次にρは、
【０１５８】
【数５２】
2005524250.tif 000054
【０１５９】
を計算し、υに対してシーケンスＡ1，．．．，Ａk+1を明らかにする。  
【０１６０】
７．υはランダムなチャレンジγ∈Ｚqを、を生成し、これをρに対して明らかにする。  
【０１６１】
８．ρは、
【０１６２】
【数５３】
2005524250.tif 000055
【０１６３】
を満たすＺqのｋ個の要素、ｒ1，．．．，ｒkを計算し、シーケンスｒ1，．．．，ｒkをυに対して明らかにする。  
【０１６４】
９．υは数式（２０）のすべての式が保持されている場合、およびその場合に限り、証明を受け入れる。
【０１６５】
（定理３）単純なｋシャッフル証明プロトコルＩＩは、数式（１５）の関係に関する知識の５ムーブ、パブリックコイン証明である。これは特別な健全性を満たすものであり、特別の公正な検証者のゼロ知識である。証明を構成するのに必要な累乗の数はｋ＋４であり、これを検証するのに必要な累乗の数は２ｋ＋２である。
【０１６６】
υがチャレンジをランダムに生成する場合、偽作の証明である確率は、依然として
(k-1)/q+(q-k+1)/q2 = (qk-q+q-k+1)/q2<k/q
より小さいかまたは等しい。
【０１６７】
（証明概略）すべての論拠は、プロパティごとに、オリジナルプロトコルの際に構成された論拠と非常によく似ている。主な違いは、推論２ではなく推論４に訴える点である。  
【０１６８】
（定義６）単純なｋシャッフルプロトコルＩＩの一例を
【０１６９】
【数５４】
2005524250.tif 000056
【０１７０】
によって示し、ここで
【０１７１】
【数５５】
2005524250.tif 000057
【０１７２】
ＣおよびＤは定義５と同じである。
【０１７３】
（５  一般的なｋシャッフル）
単純なｋシャッフルプロトコルの明らかな制限は、シャッフラＰがすべてのオリジナルの指数ｘ1，．．．，ｘkおよびｙ1，．．．，ｙkを知っていなければならないことである。多くの応用例では、これがあてはまらない。本項の目的は、この制限をなくすことである。
【０１７４】
（一般的なｋシャッフルの問題）Ｚpのｋ個の要素の２つのシーケンスＸ1，．．．，ＸkおよびＹ1，．．．，Ｙkは、公に知られている。さらに、定数ｃ、ｄ∈ＺqはＰにしか知られていないが、コミットメントＣ＝ｇcおよびＤ＝ｇdは公にされる。Ｐは、すべての１≦ｉ≦ｋの場合に、いくつかの並べ替えπ∈Σkが
【０１７５】
【数５６】
2005524250.tif 000058
【０１７６】
と共に存在することを、π、ｃまたはｄに関するどんな情報も明らかにすることなく、Ｖに納得させる必要がある。
【０１７７】
（一般的なｋシャッフル証明プロトコル）
（提示のために、ｄ＝１の場合について考えてみる。一般的なケースは、グループ生成者をｇからＣに変更し、置換ｃ＝ｃ／ｄを実行するだけで、このケースに縮小できる。）
【０１７８】
１．１≦ｉ≦ｋの場合、ρはａi、ｂi、ｕi、およびｗiをＺqからランダムに独立して生成し、以下を計算する。  
【０１７９】
【数５７】
2005524250.tif 000059
【０１８０】
さらにρは、Ｚq−｛０｝からγを生成し、Ｚqからｚ0、ｚ1もランダムに独立して生成し、
【０１８１】
【数５８】
2005524250.tif 000060
【０１８２】
を計算して、１≦ｉ≦ｋの場合、
【０１８３】
【数５９】
2005524250.tif 000061
【０１８４】
を計算して、最後に
【０１８５】
【数６０】
2005524250.tif 000062
【０１８６】
を計算する。次にρは、順序付けられたシーケンスＡi、Ｂi、Ｃi、Ｕi、およびＷiならびにＸ0、Ｙ0、およびΛを、υに対して明らかにする。  
【０１８７】
２．１≦ｉ≦ｋの場合、ＶはＺq−｛０｝からランダムに独立してｅiを選択し、シーケンスをρに戻す。  
【０１８８】
３．Ｐは、１≦ｉ≦ｋの場合
【０１８９】
【数６１】
2005524250.tif 000063
【０１９０】
を計算し、これらをυに対して明らかにする。  
【０１９１】
４．υはｔ∈Ｚq−｛０｝を生成し、これをチャレンジとしてρに戻す。  
【０１９２】
５．１≦ｉ≦ｋの場合、ρは秘密に以下の指数を計算する。  
ｒi＝ａi＋ｔｅiｂi            （２７）
ｓi＝γrπ(i)
【０１９３】
６．次にρおよびυは、単純なｋシャッフル
【０１９４】
【数６２】
2005524250.tif 000064
【０１９５】
を実行するが、ここでは以下の通りである。  
【０１９６】
【数６３】
2005524250.tif 000065
【０１９７】
（ρは、証明を構成するためにＲiおよびＳiを明示的に計算する必要はないが、Ｖは、
【０１９８】
【数６４】
2005524250.tif 000066
【０１９９】
としてＲiおよびＳiを計算することができることに留意されたい。したがってこの証明プロトコルは、ρがｋ＋４の累乗を計算し、υが４ｋ＋２の累乗を計算するように要求する。）
【０２００】
７．ρは、以下の指数を明らかにする。  
ρi＝ｕi＋ｒi−ａi            （２９）
σi＝ｗi＋ｓi−ｃi
【０２０１】
８．υは、
【０２０２】
【数６５】
2005524250.tif 000067
【０２０３】
をチェックし、
【０２０４】
【数６６】
2005524250.tif 000068
【０２０５】
を評価する。  
【０２０６】
９．ρは、
Ｇ0＝Ｇγ            （３２）
Ｇ1＝（Ｚ1Ｇ0）c
を計算し、υと共に、２つのChaum-Pedersen証明、ＣＰ（ｇ，Γ，Ｇ，Ｇ0）およびＣＰ（ｇ，Ｃ，Ｚ1Ｇ0，Ｇ1）を実行する。（したがって、数式（３２）が保持されることをＶに対して証明している。）
【０２０７】
１０．υは最終的に、
【０２０８】
【数６７】
2005524250.tif 000069
【０２０９】
をチェックする。  
【０２１０】
１１．υは
（ａ）チェックしなければならないすべての式（ステップ８および１０）が条件を満たしている場合
（ｂ）υがステップ６の単純なシャッフル証明を受け入れた場合
（ｃ）υがステップ９の両方のChaum-Pedersen証明を受け入れた場合に、
およびこれらの場合にのみ、証明を受け入れる。
【０２１１】
（６  複数機関投票アプリケーション）
従来の投票アプリケーション用の設定の多くが、［２］に示されている。票は
【０２１２】
【数６８】
2005524250.tif 000070
【０２１３】
の形のElGamalペア（またはより多くのデータが必要な場合はこれらのペアのシーケンス）として提出されるが、ここでｍは投票者の選択肢のいくつかの標準的な符号化であり、αiは投票者によって秘密に生成され、ｈはディーラーなしの秘密の共用スキーム（［７］）を介して構成された公開パラメータである。投票所が閉じる（投票が完了する）と、機関の独立した集まりが無記名投票を順番にシャッフルする。各シャッフルは、
【０２１４】
【数６９】
2005524250.tif 000071
【０２１５】
として構成され、ここでｒiはＺqからランダムに選択され、以下のようになる。
【０２１６】
【数７０】
2005524250.tif 000072
【０２１７】
最終シャッフルの出力時に、暗号化された無記名投票の最後の集まりがしきい値方式に従って暗号解除され、明確なテキスト投票は通常の選挙規則によって人の見ている前で集計される。
【０２１８】
順次シャッフルに参加する機関の数は任意であってよく、選挙秘密鍵の割り当てを保持している機関とはまったく別であってよい。それらのそれぞれの並べ替えが完全に任意であるため、すべてのシャッフル機関が結託した場合、最終的に暗号解除される無記名投票の順序は、提出された無記名投票のオリジナルの順序とのみ一致することができる。
【０２１９】
各シャッフルの形は第５項で論じたシャッフルとは異なるが、証明プロトコルはわずかな修正によって構成することができる。詳細については、以下のサブセクションで示す。
【０２２０】
（６．１  ElGamalペアのシャッフル）
１．１≦ｉ≦ｋの場合、ρはａi、ｂi、ｕi、およびｗiをＺqからランダムに独立して生成し、以下を計算する。
【０２２１】
【数７１】
2005524250.tif 000073
【０２２２】
さらにρは、Ｚq−｛０｝からγを生成し、Ｚqからｘ0、ｙ0、およびｔ0もランダムに独立して生成し、
【０２２３】
【数７２】
2005524250.tif 000074
【０２２４】
を計算して、１≦ｉ≦ｋの場合、
【０２２５】
【数７３】
2005524250.tif 000075
【０２２６】
を計算して、最後に
【０２２７】
【数７４】
2005524250.tif 000076
【０２２８】
を計算する。次にρは、順序付けられたシーケンスＡi、Ｂi、Ｃi、Ｕi、およびＷiならびにＸ0、Ｙ0、およびΛを、υに対して明らかにする。  
【０２２９】
２．１≦ｉ≦ｋの場合、υはＺq−｛０｝からランダムに独立してｅiを選択し、シーケンスをＰに戻す。  
【０２３０】
３．ρは、１≦ｉ≦ｋの場合
【０２３１】
【数７５】
2005524250.tif 000077
【０２３２】
を計算し、これらをυに対して明らかにする。  
【０２３３】
４．υはｃ∈Ｚq−｛０｝を生成し、これをチャレンジとしてρに戻す。  
【０２３４】
５．１≦ｉ≦ｋの場合、ρは秘密に以下の指数を計算する。  
ｒi＝ａi＋ｃｅiｂi            （４０）
ｓi＝γrπ(i)
【０２３５】
６．次にρおよびυは、単純なｋシャッフル
【０２３６】
【数７６】
2005524250.tif 000078
【０２３７】
を実行するが、ここでは以下の通りである。  
【０２３８】
【数７７】
2005524250.tif 000079
【０２３９】
（ρは、証明を構成するためにＲiおよびＳiを明示的に計算する必要はないが、υは、
【０２４０】
【数７８】
2005524250.tif 000080
【０２４１】
としてＲiおよびＳiを計算することができることに留意されたい。したがってこの証明プロトコルは、Ｐがｋ＋４の累乗を計算し、Ｖが４ｋ＋２の累乗を計算するように要求する。）
【０２４２】
７．ρは、以下の指数を明らかにする。
【０２４３】
ρi＝ｕi＋ｒi−ａi            （４２）
σi＝ｗi＋ｓi−ｃi
【０２４４】
８．υは、
【０２４５】
【数７９】
2005524250.tif 000081
【０２４６】
をチェックし、
【０２４７】
【数８０】
2005524250.tif 000082
【０２４８】
を評価する。  
【０２４９】
９．ρは、
Ｇ0＝Ｇγ            （４５）
Ｈ0＝Ｈγ
を計算し、υと共に、２つのChaum-Pedersen証明、ＣＰ（ｇ，Γ，Ｇ，Ｇ0）およびＣＰ（ｇ，Γ，Ｈ，Ｈ0）を実行する。（したがって、数式（４５）が保持されることをυに対して証明している。）
【０２５０】
１０．ＰおよびＶは、
【０２５１】
【数８１】
2005524250.tif 000083
【０２５２】
を計算する。  
【０２５３】
１１．Ｐは、
【０２５４】
【数８２】
2005524250.tif 000084
【０２５５】
を計算し、υに対してこれを明らかにする。  
【０２５６】
１２．υは最終的に、
【０２５７】
【数８３】
2005524250.tif 000085
【０２５８】
をチェックする。  
【０２５９】
１３．υは
（ａ）チェックしなければならないすべての式（ステップ８および１２）が条件を満たしている場合
（ｂ）Ｖがステップ６の単純なシャッフル証明を受け入れた場合
（ｃ）Ｖがステップ９の両方のChaum-Pedersen証明を受け入れた場合に、
およびこれらの場合にのみ、証明を受け入れる。
【０２６０】
（６．２  １パス集計）
標準のミックスネットの実施では、以下の２つの別個の段階を行うものと想定される。
【０２６１】
（シャッフル（または混合））暗号化された無記名投票のセットが混合される。これは、暗号化された（および繰り返しシャッフルされた）無記名投票ボックス全体が、混合段階が十分な回数実施されるまで、１つの機関から別の機関へ順番にパスされなければならないことを意味する。より精密に言えば、Ａ1，．．．，Ａnを、シャッフルのシーケンス、または通常は機関と呼ばれる混合エンティティとする。Ｂを暗号化された無記名投票のシーケンスとする。順次に、各Ａiが以下のオペレーションを実施する。
【０２６２】
１．Ａiが、Ａi-1から、必要なすべての認証および妥当性の証明と共に、
Ｂ＝（（Ｘ1，Ｙ1），．．．，（Ｘk，Ｙk））
を受け取る。（ｉ＝１の場合、Ａ1は集票センターから直接Ｂを受け取る。）
【０２６３】
２．Ａiが、すべての必要な認証チェックおよび妥当性（証明）検証を実行する。  
【０２６４】
３．ステップ２でのチェックのうちいずれかが不合格の場合、集計は打切られるか、または可能であれば再開される。そうでなければＡiは、数式（３４）および、第６．１項の対応する妥当性証明Ｐiに従って、
【０２６５】
【数８４】
2005524250.tif 000086
【０２６６】
を計算する。（典型的には、これはプロトコルの非対話型バージョンである。）
【０２６７】
４．Ａiは、
【０２６８】
【数８５】
2005524250.tif 000087
【０２６９】
をＢと改名し、Ｐiおよび任意の他の必須の認証または妥当性検査と共に、ＢをＡi+1に送る。ｉ＝ｎの場合、混合は終了し、集計は暗号解除段階に進む。
【０２７０】
（暗号解除）シャッフル（混合）の後、結果的に生じた無記名投票のセットはすべて、通常はｈで示される選挙公開鍵に暗号化される。これらの無記名投票を暗号解除するために、各機関はここで暗号解除シェアに寄与しなければならない。これは、以下のように実施される。
【０２７１】
１．
Ｂ＝（（Ｘ1，Ｙ1），．．．，（Ｘk，Ｙk））
を、最終混合機関Ａnによって出力された暗号化無記名投票のセットとし、ＳD＝｛Ｄ1，．．．，Ｄt｝を、暗号解除に参加している暗号解除機関のサブセットとする。（値ｔは、選挙公開鍵ｈが作成されたときに使用されたしきい値によって決定される。［７］を参照のこと。）
【０２７２】
２．それぞれの１≦ｊ≦ｔの場合、並行して、
（ａ）Ｄjは、シーケンスＸ1，．．．，Ｘkを、その妥当性の適切な認証と共に受け取る。  
（ｂ）ステップ２ａで提供された認証のチェックが不合格である場合、Ｄjは暗号解除を中止しなければならない。そうでない場合は、それぞれの１≦ｉ≦ｋの場合、Ｄjは
【０２７３】
【数８６】
2005524250.tif 000088
【０２７４】
を計算し、上式で、ｓjはＤjの暗号解除シェアであり、ｚ（ｊ，ＳD）は公開で計算可能な一定の乗数である。（［７］を参照のこと。）Ｄjは、数式（４９）に関する妥当性のChaum-Pedersen証明Ｃijも生成する。  
（ｃ）ＤはすべてのＺijおよびＣijを集計センターに戻す。  
【０２７５】
３．集計センターで受け取ったすべてのＣijが有効であると想定すると、明確なテキスト無記名投票のセットは、以下のように計算される。
【０２７６】
【数８７】
2005524250.tif 000089
【０２７７】
４．選挙得票は、どんな選挙の場合とも同様に、最終的にＭiを計算することによって計算される。
【０２７８】
暗号解除機関（またはまさに単なるそれの何らかのサブセット）のセットＳDが、シャッフル機関のセットに含まれる場合（実際にはこれがほぼいつもの場合）、この手順の欠点は、両方のセットにある各機関が２つの別の通信を受け取る必要があり、それらがそれぞれ非常に大規模な可能性があるということである。機関が低速の通信リンクによって接続されている場合、この欠点は特に深刻である。
【０２７９】
発明者は、一部またはすべての暗号解除を、混合と同時に実施することが可能なことに気付いた。これは、シャッフル段階中に、ＳDのメンバであるそれらシャッフル機関それぞれについて、単にステップ３のシャッフルとステップ２の暗号解除とを組み合わせることによって実施される。ＳDのメンバでないそれらシャッフル機関は、未修正のステップに従うことができる。
【０２８０】
したがって、ＡjがＳDのメンバであれば、シャッフルステップ４ではＢをＡj+1に送るだけでなく、Ａjは
Ｂ＝（（Ｘ1，Ｙ1），．．．，（Ｘk，Ｙk））
および
Ｚ＝（（Ｚ1j，Ｃ1j），．．．，（Ｚkj，Ｃkj））
の両方を送り、ここでＺijおよびＣijは上記の通りである。さらに、Ａj+1はＢをそのシャッフルへの入力として使用する代わりに、
Ｂ＝（（Ｘ1，Ｙ1／Ｚ1j），．．．，（Ｘk，Ｙk／Ｚkj））
を使用しなければならない。
【０２８１】
この方法では、通常のケースのように、すべての暗号解除機関がシャッフル機関でもある場合、最終出力は暗号解除された無記名投票のセットとなるため、別々の暗号解除段階が不要になる。ｔ0＜ｔの暗号解除機関のみがシャッフル機関でもある場合、最終のシャッフルされた無記名投票箱は、残りのｔ−ｔ0暗号解除機関の間で共用される公開鍵で暗号化された要素で構成されることになる。したがって、この場合は依然として暗号解除段階が必要であるが、必要な通信の量は対応する量だけ減じられる。
【０２８２】
（７  ＤＳＡ公開鍵のｋシャッフル）
一般的なｋシャッフルは、ＤＳＡまたはDiffie-Hellman公開鍵のセットの検証可能な並べ替えに申し分なく好適である。これは、計算上はオリジナルセットにリンク不可能であるが、同じ秘密鍵セットを検証可能に表す、ＤＳＡ公開鍵の新しいセットが生成されることを意味する。これは、秘密鍵のオリジナルグループの整合性を保護しながらも、認証済みの鍵セットを匿名扱いにしたいという場合に、非常に役立つものであり、選挙の設定がまさしくこうした例の１つである。
【０２８３】
本明細書ではこの技法の概略を示すだけであるが、読者には細部まで完全に明らかになるものとする。初期には、すべての公開鍵が（ｇ、Ｈ）、Ｈ＝ｇsの形であると想定され、ｇは何らかの固定生成者、ｓは秘密鍵である。すなわち、大雑把に言えば「すべての鍵は同じベースを使用する」。プロトコルは、以下のように進行する。
【０２８４】
１．シャッフラまたはミキサに、ｇおよび鍵Ｈiのリストが提示される。  
【０２８５】
２．シャッフラは、Ｃ＝ｇ、および
【０２８６】
【数８８】
2005524250.tif 000090
【０２８７】
（新しい公開鍵）を使用して、一般的なｋシャッフルを実行し、Fiat-Shamirの発見的方法を介して検証者のランダムなチャレンジを実施する。（すなわち、証明プロトコルの非対話型バージョンが実行される。）
【０２８８】
３．シャッフラは、証明の写し全体を「戻す」。  
【０２８９】
４．写しが、セットｇ＝Ｃ、および
【０２９０】
【数８９】
2005524250.tif 000091
【０２９１】
を検証すると想定する。共通のベースをＣに変更することにより
Ｈ＝ｇs  ⇔  Ｈ’＝Ｃs            （５１）
であるため、秘密鍵はすべて同じままである。
【０２９２】
（７．１  匿名の投票者）
投票アプリケーションでは、選挙の整合性のためには「誰が投票したか」を知らなければならないが、プライバシーのためには「どのように投票したか」を知ってはならないと、しばしば言われる。この項の技法は、新しい方法で、プライバシー／整合性のジレンマを解決するものである。「誰が投票したか」を知る代わりに、投票した人が許可された投票者セットのメンバであることだけを知る。したがって、以下のような投票解決策が残される。
【０２９３】
１．分散型信用集計方式を実施するために、鍵の共用が必要であるか。  
【０２９４】
２．投票者に対して、分散型信用集計に基づいた他の投票解決策の必要悪であるしきい値プライバシーではなく、計算プライバシーを保証する（しきい値数の機関が結託に同意した場合、すべての投票者の票を複合することができる）。  
【０２９５】
３．投票された無記名投票の暗号化または暗号解除が必要であるか。  
【０２９６】
もちろん、「２重投票」の問題に気をつけなければならないが、この項の技法は、以下のようにこれを処理するように簡単に修正される。
【０２９７】
ＡＶ−１．ステップ３では、この場合は秘密鍵ｓ0のうちの１つを知っている人である投票者（シャッフラ）が、ＤＳＡ署名方式を使用して、自分が投票した無記名投票にグループ生成者（またはベース）Ｃおよび鍵ペア
【０２９８】
【数９０】
2005524250.tif 000092
【０２９９】
で署名する。（
【０３００】
【数９１】
2005524250.tif 000093
【０３０１】
は、投票者に属する「シャッフル後」公開鍵である。投票者は、自分がシャッフルを実行したので、新しいシーケンスにおける自身の場所を知っている。さらに、シャッフルのプロパティが
【０３０２】
【数９２】
2005524250.tif 000094
【０３０３】
を保証するため、ｓ0は
【０３０４】
【数９３】
2005524250.tif 000095
【０３０５】
に対応する秘密鍵である。）
【０３０６】
ＡＶ−２．ステップ４では、シャッフル写しのチェックおよび無記名投票署名のチェックを想定し、投票センターは、単に許可された鍵のリストから
【０３０７】
【数９４】
2005524250.tif 000096
【０３０８】
を除去し、次の無記名投票要求を待って再度このプロセスを開始する。公開鍵の新しいリストはこれで小規模になり、投票者（シャッフラ）が第１の場所で複数の秘密鍵を知らない限り、新しい秘密鍵はまったく知らないことになり、再度投票することはできない。
【０３０９】
結果として生じる選挙プロトコルは、すべてのシャッフル写しおよび署名が維持されている場合、例外なく検証可能である。
【０３１０】
この選挙方式は、優れたプライバシー特性を提供する（各投票者の無記名投票の秘密性は、分散された機関セットによってではなく、投票者によって保護される）が、実施する上では潜在的な欠点がある。投票者（すなわち投票者のコンピュータ）と認証を目的とする集票サーバコンピュータの両方に必要な計算量が、投票者が標準的な公開鍵署名のみを計算しなければならない標準的な選挙プロトコルの場合よりもかなり多い。ただし、この追加計算が問題を発生させることが予測される場合、無記名投票が使用可能になる前に、選挙に先立って、同じ匿名扱いを実行することができる。
【０３１１】
これは、上記のステップＡＶ−１で無記名投票が署名されるのとまったく同様に匿名で署名される、証明書要求に応答して発行される標準のＰＫＩ証明書を発行することによって実施される。もちろん、これらの証明書要求には個人情報の識別は含まれないが、これらは最も重要なことに、それ以外は完全に標準であって、投票者が対応する秘密権を有する標準の公開鍵を含む。投票時、無記名投票にはこの通常の秘密鍵で署名することができる。この戦略では、匿名の証明書を再使用することができる。したがって、匿名署名の計算コストが多くの選挙で償却できる。
【０３１２】
（８  組のｋシャッフル）
第５項では、生成された単純なシャッフルが、証明可能な並べ替えを本質的に「凍結させた」ことが明らかである。これにより、前項を＜ｇ＞のｋ個のｌ組要素、またはｋ個のｌ組のElGamalペアをシャッフルさせるように拡張する方法が容易にわかる。ｋ個のｌ組のシーケンスをｋ×ｌアレイと考えると、単一の単純なｋシャッフルは、すべての列が同じ並べ替えに従って並べ替えられたことを証明するように働くことができる。精密には、これは、一般的なｋシャッフルプロトコルおよびElGamalシャッフルプロトコルの両方で、同じ値、Ａi、Ｂi、Ｃi、およびＤiがすべての列で使用されることを意味する。（一般的なｋシャッフルではすべての列に同じ値ｔを使用することが可能であり、ElGamalシャッフルではすべての列に同じ値ｃを使用すること可能であるが、これは必須ではない。）
【０３１３】
（８．１  共通ベースなしのＤＳＡ鍵シャッフル）
この項の考えによれば、第７項のＤＳＡ鍵シャッフルプロトコルの一般化も可能である。同じベース、ｇ←→Ｃに対して公開鍵のセット全体を維持するのではなく、鍵は独立したペア（ｇi，Ｈi）として維持される。シャッフラは、鍵ペアの任意のサブセット（Ｇi，Ｈi）を選択し、これらを「２組として」シャッフルし、その結果を戻す。これにより、オリジナルセットが大規模な場合、鍵あたりの作業がおよそ５０％増加するという犠牲を払うが、シャッフルはより扱いやすくなる。
【０３１４】
（参照文献）
［１］R.Cramer、I.Damgrd,、B.Schoenmakers、「証拠隠匿プロトコルの部分的知識および簡略化設計の証明」暗号学の発達−ＣＲＹＰＴＯ’９４、コンピュータサイエンス講義録、１７４〜１８７ページ、シュプリンガー出版、ベルリン、１９９４年。
【０３１５】
［２］R.Cramer、R.Gennaro、B.Schoenmakers、「安全かつ最適に効率化された複数機関選挙方式」暗号学の発達−ＥＵＲＯＣＲＹＰＴ’９７、コンピュータサイエンス講義録、シュプリンガー出版、１９９７年。
【０３１６】
［３］D.Chaum、T.P.Pedersen、「監視付きのウォレットデータベース」暗号学の発達−ＣＲＹＰＴＯ’９２、コンピュータサイエンス講義録第７４０巻、８９〜１０５ぺージ、ベルリン、１９９３年、シュプリンガー出版。
【０３１７】
［４］A.De Santis、G.Di Crescenzo、G.Persiano、M.Yung、「ＳＺＫの単調な公式閉包にて」ＦＯＣＳ’９４、４５４〜４６５ページ。
【０３１８】
［５］A.Fiat、A.Shamir、「自己証明の方法：識別および署名問題の実践的解決方法」暗号学の発達−ＣＲＹＰＴＯ’８６、コンピュータサイエンス講義録、１８６〜１９４ページ、シュプリンガー出版、ニューヨーク、１９８７年。
【０３１９】
［６］A.J.Menezes、P.C.van Oorschot、S.A.Vanstone、「応用暗号学ハンドブック」CRC Press、１９９７年。
【０３２０】
［７］T.Pedersen、「信用パーティなしのしきい値暗号システム」暗号学の発達−ＥＵＲＯＣＲＹＰＴ’９１、コンピュータサイエンス講義録、５２２〜５２６ページ、シュプリンガー出版、１９９１年。
【０３２１】
［８］K.Sako、J.Kilian、「受領証なしの混合タイプ投票方式−投票用紙記入所の実施に関する実践的解決方法」暗号学の発達−ＥＵＲＯＣＲＹＰＴ’９５、コンピュータサイエンス講義録、シュプリンガー出版、１９９５年。
【発明を実施するための最良の形態】
【０３２２】
図１および以下の考察は、本発明の態様が実施可能な好適なコンピューティング環境を簡単に、一般的に示すものである。必須ではないが、本発明の実施形態は、パーソナルコンピュータまたはウェブサーバなどの汎用コンピュータによって実行されるルーチンなどの、コンピュータ実行可能命令として実施可能である。当分野の技術者であれば、本発明の態様（小規模選挙など）が、インターネット機器、ハンドヘルドデバイス、ウェアラブルコンピュータ、携帯用情報端末（「ＰＤＡ」）、マルチプロセッサシステム、マイクロプロセッサベースまたはプログラム可能大衆消費電子製品、ネットワークＰＣ、ミニコンピュータ、セル式または移動電話、セットトップボックス、メインフレームコンピュータなどを含む、他のコンピュータシステム構成で実施可能であることを理解されよう。本発明の態様は、本明細書で説明した１つまたは複数のコンピュータ実行可能命令を実行するように特別にプログラム、構成、または構築された、特定用途向けコンピュータまたはデータプロセッサで実施可能である。実際、本明細書で一般的に使用される「コンピュータ」という用語は、上記デバイスのいずれかならびにデータプロセッサのいずれかを指すものである。
【０３２３】
本発明は、タスクまたはモジュールが、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、またはインターネットなどの、通信ネットワークを介してリンクされた、リモート処理デバイスによって実行される、分散コンピューティング環境で実施することもできる。分散コンピューティング環境では、プログラムモジュールまたはサブルーチンは、ローカルおよびリモート両方のメモリ記憶デバイス内に位置することができる。本明細書に記載された発明は、ファームウェアとしてチップ内に格納され、ならびにインターネットまたは他のネットワーク（無線ネットワークを含む）を介して電子的に配布される、磁気および光の読取り可能および取外し可能コンピュータディスクを含む、コンピュータ読取り可能媒体上で格納または配布することができる。関連分野の技術者であれば、本明細書に記載されたプロトコルの一部がサーバコンピュータ上に常駐可能であり、対応する部分がクライアントコンピュータ上に常駐することを理解されよう。こうしたプロトコルに特有のデータ構造およびデータの伝送も、本発明の範囲内に含まれる。
【０３２４】
特に指定のない限り、図１に示された様々なブロックの構成およびオペレーションは、従来の設計である。その結果、関連分野の技術者であれば容易に理解されるものであるため、こうしたブロックについては本明細書でこれ以上詳細に説明する必要がない。
【０３２５】
図１を参照すると、システム１００の好適な環境は、１つまたは複数の投票者またはクライアントコンピュータ１０２を含み、それぞれが、コンピュータが、インターネットのワールドワイドウェブ部分１０６内のウェブサイトを含むインターネットにアクセスしてデータを交換できるようにする、ブラウザプログラムモジュール１０４を含む。投票者コンピュータ１０２は、すべてよく知られているが図１には示されていない、１つまたは複数の中央処理ユニットまたは他の論理処理回路、メモリ、入力デバイス（たとえば、キーボード、マイクロフォン、タッチスクリーン、およびポインティングデバイス）、出力デバイス（たとえば、ディスプレイデバイス、オーディオスピーカ、およびプリンタ）、ならびに記憶デバイス（たとえば、固定、フロッピィ、および光のディスクドライブ）を含むことができる。投票者コンピュータ１０２は、オペレーティングシステム、１つまたは複数のアプリケーションプログラム（たとえばワードプロセッシングまたはスプレッドシートアプリケーション）などの、他のプログラムモジュールを含むこともできる。図１に示されるように、投票者１、２、３．．．Ｎで表されるＮ個の投票者コンピュータ１０２がある。
【０３２６】
インターネットまたはワールドワイドウェブ（「ウェブ」）１０６に結合されたサーバコンピュータシステム１０８または「集票センター」は、無記名投票の収集、格納、および他のプロセスの多くまたはすべてを実行する。サーバコンピュータ１０８に結合されたデータベース１１０は、投票者コンピュータ１０２、１つまたは複数の投票所コンピュータ１１２、およびサーバコンピュータ１０８の間で交換される、ウェブページおよびデータ（無記名投票およびシャッフル妥当性証明を含む）のうちの多くを格納する。投票所コンピュータ１１２は、大衆のメンバ、またはインターネット１０６に結合されたコンピュータへの容易なアクセスを有することができない投票者が、本明細書に記載されたシステムの下で電子的に投票できるようにするために、好適な投票場所に配置された、パーソナルコンピュータ、サーバコンピュータ、ミニコンピュータなどである。したがって、投票者コンピュータ１０２は、個々の投票者の家庭に配置することが可能であり、１つまたは複数の投票所コンピュータ１１２が公的に配置されるかまたはその他の方法で公的選挙の投票者にアクセスできる。投票所コンピュータ１１２は、それによっていくつかの投票者が同時にまたは平行して投票できるようにするために、１つのサーバコンピュータおよびＬＡＮを介してそれに結合された、いくつかのクライアントコンピュータまたは投票者端末を有する、ローカルエリアネットワーク（ＬＡＮ）を含むことができる。「投票者」という用語は、本明細書では一般に、本明細書に記載された一部またはすべてのプロトコルを使用する、任意の個人または組織を指すものであることにも留意されたい。
【０３２７】
代替実施形態の下では、システム１００は、団体の役員またはメンバの選挙などの、私的選挙の状況で使用することができる。この実施形態の下では、投票者コンピュータ１０２は、株主のラップトップまたはデスクトップのコンピュータとすることができ、投票所コンピュータ１１２は、選挙を実行する会社内に（たとえばロビーに）配置された１つまたは複数のコンピュータであってよい。したがって株主は、投票するために会社を訪問し、投票所コンピュータ１１２にアクセスすることができる。
【０３２８】
１つまたは複数の機関または組織コンピュータ１１４も、インターネット１０６を介してサーバコンピュータシステム１０８に結合される。しきい値暗号システムが使用される場合、機関コンピュータ１１４はそれぞれ、データベース１１０に格納された電子無記名投票を暗号解除するのに必要な鍵の割り当てを保持する。しきい値暗号システムは、機関の合計数ｎのサブセットｔ（すなわちｔ＜ｎ）が無記名投票を暗号解除することに同意する必要があり、それによって無記名投票の暗号解除にはすべての機関が必要であるという要件を避ける。言い換えれば、しきい値暗号システムの目的は、実質的なサブセットＴが協働するとメッセージが暗号解除できるように、グループのメンバｎの間で、秘密鍵ｓを共用すること、すなわち（ｔ，ｎ）しきい値暗号システムである。プロトコルは、（１）グループ間で共同で鍵を生成する、および（２）秘密鍵を再構築することなくメッセージを暗号解除するように定義される。機関コンピュータ１１４は、投票機関終了後、それらの暗号解除の割り当てをサーバコンピュータシステム１０８に提供することが可能であり、その結果サーバコンピュータシステムが無記名投票を暗号解除し、結果を集計する。
【０３２９】
さらに、図示された実施形態の下では、本明細書に記載されたように、機関コンピュータがそれぞれ無記名投票を１回シャッフルすることができる。各シャッフルと共に、各機関コンピュータはシャッフル妥当性証明を生成し、これを暗号化してサーバコンピュータ１０８に転送するか、または機関コンピュータによってローカルに格納することができる。代替実施形態では、機関コンピュータの１つのセットが暗号化された無記名投票をシャッフルしてシャッフル妥当性証明を生成し、機関コンピュータの第２のセットが無記名投票を暗号解除するために鍵のシェアを使用する、機関コンピュータの追加セットが提供される。
【０３３０】
機関コンピュータ１１４と同様の、１つまたは複数のオプションの検証者コンピュータ１３０も提供することができる。検証者コンピュータは、選挙が損なわれていないことを検証するために、選挙の写しを受け取ることができる。たとえば検証者コンピュータは、本明細書に記載されるように、それぞれの機関コンピュータからシャッフル妥当性証明を受け取ることができる。検証者コンピュータは、選挙後に検証を実行することが可能であり、インターネットに接続する必要はない。実際には、本明細書に図示または記載された他のコンピュータによって、検証を実行することができる。
【０３３１】
サーバ、検証者、または機関のコンピュータが投票者登録プロトコルを実行可能であるか、または別々の登録コンピュータを提供することができる（図示せず）。登録コンピュータは、指紋データ、声紋データ、デジタル写真の比較、および関連分野の技術者に知られた他の技法などの登録者の生物測定データを読み取るための生物測定読取り器を含むことができる。投票者登録および検証可能なシャッフルで使用するための匿名証明書の発行について、以下で説明する。
【０３３２】
サーバコンピュータ１０８は、サーバエンジン１２０、ウェブページ管理構成要素１２２、データベース管理構成要素１２４、ならびに図示されていない他の構成要素を含む。サーバエンジン１２０は、標準機能に加えて、電子投票プロトコルの一部を実施する。暗号化プロトコルをサーバコンピュータ上に格納し、こうしたプロトコルの一部を適切な定数と共にクライアントコンピュータ上にも格納することができる。実際には、上記プロトコルは、磁気および光の読取り可能および取外し可能コンピュータディスク、半導体チップ上に格納されたマイクロコード（たとえばＥＥＰＲＯＭ）を含む、コンピュータ読取り可能媒体上で格納および配布可能、ならびにインターネットまたは他のネットワークを介して電子的に配布可能である。関連分野の技術者であれば、プロトコルの一部がサーバコンピュータ上に常駐し、対応する部分がクライアントコンピュータ上に常駐することを理解されよう。上記プロトコル特有のデータ構造およびデータの伝送も、本発明の範囲内に含まれる。したがって、サーバエンジン１２０は、許可された投票者への必要なすべての無記名投票の伝送、集票、無記名投票の検証（たとえば、デジタル署名のチェックおよび無記名投票に含まれた妥当性証明の検証のパス）、票の集約、無記名投票の暗号解除、および／または投票の集計を実行することができる。代替実施形態の下では、サーバエンジン１２０は、データ収集センターとしてすべての電子無記名投票を集めるだけである。次に電子無記名投票は、無記名投票をシャッフルし、得票を暗号解除し、選挙結果を生成するためのツールと共に格納され、地方自治体などの選挙を実施する第三者組織に提供される。同様に、シャッフル妥当性証明などの選挙監査情報をローカルに格納するか、あるいは地方自治体または他の組織に提供することができる。
【０３３３】
ウェブページ構成要素１２２は、以下に記載するように、電子無記名投票箱ウェブページなどのウェブページの作成および表示またはルーティングを処理する。投票者およびユーザは、http://www.votehere.netなどのサーバコンピュータ１０８に関連付けられたＵＲＬ、または地方自治体のＵＲＬなどの選挙に関連付けられたＵＲＬを使用して、サーバコンピュータ１０８にアクセスすることができる。地方自治体は、サーバコンピュータシステム１０８を直接ホストまたは操作するか、あるいはこのような受け取った電子無記名投票を、サーバコンピュータシステムを操作することのできる第三者の投票認可者に自動的に転送することができる。本明細書に記載されたＵＲＬあるいは任意のリンクまたはアドレスは、任意のリソースロケータであってよい。
【０３３４】
ウェブページ管理プロセス１２２およびサーバコンピュータ１０８は、許可された投票者またはシステム管理者などの、許可された人々のみがアクセスできる安全なセクションまたはページを有することができる。サーバコンピュータ１０８は、こうしたユーザを認証するために、たとえばセキュアソケットレイヤ（「ＳＳＬ」）およびトークンまたはクッキーを使用することができる。実際には、小規模な選挙、または不正行為の確率が低い（または不正行為の結果が比較的重要でない）場合、システム１００は、上記の特許出願に記載されたような複雑な電子暗号化無記名投票を使用する代わりに、以下で説明するように投票を集めて格納するために、こうした単純なネットワークセキュリティ手段を使用することができる。（パスワードの使用などによる）ユーザの認証、安全な伝送接続の確立、ならびに安全なサーバおよびウェブページの提供などの方法が、関連分野の技術者に知られている。
【０３３５】
選挙の方式およびシステムは、各記入にデジタル署名され、何も消去できない、「掲示板」を使用することができる。掲示板はウェブサーバとして実施される。「無記名投票箱」が掲示板上に常駐し、暗号化されたすべての無記名投票を保持する。ウェブサーバデータを追記型（ＷＯＲＭ）永続記憶媒体または同様のデバイスに書き込むことによって、消去を防止することができる。
【０３３６】
本発明の一実施形態は、コンピュータを接続するためにインターネットを使用するものとして本明細書に記載されているが、他の代替実施形態が可能であることに留意されたい。たとえば、本発明の態様は、スタンドアロン型コンピュータによって使用することができる。本発明の態様は、任意の相互接続されたデータ処理マシンによって使用することもできる。こうしたマシンは、ブラウザを使用する代わりに、本発明に記載された方法またはプロトコルの態様を実施するためのクライアントソフトウェアを使用することができる。
【０３３７】
図２を参照すると、方法２００として示された、シャッフルプロトコルの選挙への基本的応用例を示す概略図が示されている。ブロック２０２では、投票者Ｊｏｅ  Ｓｍｉｔｈ、Ｓａｌｌｙ  Ｊｏｎｅｓ、およびＩａｎ  Ｋｅｌｌｅｉｇｈそれぞれに１つずつ、３つの暗号化された無記名投票が提出される。ブロック２０４では、投票者のリストまたは名簿が、ブロック２０６に示された暗号化された無記名投票とは分離される。その後、ブロック２０８に示される無記名投票のシャッフル済みセットを生成するために、無記名投票の一方向の再暗号化が実行される。シャッフル妥当性証明が、ブロック２１０に示されたこの第１のシャッフルに基づいて生成される。シャッフル妥当性証明は、第三者が、すべての入力データ（無記名投票）には同じオペレーションが適用されていること、および無記名投票に何の変更も実行されていないことを保証できるものである。
【０３３８】
ブロック２１２に示された第２のシャッフル済みセットを生成するために、（以前にシャッフルされた）無記名投票の第２のシャッフルが実行される。ブロック２１４に示されたシャッフル妥当性証明が再度生成される。ブロック２１６の下で無記名投票の最終のシャッフル済みセットを生成するために、ブロック２１２のシャッフル済み無記名投票が３回目にシャッフルされる。第３のシャッフルに基づいて、第３の妥当性証明２１８が同様に生成される。この例では、合計で３掛ける３のシャッフルアレイが提供される。無記名投票は、シャッフルに続き、ブロック２２０として示される得票を生成するために暗号解除される。第三者は、各シャッフラが選挙の整合性を保っていることを保証するために、とりわけ各シャッフル妥当性証明を分析することによって、その選挙を検証することができる。
【０３３９】
シャッフルプロトコルは、上記では、電子投票方式の場合などの様々な応用例に使用可能な有効に分けられたサブルーチンとして示されている。第１のサブルーチンは、証明者と検証者との間に、スケーリングされた反復対数乗算証明の機能を提供する。第２のサブルーチンは、単純なシャッフルプロトコルの機能を提供し、スケーリングされた反復対数乗算証明を使用する。その後、第３のサブルーチンが、シャッフラが指数を知らない一般的なシャッフル機能を実施して、第２のサブルーチンに基づいて単純なシャッフルを構築する。第４のサブルーチンは、第３のサブルーチンをｋ組の要素のシャッフルにまで拡大する。他のルーチンももちろん提供される。
【０３４０】
当分野の技術者であれば、本発明の概念がインターネット以外の様々な環境で使用可能であることを理解されよう。たとえばこの概念を、電子メール無記名投票、トランザクション、またはフォームが処理および格納される、電子メール環境で使用することができる。一般に、ウェブページまたは表示記述（たとえば掲示板）は、ＨＴＭＬ、ＸＭＬ、またはＷＡＰフォーマット、電子メールフォーマット、あるいは（文字／コードベースフォーマット、ビットマップ化されたフォーマット、およびベクトルベースフォーマットを含む）情報を表示するのに好適な任意の他のフォーマットであってよい。また、インターネットの代わりに、ローカルエリアネットワーク、ワイドエリアネットワーク、またはポイントツーポイントダイヤルアップ接続などの、様々な通信チャネルを使用することができる。クライアント／サーバ環境ではなく、単一のコンピュータ環境内で、様々なトランザクションも実行可能である。各投票者またはクライアントのコンピュータは、サーバコンピュータまたはシステムと対話するハードウェアまたはソフトウェアの任意の組合せを含むことができる。これらのクライアントシステムは、テレビジョンベースシステム、インターネット機器、移動電話／ＰＤＡ、およびそれを介してトランザクションが実行可能な様々な他の大衆消費製品を含むことができる。
【０３４１】
一般に、本明細書で使用される「リンク」とは、ネットワーク上にサイトまたはノードを有する投票機関の表示記述などの、ネットワーク上のリソースを識別する任意のリソースロケータのことである。一般に、投票者コンピュータ、端末、およびサーバなどのハードウェアプラットフォームが本明細書に記述されているが、本明細書の態様は、こうしたノードを識別するための対応するリソースロケータを有するネットワーク上のノードに等しく適用可能である。
【０３４２】
状況により明確に必要とされない限り、記述および特許請求の範囲全体を通じて、「含む」などの用語は、排他的または網羅的な意味とは反対の、包括的な意味、すなわち、「含むがそれに限定されない」という意味であると解釈される。単数または複数を使用した用語は、それぞれ単数または複数も含む。さらに、本明細書で使用される「本明細書」「上記」「以下」および同様の趣旨の用語は、概して本明細書全体を指すものであり、本明細書の任意の特定部分を指すものではない。
【０３４３】
本発明の例示された実施形態の上記説明は、網羅的であるかまたは本発明を開示された精密な形に限定することを意図するものではない。関連分野の技術者であれば理解されるように、本発明の特定の実施形態およびその例は、例示的な目的で本明細書に記載されており、本発明の範囲内で様々な等価の修正が可能である。本明細書に提供された本発明の教示は、上記に示された電子投票システムだけでなく、他の暗号化応用例にも適用可能である。たとえば、プロトコルは、匿名および監査能力の両方が必要条件である電子商取引にも応用例がある。この例が、電子支払方式（「ｅキャッシュ」）である。
【０３４４】
上記の詳細な説明に鑑みて、本発明のこれらおよび他の変更が実施可能である。一般に、添付の特許請求の範囲では、使用される用語は、本発明を本明細書および特許請求の範囲に開示された特定の実施形態に限定するものと解釈されるべきではなく、データセキュリティを提供するために特許請求の範囲の下で動作するすべての暗号化システムおよび方法を含むものと解釈されるべきである。したがって本発明は本開示に限定されるものではなく、本発明の範囲は、もっぱら特許請求の範囲によって決定されるものである。
【０３４５】
本発明の一定の態様は一定の特許請求の範囲形式で提示されるが、発明者は、任意数の特許請求の範囲形式で、本発明の様々な態様を企図している。たとえば、コンピュータ読取り可能媒体で実施されるものとして本発明の一態様のみが示されているが、他の態様もコンピュータ読取り可能媒体で同様に実施可能である。したがって発明者は、本発明の他の態様に関するこうした追加の特許請求の範囲形式を追求するために、本明細書出願後、追加の特許請求の範囲を追加する権利を留保する。
【図面の簡単な説明】
【０３４６】
【図１】本発明の態様が実施可能な好適なコンピューティング環境を示す図である。
【図２】本発明のシャッフルプロトコルの選挙への基本的応用例を示す概略図である。
【図１】
2005524250.tif 000097
【図２】
2005524250.tif 000098
【手続補正書】
【提出日】平成16年4月16日(2004.4.16)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】  コンピュータ化されたネットワークと共に使用する電子投票システムであって、
コンピュータ化されたネットワークに結合された少なくとも第１、第２および第３の投票者コンピュータから要求を受け取るために結合された少なくとも１つのサーバコンピュータを備え、
前記第１の投票者コンピュータは、複数の投票者コンピュータから受け取った電子信用証明の集約体に対応する一連の電子信用証明を、前記サーバコンピュータから受け取るように構成され、各電子信用証明は、デジタル署名アルゴリズム（ＤＳＡ）またはＥｌＧａｍａｌペアであり、前記第１の投票者コンピュータは、少なくとも第１の秘密鍵を使用して、秘密の一方向暗号変換を適用して、前記一連の電子信用証明を匿名でシャッフルし、前記サーバコンピュータの一連の第１のシャッフル済み信用証明を生成するように構成され、前記第１の投票者コンピュータのみが、前記一連の第１のシャッフル済み信用証明と前記一連の電子信用証明との間の一致を知っており、前記第１の投票者コンピュータは、反復対数乗算証明に基づいて前記一連の第１のシャッフル済み信用証明に関する正当性の第１の線形サイズ証明を提供し、第１の無記名投票に第１の関連付けられた信用証明を提供するように構成され、
前記第２の投票者コンピュータは、前記サーバコンピュータから、前記一連の第１のシャッフル済み信用証明を受け取り、少なくとも第２の秘密鍵を使用して前記暗号変換を適用し、前記一連の第１のシャッフル済み信用証明を匿名でシャッフルし、前記サーバコンピュータの一連の第２のシャッフル済み信用証明を生成するように構成され、前記第２の投票者コンピュータのみが、前記一連の第１のシャッフル済み信用証明と前記一連の第２のシャッフル済み信用証明との間の一致を知っており、前記第２の投票者コンピュータは、第２の関連付けられた信用証明を有する第２の無記名投票と共に、反復対数乗算証明に基づいて前記一連の第２のシャッフル済み信用証明に関する正当性の第２の線形サイズ証明を第２のサーバコンピュータに提供するように構成され、
前記第３の投票者コンピュータは、前記一連の第２のシャッフル済み信用証明を受け取り、少なくとも第３の秘密鍵を使用して前記暗号変換を適用し、前記一連の第２のシャッフル済み信用証明を匿名でシャッフルし、前記サーバコンピュータの一連の第３のシャッフル済み信用証明を生成するように構成され、前記第３の投票者コンピュータのみが、前記一連の第２のシャッフル済み信用証明と前記一連の第３のシャッフル済み信用証明との間の一致を知っており、前記第３の投票者コンピュータは、第３の関連付けられた信用証明を有する第３の無記名投票と共に、反復対数乗算証明に基づいて前記一連の第３のシャッフル済み信用証明に関する正当性の第３の線形サイズ証明を提供するように構成され、
前記サーバコンピュータは、前記第１、第２および第３の投票者コンピュータから正当性の証明を受け取り、前記シャッフル済み信用証明の正当性を検証し、各々第１、第２および第３の関連付けられた信用証明を有する第１、第２および第３の無記名投票を受け取り、検証し、集計するように構成されたことを特徴とするシステム。
【請求項２】  前記コンピュータ化されたネットワークに結合された複数の機関コンピュータであって、前記第１、第２および第３の無記名投票は、しきい値、基礎となるグループＺｐまたは楕円曲線を使用する離散対数非対称暗号化プロセスの下で暗号化され、
次に前記複数の機関コンピュータの各々は、
少なくとも前記第１、第２および第３の暗号化された無記名投票を受け取り、
前記無記名投票を秘密にシャッフルし、
前記秘密にシャッフルされた無記名投票に暗号解除鍵の割り当てを適用して、前記秘密にシャッフルされた無記名投票を部分的に暗号解除し、
前記部分的に暗号解除され秘密にシャッフルされた無記名投票を、次の機関コンピュータに渡すことを特徴とする請求項１に記載のシステム。
【請求項３】  前記第１、第２および第３の投票者コンピュータは、少なくとも第１、第２および第３の公開鍵の識別を、前記第１、第２および第３の投票者コンピュータに各々すべて関連付けられた電子信用証明の集約体において、前記サーバコンピュータに提供するように構成され、
前記サーバコンピュータは、前記第１、第２および第３の公開鍵をそれに応答して除去するように構成されたことを特徴とする請求項１に記載のシステム。
【請求項４】  前記コンピュータ化されたネットワークは、ワールドワイドウェブを含み、前記第１、第２および第３の投票者コンピュータは、ウェブブラウザプログラムを含むことを特徴とする請求項１に記載のシステム。
【請求項５】  前記第１、第２および第３の投票者コンピュータのうちの少なくとも１つは、パームサイズコンピュータ、セル式電話、ウェアラブルコンピュータ、対話型テレビジョン端末、またはインターネット機器であることを特徴とする請求項１に記載のシステム。
【請求項６】  要素のシーケンスを受け取るためのコンピュータシステムであって、
コンピュータネットワークに結合され、
個々のデータファイルを表す電子データ要素のシーケンスを受け取り、
少なくとも第１の秘密値を使用して暗号化変換を適用して、前記電子データ要素のシーケンスを匿名で並び替え、電子データ要素の第１のシャッフル済みシーケンスを生成し、前記サーバコンピュータは、前記電子データ要素の第１のシャッフル済みシーケンスと前記電子データ要素のシーケンスとの間の一致を知っており、
２進演算子を使用する反復対数乗法証明に基づいて前記電子データ要素の第１のシャッフル済みシーケンスの正当性の第１の線形サイズ証明を生成し、前記データ要素のシーケンス内の前記データ要素の各々は、共通のベース値に関連付けられ、前記正当性の証明を検証することは、３ムーブ、パブリックコイン証明の知識を使用し、ここで、前記コンピュータは、検証要求に応答して関連付けられた一連の線形等式を解くことによって、一連の指数を計算するように構成されたコンピュータ
を備えたことを特徴とするシステム。
【請求項７】  前記受け取られた電子データ要素のシーケンスは、コンピュータが知らない鍵を使用するＺｐまたは楕円曲線グループを使用して暗号化され、前記コンピュータは、
検証者コンピュータからランダムに生成された値ｅｉを受け取り、
前記受け取られた一連の値ｅｉと秘密に生成された値とを使用する、秘密の一方向暗号化変換に基づいて、一連の値Ｄｉを秘密に生成し、
前記電子データ要素のシーケンスを並べ替え、前記一連の値Ｄｉおよび秘密値γに基づいて、前記要素の第１のシャッフル済みシーケンスを生成し、
前記暗号化変換に基づいて、前記サーバコンピュータが、前記暗号化変換がどのように前記電子データ要素のシーケンスを並べ替えたかのアクセスを有する知識の証明として、前記値Ｄｉおよび一連の証明値を提供し、前記暗号化変換を前記検証者コンピュータに対して明らかにすることなく、前記要素の第１のシャッフル済みシーケンスを生成するように構成されたことを特徴とする請求項６に記載のシステム。
【請求項８】  前記サーバコンピュータは、
対応する複数の個人から複数の公開鍵を受け取り、前記複数の個人の各々は、前記複数の公開鍵のうちの１つに対応する秘密鍵を有し、
１つの秘密鍵を有する前記複数の個人のうちの１人から要求を受け取り、
前記複数の公開鍵のうち少なくとも１つのサブセットを要求側の個人に提供し、
反復対数乗算証明および前記１つの秘密鍵に対応する値に基づいて、前記複数の公開鍵のファイルおよびシャッフルと、前記シャッフル済み公開鍵に関する正当性の線形サイズ証明とを受け取り、前記値は、前記ファイルに関連付けられ、前記１つの秘密鍵を明らかにすることなく、１人の個人が前記１つの秘密鍵の知識を有するという証明を提供し、
前記正当性の証明をチェックし、
前記値が前記公開鍵および前記ファイルのうちの１つに数学的に関係していることをチェックし、
前記複数の公開鍵から１つの公開鍵を減らすように
構成されたことを特徴とする請求項６に記載のシステム。
【請求項９】  前記電子要素のシーケンスは、公開鍵であり、前記サーバは、個人からの要求に応答して、個人が前記公開鍵のうちの１つに一意かつ数学的に関係する値を有することをチェックするように構成され、
そうであれば、前記１人の個人に対して証明書を発行することを特徴とする請求項６に記載のシステム。
【請求項１０】  コンピュータ実施方法であって、
複数の公開鍵のうちの１つに対応する秘密鍵を有する複数の個人のうちの１人からの要求を受け取ること、
前記複数の公開鍵のうちの少なくとも１つのシャッフル済みサブセットを、要求側個人に提供すること、
ファイルＦと、
（１）公開鍵の新しいシャッフル済みセットＳ、
（２）前記公開鍵の新しいシャッフル済みセットに関する正当性のシャッフル証明、および
（３）前記要求側個人からの署名値ｘからなる認証とを受け取ること、および
前記認証を、
（ａ）前記正当性のシャッフル証明の検証が成功し、および
（ｂ）Ｖ（Ｆ，ｘ，ｓ０）が真であり、ただし、Ｖは署名検証機能であり、ｓ０は前記公開鍵の新しいシャッフル済みセットＳからの１つの公開鍵である場合に受け取ること
を備えたことを特徴とする方法。
【請求項１１】  コンピュータ実施方法であって、
複数の公開鍵のうちの１つの公開鍵に対応する１つの秘密鍵に関連付けられたコンピュータから要求を受け取り、前記複数の公開鍵の各々は、複数の秘密鍵のうちの１つに対応すること、
前記複数の公開鍵のうちの少なくとも１つのシャッフル済みサブセットを前記要求側コンピュータに提供すること、
前記要求側コンピュータからファイルを受け取ること、
反復対数乗算証明および前記１つの秘密鍵に対応する値に基づいて、前記複数の公開鍵の新しいシャッフル済みサブセットと、前記公開鍵の新しいシャッフル済みサブセットに関する正当性の線形サイズ証明とを受け取り、前記値は、前記ファイルに関連付けられ、前記１つの秘密鍵を明らかにすることなく、１人の個人が前記１つの秘密鍵の知識を有するという証明を提供すること、
前記正当性の証明をチェックすること、および
前記値が前記公開鍵および前記ファイルのうちの１つに、実質的に一意の方法で数学的に関係していることをチェックすること
を備えたことを特徴とする方法。
【請求項１２】  前記要求側コンピュータから、前記公開鍵の新しいシャッフル済みサブセット内の前記１つの公開鍵の少なくとも１つの指示を受け取ることをさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１３】  前記公開鍵の新しいシャッフル済みサブセットから前記１つの公開鍵を除去することをさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１４】  複数の公開鍵の少なくとも１つのサブセットＨ上で実行された秘密の暗号シャッフルオペレーションに基づいて、複数の公開鍵のシャッフル済みサブセットＨ’を複数の機関の各々から順番に受け取り、前記複数の公開鍵のシャッフル済みセットＨ’を生成すること、
前記暗号シャッフルオペレーションの検証写しを複数の機関の各々から順番に受け取ること、および
前記検証の写しに基づいて、前記暗号シャッフルオペレーションの正当性を検証し、検証された場合は、前記複数の公開鍵のシャッフル済みセットをＨ’からＨに設定すること
をさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１５】  前記複数の公開鍵の少なくとも一部を受け取った後に、前記受け取った複数の公開鍵のうち少なくとも１つのサブセットを前記複数の公開鍵のうち受け取ったシャッフル済みセットに設定し、前記複数の公開鍵のうちのシャッフル済みセットは、第三者から受け取られたことを特徴とする請求項１１に記載の方法。
【請求項１６】  前記チェックステップに従って、証明書を発行すること、
その後、複数の個人のうちの１人から前記発行された証明書を受け取ること、および
前記１人の個人に電子無記名投票を提供すること
をさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１７】  受け取った要求にデジタル署名して、公開鍵インフラストラクチャ（ＰＫＩ）証明書を生成することをさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１８】  複数のユーザコンピュータのうちの少なくとも一部から発行された証明書を受け取り、それに応答して初期の電子無記名投票を提供すること、および
前記複数のユーザコンピュータのうちの少なくとも一部から、暗号化されていない投票済みの無記名投票を受け取ること
をさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１９】  証明者コンピュータと検証者コンピュータとの間のコンピュータ実施暗号化方法であって、
電子データ要素の第２のシリーズに関して電子データ要素の第１のシリーズを秘密にシャッフルして、シャッフル済みセットを生成すること、および
第１の多項式に関する第１のルートセットが、第２の多項式に関する第２のルートセットの固定定数倍に等しいことの証明に基づいて、前記シャッフル済みセットに関する正当性の線形サイズ証明を生成することを備え、
前記第１のルートセットが前記第２のルートセットの固定倍に等しいことの正当性の前記線形サイズ証明は、第２の固定定数を指定すること、第１のランダムポイントで前記第１の多項式を評価して第１の値を得ること、前記第１のランダムポイントで前記第２の多項式を評価して第２の値を得ること、および前記第２の値が前記第１の値と前記第２の固定定数との積に等しいことを判定することによって得られることを特徴とする方法。
【請求項２０】  前記第１の要素シーケンス内の要素のうちの少なくとも一部は、電子無記名投票であることを特徴とする請求項１９に記載の方法。
【請求項２１】  前記シャッフル済みセット内の要素のうちの少なくとも一部は、ＥｌＧａｍａｌペアであることを特徴とする請求項１９に記載の方法。
【請求項２２】  秘密のシャッフルを反復すること、要素の入力シーケンスでｌ組の要素を生成して提供することをさらに備えたことを特徴とする請求項１９に記載の方法。    【請求項２３】  前記要素の第１のシリーズを秘密にシャッフルすることは、識別要素セットのサブセットを受け取ることを含み、前記セット内の各識別要素は、個人に対応し、前記方法は、
前記検証コンピュータが前記正当性の証明を検証した場合、匿名の証明書を受け取ることをさらに備えたことを特徴とする請求項１９に記載の方法。
【請求項２４】  コンピュータ化されたネットワークで使用するための電子投票システムであって、
前記コンピュータ化されたネットワークに結合され、しきい値と離散対数非対称暗号化プロセスの下で暗号化された複数の無記名投票を受け取る複数の機関のコンピュータを備え、
前記複数の機関のコンピュータの各々は、順に、
少なくとも前記暗号化された無記名投票を受け取り、
前記無記名投票を秘密にシャッフルし、
前記秘密にシャッフルされた無記名投票に暗号解除鍵の割り当てを適用し、前記秘密にシャッフルされた無記名投票を部分的に暗号解除し、
前記シャッフルされ部分的に暗号解除された無記名投票に関する妥当性証明を生成し、
前記部分的に暗号解除され秘密にシャッフルされた無記名投票を、次の機関コンピュータに渡すように構成され、
最後の前記機関のコンピュータは、前記秘密にシャッフルされた無記名投票に最後の暗号解除鍵の割り当てを適用し、前記秘密にシャッフルされた無記名投票を全て暗号解除することを特徴とするシステム。
【請求項２５】  前記複数の機関のコンピュータの各々は、実質的に同時に、
（１）前記無記名投票を秘密にシャッフルし、
（２）前記秘密にシャッフルされた無記名投票に前記暗号解除鍵の割り当てを適用し、前記秘密にシャッフルされた無記名投票を部分的に暗号解除し、
（３）前記部分的に暗号解除された無記名投票の妥当性の証明を生成する
ように構成されたことを特徴とする請求項２４に記載のシステム。
【請求項２６】  コンテンツが命令を提供し、コンピュータによって実施されると、電子データ要素のシーケンスのシャッフルを実行する、コンピュータ読取り可能媒体であって、
複数の公開鍵のうちの１つの公開鍵に対応する１つの秘密鍵に関連付けられたコンピュータからの要求を提供し、前記複数の公開鍵の各々は、複数の秘密鍵の１つに対応すること、
前記複数の公開鍵のうち少なくとも１つのシャッフル済みサブセットを受け取ること、
ファイルを提供すること、および
反復対数乗算証明および前記１つの秘密鍵に対応する値に基づいて、前記複数の公開鍵の新しいシャッフル済みサブセットと、前記公開鍵の新しいシャッフル済みサブセットに関する正当性の証明とを生成し、前記値は、前記ファイルに関連付けられ、前記１つの秘密鍵を明らかにすることなく前記１つの秘密鍵の知識の証明を提供すること
を備えたことを特徴とするコンピュータ読取り可能媒体。
【請求項２７】  前記コンピュータ読取り可能媒体は、前記電子データ要素のシーケンスおよび前記コンテンツを受け取るコンピュータネットワーク内の論理ノードであることを特徴とする請求項２６に記載のコンピュータ読取り可能媒体。
【請求項２８】  前記コンピュータ読取り可能媒体は、コンピュータ読取り可能ディスクであることを特徴とする請求項２６に記載のコンピュータ読取り可能媒体。
【請求項２９】  前記コンピュータ読取り可能媒体は、前記コンテンツを含む生成済みデータ信号を伝送するデータ伝送媒体であることを特徴とする請求項２６に記載のコンピュータ読取り可能媒体。
【請求項３０】  前記コンピュータ読取り可能媒体は、コンピュータシステムのメモリであることを特徴とする請求項２６に記載のコンピュータ読取り可能媒体。
【請求項３１】  前記コンピュータ読取り可能媒体は、投票機関のサーバコンピュータへのインターネット接続リンクであることを特徴とする請求項２６に記載のコンピュータ読取り可能媒体。
【請求項３２】  前記正当性の証明は、第１および第２の多項式の計算を含む正当性の線形サイズ証明であり、ランダムに選択されたポイントにおいて前記第１および第２の多項式の評価は、結果として計算された同じ値になることを特徴とする請求項２６に記載のコンピュータ読取り可能媒体。
【請求項３３】  電子データ要素の混合を実行するコンピュータ実施方法であって、
複合公開鍵の少なくとも元のサブセットを受信すること、および
前記公開鍵の元のサブセットを混合して、混合された公開鍵のセットを生成することを備え、
前記混合された公開鍵のセットは、前記公開鍵の元のサブセットと相関がなく、前記混合された公開鍵のセットは、秘密鍵のセットに対応することを特徴とする方法。
【請求項３４】  ファイルを提供すること、および
反復対数乗算証明および前記１つの秘密鍵に対応する値に基づいて、前記新しく混合された公開鍵のサブセットに関する正当性の証明を生成し、前記値は、前記ファイルに関連付けられ、前記１つの秘密鍵を明らかにすることなく前記１つの秘密鍵の知識の証明を提供すること
をさらに備えたことを特徴とする請求項３３に記載の方法。
【請求項３５】  前記混合された公開鍵のセットに関する正当性の証明を生成し、前記正当性の証明は、前記混合された公開鍵のセットが前記秘密鍵のセットに対応することをさらに備えたことを特徴とする請求項３３に記載の方法。
【請求項３６】  前記混合された公開鍵のセットは、一連の無記名投票に相当することを特徴とする請求項３３に記載の方法。
【請求項３７】  前記混合された公開鍵のセットに関し、第１および第２の多項式の計算を含む正当性の証明を生成し、ランダムに選択されたポイントにおいて前記第１および第２の多項式の評価は、結果として計算された同じ値になることを特徴とする請求項３３に記載の方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０１８３
【補正方法】変更
【補正の内容】
【０１８３】
【数１】
2005524250.tif 000099
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０２２５
【補正方法】変更
【補正の内容】
【０２２５】
【数２】
2005524250.tif 000100
【国際調査報告】
2005524250.tif 000101
2005524250.tif 000102
2005524250.tif 000103