安全な複数オーソリティ選挙のためのエルガマル暗号化データのように暗号化されたデータの検証可能な秘密シャッフル
【課題】暗号化プロセスは、一連の入力データ要素を検証可能にシャッフルすることを可能にする。
【解決手段】1つまたは2つ以上のオーソリティまたは個人は、入力データ(例えば、離散対数形式またはエルガマル暗号化投票データにおける公開鍵)を「シャッフル」または「匿名化」する。このプロセスは、結果的に生じる証明の写しを検査する誰からも見つからずに1つまたは2つ以上のオーソリティまたは個人が元のデータに変更を加えることを防止する有効な構築を含む。シャッフリングは、種々の時点で実行することができる。選挙の実施例では、シャッフリングは、例えば票の収集後、または登録中、または選挙の票要求フェーズで実行することができ、それによって投票者の識別を匿名化する。
【解決手段】1つまたは2つ以上のオーソリティまたは個人は、入力データ(例えば、離散対数形式またはエルガマル暗号化投票データにおける公開鍵)を「シャッフル」または「匿名化」する。このプロセスは、結果的に生じる証明の写しを検査する誰からも見つからずに1つまたは2つ以上のオーソリティまたは個人が元のデータに変更を加えることを防止する有効な構築を含む。シャッフリングは、種々の時点で実行することができる。選挙の実施例では、シャッフリングは、例えば票の収集後、または登録中、または選挙の票要求フェーズで実行することができ、それによって投票者の識別を匿名化する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に暗号化に関し、より詳細には、投票方式で使用するための電子暗号化に関する。
【背景技術】
【０００２】
(背景および概要)
オブジェクト、記録またはトークンの集合のシャッフルの概念は、簡素かつ直観的であり、有用な使用例が、人々の日常の種々の活動にあふれている。カジノのギャンブラーは、自分の持ち札を取り出すときは、その1枚1枚が52の一意の値のうちの1つであること、およびその持ち札と同じ持ち札を有する者はそのテーブルにはいないということを知っている。しかし、たとえディーラーがそれらのカードをシャッフルする前にそのギャンブラーがカードの正確な順序を記録しておくことができたとしても、そのギャンブラーは、それらのカードがどのように配られたかはまったく知ることはない。
【０００３】
電子データのコンテクストにおいては、入力されたシーケンスを同種のランダムだが検証が可能なように置換するという問題は驚くほど困難である。この問題は、データ自体、監査役(auditor)に常に明白であるか、そうでないかのどちらかしかないということである。明白である場合、入力された記録と出力された記録との間の対応は自明(trivial)で、監査役または他のオブザーバーが再構成することができる。明白でない場合、入力された記録と出力された記録は、同一の基礎となるデータの異なる表現でなければならない。しかし、出力が十分に異なっていて(すなわち、十分に暗号化されていて)監査役が対応関係を再構成することができない場合、監査役は、シャッフリングの過程でシャッフラが基礎となるデータを変更しなかったことをいかに確信するであろうか。
【０００４】
以下の説明の大半は、エルガマル（ElGamal）暗号化データという、重要なコンテクストにおいてこの問題を解決するための有効な(線形の)方法を提供するために費やされている。できる限り明瞭かつ簡潔な解説とするため、以下の説明の大部分は、大きな素数pを法とする乗法単位群である
【０００５】
【数１】
【０００６】
で演算が実行される具体的なケースをそのまま参照する。しかし、使用され基礎となる(乗法の)群の特性は、関連するエルガマル暗号システムが安全でなければならないということ、および、関係式loggX = loghY = uに対するChaum-Pedersen（チョム−ペダーセン）プロトコル(D.Chaum著、「Zero-knowledge undeniable signatures. Advances in Cryptology EUROCRYPT'90, volume 473, Lecture Notes in Computer Science」473巻、458-464頁、1991年Springer-Verlag。D.ChaumおよびT.P.Pedersen著、「Wallet Databases With Observers. In Advances in Cryptology CRYPTO '92, volume 740, Lecture Notes in Computer」740巻、89-105頁、ベルリン、1993年、Springer-Verlag。)は秘密指数uに関する情報を漏らしてはならないということだけである。実際、一実施形態では、普遍的に検証可能な複数オーソリティ選挙プロトコル−べリファイア(verifier)は、Fiat-Shamirヒューリスティック(A.FiatおよびA.Shamir著、「How to prove yourself: Practical solutions to identification and signature problems. Advances in Cryptology CRYPTO'86, Lecture Notes in Computer Science」186-194頁、Springer-Verlag、New York、1987年。) によって実施されるので、この場合には、公正なベリファイアに対してプロトコルはゼロ知識であれば十分である(R. Cramer、R.Gennaro、B. Schoenmakers著、「A secure and optimally efficient multi-authority election scheme. Advances in Cryptology EUROCRYPT '97, Lecture Notes in Computer Science」Springer-Verlag, 1997年。)。したがって、シャッフルプロトコルは、楕円曲線などの他の群までエルガマル暗号化を実施するときにも有用である。R.Cramer, I.Damgrd, B.Schoenmakers著、「Proofs of partial knowledge and simplified design of witness hiding protocols」(Advances in Cryptology CRYPTO'94, Lecture Notes in Computer Science, 174-187頁、Springer-Verlag、ベルリン、1994年)の、一般的なブールの証明（boolean proof）手法も、同じ特性を有する証明を構築するために使用することができるが、結果的に証明のサイズ(複雑さ)は入力シーケンスのサイズでは2次元またはそれよりも劣ることとなる。
【０００７】
後述するプロトコルまたは方法によっても、K.Sako, J. Kilian著、「Receipt-free mix-type voting scheme- A practical solution to the implementation of a voting booth, Advances in Cryptology EUROCRYPT '95, Lecture Notes in Computer Science」Springer-Verlag, 1995年で使用されたような、カットアンドチューズ手法のいくつかの利点が得られる。この手法では、証明のサイズは、すべての参加者を満足させることを要求される証明者の不正行為を行う確率に依存する。本発明に記載のシャッフルプロトコルでは、この不正行為の行われる確率は、kをシャッフルされるべき要素数とし、qをそれらの要素が暗号化される
【０００８】
【数２】
【０００９】
の部分群のサイズとすると、基本的にk/qである。K.Sakoの論文では証明のサイズの分析は行われていないが、同様に不正行為の行われる確率を低くするためには、本発明で提供する証明のサイズよりも数桁大きくする必要があると考えられる。(さらに、K.Sakoのプロトコルが非対話式に実施される場合、不正行為を行う確率は極めて小さく選択されなければならない。何故ならば、悪意のある参加者が、徹底したサーチにより偽造証明を生成するため、多量のオフライン計算を使用する可能性があるからである。これは、当然ながら、上記プロトコルではこの通りであり得るが、確率k/qは、kとqのすべての現実的な値に関して十分小さいことは確実である。)
【発明の開示】
【発明が解決しようとする課題】
【００１０】
結果的に普遍的に検証可能となる選挙プロトコルのコンテクストにおいて見るとき、現行方式の利点はさらに明確になる。K.Sakoにおいて、各投票者は、実際に票を投じる前に各「集計センター」と連続して対話する必要がある。このような理由から、近い将来、大規模な公共セクタの選挙のために有効な実施がなされる可能性は低いと考えられる。反対に、後述するプロトコルでは、純粋に作表の目的で選挙終了時にすべてのオーソリティを参加させる(場合によっては、基本的な選挙パラメータの作成は除く)。
【課題を解決するための手段】
【００１１】
この素晴らしい特性は、R.Cramer, R.GennaroおよびB. Schoenmakersの論文に記載の洗練された準同形選挙プロトコルにも見られる。しかし、このプロトコルは、「nの中のm(以下)を選択せよ」という簡素なタイプの質問を有する投票に適用できるだけである。これは効果的に、投票者が優先順位で回答を示すことが要求され、質問項目はその優先順位に従って作表されることとなる、「記入式」応答、並びに「比例タイプの」質問を除外する。R.Cramer, R.GennaroおよびB.Schoenmakersスキームの欠点は、これに比べて若干重要度は低いが、投票データサイズを大幅に拡張すること、および、投票者に「妥当性証明」を要求することである。この証明によると、投票データのサイズは約1桁だけ拡張され、実用的な観点からは魅力的ではない。なぜなら、投票者のコンピュータで専用コードが実行していることが前提とされるからである。
【００１２】
このプロトコルは後述するが、Chaum-Pedersen(チョム-ペダーセン)証明のシーケンスと基本的な算術演算だけで構成されている。したがって、これは、容易に実施される。
【発明を実施するための最良の形態】
【００１３】
(詳細な説明)
図面では、同一またはほぼ同一の要素または動作は同一の参照番号で示す。いかなる特定の要素または動作の説明をも容易に識別するために、参照番号の1つまたは2つ以上の最上位桁は、その要素が最初に紹介された図番を示している(例えば、要素204は最初に図2で紹介され、図2に関して説明されている。)。
【００１４】
本発明に設けられている表題は便宜上のみのためのものであり、請求の範囲に記載の発明の範囲または意味には必ずしも影響を与えるものではない。
【００１５】
1.概要
以下で詳述するのは、一連の要素、例えば離散対数形式またはk入力エルガマル暗号化による公開鍵の入力シーケンスを「検証可能にシャッフルする」ための暗号化プロトコルであり、これらはセキュリティ保護された普遍的に検証可能な複数オーソリティ選挙スキームに応用例を持つ。k入力エルガマル暗号化の場合、シャッフル演算の出力はkエルガマル暗号の別のシーケンスであり、その各々は入力された暗号の中の正確に1つを再暗号化する(すなわち、同一のクリアなテキストを正確に暗号化するエルガマル対)が、出力の中の要素の順序は秘密に保持される。(適用されるべき要素の並べ替えおよび使用される暗号化鍵を選択する)「シャッフラ」にとって、入力から出力を計算することは些細なことではあるが、その構築は重要である。なぜなら、任意のベリファイアによってチェックされる可能性のある出力シーケンスのための正確さについてのリニアなサイズの証明(すなわち、請求された形式の証明)が提供されるからである。証明プロトコルのセキュリティは、関係式loggx = loghyに対するChaum-Pedersenプロトコルのそれと同じであり、使用される選挙の応用例に関し、これで十分である。
【００１６】
以下の説明では、本発明の実施形態を完全に理解するための具体的な詳細、および実施可能な説明が提供される。しかし、当業者ならば、本発明はこれらの詳細なくしても実施可能であることが理解されるであろう。他の例においては、本発明の実施形態の説明を不必要に不明瞭化することを避けるため、周知の構造および関数は詳細に図示または説明しない。
【００１７】
以下に提供される詳細な説明の大半は、上記の仮出願で明示的に開示されている；追加資料の多くは、そのような仮出願に提供された詳細な説明に固有のものとして関連技術の精通者に理解されるものであり、あるいは周知のものである。関連技術の精通者は、仮出願に提供された詳細な説明に基づいて本発明の態様を実施することができる。
【００１８】
本発明で使用される数学的表記法の多くは、関連技術の精通者には容易に理解することができるが、当技術分野に精通していない技術者のために以下のように定義して説明する。これらの定義は簡略ではあるが、当技術分野に全般的に精通していない技術者が、本明細書に記載の詳細な説明に基づいて本発明の実施態様をさらに完全に理解するのに役立つであろう。これらの定義は、全体として(特許請求の範囲を含めて)本発明の説明によってさらに定義されるものであり、これらの定義にだけよるものではない。
【００１９】
図1-5は、本明細書に記載の詳細な説明に加えて、当事者(例えば、投票者)とベリファイアの間(または、証明側当事者と検証側当事者の間)のプロトコルを説明する。これらの当事者によって実行される動作は、流れ図のボックスに共に分類される。一般に、ボックス内の各行のテキストまたは方程式は、計算、情報の伝送、あるいは記憶または検索関数などのステップを説明している。このような流れ図は1行ごとに、また、ボックスごとに読まれる。
【００２０】
本発明で一般に使用される「当事者」という用語は、エンティティを示しているが、このプロトコルの下で、ステップまたはステップの集合を実行するエージェントとすることができる。この用語はまた、これらステップの一部またはすべてを実行する手段または方法のことを言う場合もある。したがって、デジタル論理回路中の適当ないかなる構成の下でも、プロトコルの一部またはすべての部分を実行することができる。例えば、プロトコルの下の任意のステップまたはすべてのステップは、パーソナルコンピュータなどの汎用コンピュータだけでなく、組み込み型または専用の組み合わせ論理装置、またはいかなる種類の適切にプログラムされたマシン乃至マイクロプロセッサによっても、以上の装置またはマシンが必要な処理ステップ、ストレージ、入力および出力などを実行する場合に限り、実現することができる。
【００２１】
記号「∈R」は、一般に、略均一で独立した(ランダムな)確率分布に従って、右側の集合から左側の1つまたは複数の数字が選択されることを示している。実際、場合によっては付加的な事後処理または決定論的擬似乱数ジェネレータと共に、物理的な乱数ジェネレータを使用することができる。乱数を生成する方法は、関連技術の精通者には周知である。
【００２２】
記号「Π」および「Σ」は、それぞれインデックス付きの積と和を示す。
【００２３】
記号「Zp」は整数0からp-1の数の集合、またはpを法とする整数の環を示す。環Zpでの要素の加法および乗法はpを法として定義される。
【００２４】
記号「∈」は、左側の要素が右側の集合の構成要素または要素であることを示している。
【００２５】
記号「⊂」は、左側の集合が右側の集合の部分集合であること、すなわち左側の集合が右側の集合に含まれることを示している。
【００２６】
角括弧記号(すなわち、「<>」)は、それらに挟まれた1つまたは複数の項が所与の群または整数の環(例えば、環Zp)の部分集合によって生成された部分群であることを示している。部分群は、これもまた同じバイナリオペレーション下の群である別の群(または環)の部分集合である(例えば、整数は加法下の実数の部分群であるが、nを法とする整数は、演算が別に定義されるので、それらの部分群ではない。
【００２７】
以下では、別途明示しない限り、公知のように、nは正の整数であり、pとqは素数の整数である。算術演算は、モジュラ環Zp(またはZnである場合がある)で実行され、g∈Zpは(素数の)乗法の階数qを有することになる。(したがって、単にq|(p-1)である)。各証明プロトコルでは、Pは証明者(シャッフラ)でありVはベリファイア(監査役)である。
【００２８】
後述する一実施形態は、Zp(エルガマル)暗号システムを使用するが、楕円曲線暗号システムと、一般群下の暗号システムを使用することもできる。このような暗号システムは、非対称暗号システムに対する公開鍵を使用する。公開鍵システムは、所謂一方向性関数と落し戸関数を使用する。「一方向性関数」とは出力を計算するのは比較的容易だが、その逆関数は計算することが遥かに困難な関数のことである。例えば、ベキ関数は等しい因数の数の積を計算することは容易であるが、数量の根を探す逆演算はより複雑である。「トラップドア」関数は一方向性関数と類似しているが、何らかの追加情報が入手できない限り、逆関数は極めて困難である。この追加情報は、通常、投票者などの当事者によって保持される「公開鍵」である。
【００２９】
下記の方法およびプロトコルは、離散対数に対するChaum-Pedersenの等式(equality)の証明を頻繁に使用する。g、X、h、Y ∈ Zpの場合、これは関係式
【００３０】
logg X = logh Y (1)
【００３１】
に関する知識の証明である。
【００３２】
ゼロ知識であることは知られていない。しかし、公正なベリファイアに対してはゼロ知識であることが知られているが、これは、Fiat-Shamirヒューリスティックによってベリファイアを実施する、主要な応用例にとっては十分である。
【００３３】
「ゼロ知識証明」では、投票者または証明側当事者は、秘密のノリッジを証明することができるが、使用している情報が何であれ、ノリッジのその証明の伝達する際に検証側当事者にそれを露出することはない。単一ビットの情報、すなわち、証明側当事者が実際にその秘密を知っているということだけが伝達される。換言すると、投票者と検証するオーソリティはメッセージを交換するが、投票者の目的は、票の各質問に投票者がどのように投票したか、または一連の要素がどのようにシャッフルされたかを露出することなく、主張が真実であることをベリファイアに確信させることであり、その主張とは、例えば暗号化された投票または、投票または要素のシャッフルされたシーケンスは完全であり正確であるというような主張である。このようなゼロ知識証明の下では、各投票者または証明側当事者は、効果的に、自分の秘密鍵を有する人物だけが生成することのできる特定の数を生成する。ベリファイアまたは認証する当事者は、次いで、それぞれの計算された数が本当に周知のアルゴリズムで生成され、それによって投票者を認証すること、および、投票者の電子投票が完全かつ正確であるかまたは許容される選択と制約に関し「良好に形成されている」ことを確認し、あるいは一連の要素が(シャッフルされ暗号化された以外に)変更されていないことを確認する。
【００３４】
定義1
上記のChaum-Pedersen証明の一例は、
【００３５】
CP(g,X,h,Y)
【００３６】
によって示される。
【００３７】
定義2
固定された
【００３８】
【数３】
【００３９】
が<g>x<g>上のバイナリオペレータの場合、すべてのx、y ∈ <g>に対する
【００４０】
【数４】
【００４１】
によって定義された環の部分集合によって生成された部分群を示す。あるいはこれに替えて、すべてのa、b ∈ Zqに関する
【００４２】
【数５】
【００４３】
である。加法および乗法に使用されるインデックスを付ける規則に従って、
【００４４】
【数６】
【００４５】
の表記法も使用する。
【００４６】
このオペレーションを、本発明では対数乗法基数gと称する。
【００４７】
以上の定義における各々の表記法では、下付き添え字gの値が前後関係から明らかな場合は、これを省略することができる。本発明で一般に使用するように、「バイナリオペレータ」とは入力として集合から2つの要素をとり、1つの要素を戻すような集合で定義されるオペレータを意味する。
【００４８】
注意1
Chaum-Pedersen証明では、h = gSであり、かつその常用対数がu = loggX = loghYである場合、CP(g、X、h、Y)は明らかに関係式
【００４９】
【数７】
【００５０】
を証明してもいることに注意されたい。
【００５１】
注意2
上記の証明は、明らかにsに関してゼロ知識である。これは証明者が、証明を構成するためにこの値を知る必要は全くないからである。
【００５２】
詳細な説明の以下の部分で非常に多く使用されるので、以下のよく知られた結果のコレクション(collection)に注目されたい。
【００５３】
補助定理1
f(x)∈Zq[x]を次数dの多項式とする。この場合、d以下の値z1,．．．zd∈Zqがあり、したがって、f(zi) = 0である。
【００５４】
系1
f(x), g(x)∈Zq[x]を、f≠gとして、次数d以上の2つの多項式とする。この場合、d以上の値z1,．．．zd∈Zqが存在し、したがって、f(zi) = g(zi)である。
【００５５】
系2
f(x), g(x)∈Zq[x]を、f≠gとして、次数d以上の2つの多項式とする。c∈RZq、(cはZqからアトランダムに選択された)とすると、以下の確率が得られる。
【００５６】
【数８】
補助定理2
【００５７】
【数９】
【００５８】
をZqに亘る標準的なk次元のベクトル空間とし、
【００５９】
【数１０】
【００６０】
をv≠0に固定する。
【００６１】
【数１１】
【００６２】
がアトランダムに選択されると、
【００６３】
【数１２】
【００６４】
となる。
【００６５】
2.反復対数乗法の証明
この節の以下の部分で、すべての対数乗法は、固定された要素gに関して計算されるので、表記法の下付き添え字は省略される。以下の問題は、後に出て来るシャッフル証明の基礎となるものである。
【００６６】
反復対数乗法問題:2つのシーケンス
【００６７】
【数１３】
【００６８】
と、
【００６９】
【数１４】
【００７０】
は公然と知られている。証明者Pはすべてのiに関するui=loggXiおよびvi=loggYiも知っているが、これらはベリファイアVには知られていない。Pは、秘密対数uiとviに関する情報を露出せずに、関係式
【００７１】
【数１５】
【００７２】
をVに確信させることが要求される。
【００７３】
直観的に、注意1を考慮するとこの問題は簡潔である。証明者はk Chaum-Pedersen証明の2つのシーケンスを構築して、Vに、
【００７４】
【数１６】
【００７５】
の値と、
【００７６】
【数１７】
【００７７】
の値の両方を確信させることができ、次いでVはそれらの2つの値が同一であるとチェックすることができる。すべてのXiとYiがランダムかつ独立であることが知られている場合、このことはuiとviとを秘密に保持する目的で受け入れることができ、本発明の一実施形態で実施することができる。しかし、このプロトコルは、中間対数乗法に加え、V自身では計算することができない一部の情報、すなわち
【００７８】
【数１８】
【００７９】
の値を露出することは明らかである。このプロトコルを強化するために、上述の実施形態と以下で詳述される方法はある程度のランダム性を導入し、基礎となるChaum-Pedersenプロトコルよりも多く情報を漏洩しないことを保障する。
反復対数乗法証明:
1.Pは秘密裏に、k+1個の値
【００８０】
【数１９】
【００８１】
をランダムかつ独立に生成し、指数のベキにあげる値
【００８２】
【数２０】
【００８３】
を露出する。
2. 1≦i≦kの各々に関して、Pは秘密裏にwi=riui/ri-1を計算し、
【００８４】
【数２１】
【００８５】
と、zi=wi/viを露出する。
3.Pは
【００８６】
【数２２】
【００８７】
をセットし、Vに対してPが露出する2つのChaum-Pedersen証明
【００８８】
CP(Ri-1,Xi,Ri,Wi) (3)
CP(Yi,gi,Wi,Zi) (4)
【００８９】
を構築する。これら2つの共になされたChaum-Pedersen証明では、別個に行われて各々から露出される情報以上に秘密に関する情報を露出する可能性はない。これを理解するキーは注意2である。第1の証明はri/ri-1に関してゼロ知識であるが、ui/ri-1に関しては、公正なベリファイアだけがゼロ知識である。しかし、第2の証明はri,ri-1とuiに関しゼロ知識である。これは、証明者さえも、証明を生成するためにそれらの値を知る必要がないからである。しかし、もちろん、露出されたziからこれらの値に関する情報の一部を、viに関して一部の情報が知られる場合だけ、得ることができる。不正なベリファイアによってこのようなことが起こる可能性があるかどうかは知られていないが、ベリファイアが公正な場合は起こらない。これは、後述する実施形態と応用例でも同様である。
【００９０】
明らかに商ri/ri-1はすべて均一に分配されて独立しているので、値zi自体は、uiとviに関していかなる情報もそれら自体によっては露出しない。
4.Vは
【００９１】
【数２３】
【００９２】
であることをチェックし、各Chaum-Pedersen証明をチェックする。
5.Vは最終的に
【００９３】
【数２４】
【００９４】
を評価し、
【００９５】
【数２５】
【００９６】
であることをチェックする。
【００９７】
注意1を参照し、単純にその指数を乗算することによって、このプロトコルが反復対数乗法問題を解決することは、容易に確認することができる。偽造証明の確率は、1つまたは2つ以上のChaum-Pedersen証明が偽造された確率だけ上に有界である。これらの確率のそれぞれは1/qである。したがって、偽造される証明の全体的な確率は2k/qだけ上に有界である。
【００９８】
後で明らかになる理由から、この方法に対しては、実際上次の別の反復対数乗法問題はより有益である。
【００９９】
スケールされる反復対数乗法問題:元の問題と同様に、2つのシーケンス
【０１００】
【数２６】
【０１０１】
と、
【０１０２】
【数２７】
【０１０３】
は公然と知られており、すべてのiに関するui=loggXおよびvi=loggYiはPに知られているが、Vには秘密である。さらに、定数c∈ZqはPにだけ知られているが、cのコミットメントであるC=gcはVに知られることになる。Pは、秘密対数ui,vi,およびcに関する情報を露出せずに、関係式
【０１０４】
【数２８】
【０１０５】
をVに確信させることが要求される。
【０１０６】
スケールされる反復対数乗法証明:この証明は、元の値に対するより小さい変分しか必要としない。4のChaum-Pedersen証明は、類似の証明
【０１０７】
CP(Yi,Ci,Wi,Zi) (6)
【０１０８】
で置き換える必要がある。
【０１０９】
3.簡素なKシャッフル
本発明で構築した第1のシャッフル証明は、条件の限定的な集合を必要とする。これは2つの理由から有用であろう。第1に、これは、後で出てくる、より一般的なシャッフル証明の基本的なビルディングブロックとなる。偶然にも、これは第2の重要な目的にも役立つ。この証明の一例を、特定の置換を効果的に「コミットする」ために構築することができる。Zpの要素のタプル上でシャッフルを実施する必要がある場合に、これは重要となる可能性があるが、これはまさしく投票応用例で必要とされるものである(「タプル」はシーケンスまたは順序集合のことである。例えば、5-タプルまたは5倍は5つの要素をもつ順序集合であり、k-タプルは不特定数の構成要素による有限の順序集合のことである。)。
【０１１０】
簡素なkシャッフル問題:k要素の2つのシーケンス、ZP,X1,．．．XkおよびY1,．．．Ykは公然と知られている。証明者Pもui,=loggXiおよびvi=loggYiを知っているが、それらはベリファイアVには知られていない。さらに、定数c∈ZqはPだけに知られているが、cのコミットメントであるC=gcはVに知らされる。Pは、πまたは秘密cに関する情報を露出せずに、すべての1≦i≦kに関して、
【０１１１】
【数２９】
【０１１２】
という特性を有するある種の置換π∈ΣkがあることをVに確信させることが要求される。関数πは入力される要素の集合を置換された出力される要素の集合にマッピングするための関数に対応する。
【０１１３】
簡素なkシャッフル証明:この証明の構築は、前節および系2を考慮すると略自明である。
1.Vはランダムなt∈Zqを生成し、それをチャレンジとしてPに与える。
2.PはT=gt(また知られているV)とS=Tc=gctとを計算する。
3.PはChaum-Pedersen証明CP(g,C,T,S)を生成し、これをVに露出する。
4.Pは公然と(すなわち、Vによってチェックされる)Ui=T/XiおよびVi=S/Yiの値を計算する。注意:UiおよびViは、系2の表記法によって行内にさらに入るように選択される。一実施形態では、除法は計算上は乗法よりも費用が掛かるので、この方法はUi=Xi/TおよびVi=Yi/Sによってプロトコルを実施する。
【０１１４】
証明者は、シーケンス
【０１１５】
【数３０】
【０１１６】
と、
【０１１７】
【数３１】
【０１１８】
および、コミットメントCに対してスケールされる反復対数乗法証明を実行する。スケールされる対数乗法証明をUおよびVの上でチェックすることによって、ベリファイアは、要素Xの初期入力シーケンスとシーケンスYの間の所望の関係が(系2に基づいて)保たれることを保障する。
【０１１９】
スケールされる反復対数乗法証明が偽造されるか、またはS=Tcの単一の証明が偽造されるか、あるいはVが系2の除外集合からcを偶然に選択した場合、偽造された証明が生成される可能性がある。したがって、偽造された証明の全体的な確率は(3k+1)/qだけ上に有界である。本発明に記載のシャッフルプロトコルの下で提供される証明に関するさらなる情報は、上記で参照した米国仮出願明細書に記載されている。
【０１２０】
一般に、ある応用例では簡素なkシャッフルで十分かもしれない。項目をシャッフルするには、結果的に生じたY要素を生成したのは、元のX要素のうちのいずれであるかを露出せずに、一連の出力要素Y1からYkまたはそれらのシーケンスが、定数暗号化情報に基づいて、元の要素X1からXkまたはそれらの入力シーケンスから導出されたことが確実な場合、各々暗号変換(例えば、累乗法)を使用する必要がある。さらに、十分なレベルの証明のためには多数の反復を必要とする先行技術で周知の、カットアンドチューズタイプの妥当性証明などの、煩わしい妥当性の証明を使用することも必要とせずに、個々にこのようなシャッフルを実現することが希望される。その代わりに、秘密累乗法値cに基づく一連のk独立Chaum-Pedersen証明が本明細書に記載されたように使用される。
【０１２１】
4.一般的ｋシャッフル
シャッフラPがすべての元の指数s1,．．．,skを知る必要があるということが、簡素なkシャッフルプロトコルの明らかな限界である。多くの応用例では、これはこの通りではない。次のステップは、この制約を解消することである。
【０１２２】
一般的ｋシャッフル問題:Zp,X1,．．．,XkとY1,．．．Ykのk要素の2つのシーケンスは、公然と知られている。さらに、定数c∈ZqはPだけに知られているが、cのコミットメントであるC=gcはVに知らされている。Pは、πまたは秘密cに関する情報を露出せずに、すべての1≦i≦kに関して、
【０１２３】
【数３２】
【０１２４】
という特性を有するある種の置換π∈ΣkがあることをVに確信させることが要求される。
【０１２５】
一般的ｋシャッフル証明:この証明は、ベリファイアによって「適切にランダム化された」簡素なkシャッフルと、補助定理2の適用から構築される。
1.Pはシーケンス
【０１２６】
【数３３】
【０１２７】
をランダムに、かつ独立して生成し、シーケンス
【０１２８】
【数３４】
【０１２９】
を露出する。
2.Vは別のシーケンス
【０１３０】
【数３５】
【０１３１】
をランダムに、かつ独立して生成し、これをチャレンジとしてPに与える。
3.Pは公然と
【０１３２】
【数３６】
【０１３３】
をセットし、秘密裏に
【０１３４】
【数３７】
【０１３５】
をセットする。ベリファイアが生成した値を加えるように証明者に要求することによって、証明者が特定の秘密(指数)を選択することを防止し、そうでない場合は暗号の堅固さを保障するために役立つ。
4.Pはシーケンス
【０１３６】
【数３８】
【０１３７】
上で、別のコミットメントD=gd(異なる秘密指数)と逆置換π-1によって簡素なkシャッフルを構築し、簡素なkシャッフルの節にあるように、結果的にシーケンス
【０１３８】
【数３９】
【０１３９】
および対応する証明を生じる(Viは公開だが、viはPに対して秘密であることを想起されたい。)。
5.Pは公然と
【０１４０】
【数４０】
【０１４１】
および
【０１４２】
【数４１】
【０１４３】
をセットし、Chaum-Pedersen証明
【０１４４】
CP(g,Vi,Xi,Ai) (9)
CP(g,Ui,Yi,Bi) (10)
を露出する。
したがって、要素AおよびBのシーケンスは要素XおよびYの入力シーケンスに対応する。
6.値
【０１４５】
【数４２】
【０１４６】
【数４３】
【０１４７】
が公然と評価される。
7.PはChaum-Pedersen証明
【０１４８】
CP(D,A,C,B) (13)
を露出する。
【０１４９】
上記のステップ5-7は、証明者が元のデータを改ざんしていないことを保障するために役立つようにデータを留めておくことを証明者に効果的に要求する(これらのステップは、上記の簡素なシャッフルの説明とは異なる)。簡素なkシャッフル証明が偽造されるか、Chaum-Pedersen証明の1つが偽造されるか、補助定理2の除外集合からタプル(ui,．．．uk)が選択される場合だけ、偽造された証明が生成される可能性がある。したがって、偽造の全体的な確率は
【０１５０】
【数４４】
【０１５１】
だけ上に有界である。
【０１５２】
5.タプルのKシャッフル
関連技術の精通者ならば、前節で、簡素なシャッフルを選択することによって、証明される可能性のあった置換を基本的に「凍結した」ことが理解されるであろう。これによって、前節を、<g>の要素のkタプルのシャッフルまでどのようにして拡張すべきかを理解することが容易になる。k個のl-タプルのシーケンスをk×lの配列と考えると、すべてのシーケンスは同じ置換に従って置換されたが、各行は変更されずにあることを証明するために、単一の簡素なk-シャッフルを利用することができる。したがって、上述のkシャッフルは、k要素の配列の各シーケンスに1回ずつ、l(エル)回実行される(kシャッフルの各々はこの簡素なシャッフルを再利用する)。具体的には、これはエルガマル対のタプルまで拡張される。
【０１５３】
6.投票応用例
投票者の登録、票の形成および分配、票の記憶、および暗号化された電子投票を利用する選挙の実行に関する情報は、2000年3月24日出願の「Multi-Way Election Method and Apparatus」という名称の米国特許出願第09/535,927号明細書、2000年3月24日出願の「Electronic Voting Scheme Employing Permanent Ballot Storage」という名称の米国特許出願第09/534,835号明細書、2000年3月24日出願の「Method, Article and Apparatus for Registering Registrants, Such as Voter Registrants」という名称の米国特許出願第09/534,836号明細書、2000年11月22日出願の「Election System」という名称の米国仮出願第60/252,762号明細書、2001年2月20日出願、「Method and Apparatus for Detection and Correction of Compromised Ballots in Secret, Remote, Electronic Voting Systems」という名称の米国仮出願第60/270,182号明細書、および2001年3月2日出願、「Information Theoretically Anonymous Signatures with Discrete Log Security」という名称の米国仮出願第60/272,883号明細書に記載されている。
【０１５４】
一実施形態では、投票は、
【０１５５】
【数４５】
【０１５６】
という形式のエルガマル対 (または、さらに多くのデータが必要とされる場合は、それらの対のシーケンス) として提供される。ここで、mは投票者の選択した(本明細書に記載の)ある種の標準符号化、αiは投票者によって秘密裏に生成され、hはディーラーのいない秘密共有方式によって構築された公開パラメータである(例えば、T.Pedersen著、「A threshold cryptosystem without a trusted party, Advances in Cryptology EUROCRYPT '91, Lecture Notes in Computer Science」522-526頁。Springer-Verlag、1991年を参照のこと)。投票所が閉まると(投票が終了すると)、オーソリティの独立したコレクションが連続して票をシャッフルする。最後のシャッフルを出力する際、暗号化された票の最後のコレクションが、この閾値方式に従って暗号解読され、明確なテキストの票決が通常の選挙規則によって全景で作表される。
【０１５７】
連続的なシャッフルに参加するオーソリティは、任意の数でよく、選挙の秘密鍵を分担して保持する者とは完全に異なっていてもよい。シャッフリングするオーソリティのすべてが共謀している場合、最後に暗号解読される票のシーケンスは、提出された票の元のシーケンスと一致することだけが可能である。これは、これらの置換の各々が完全に任意だからである。
【０１５８】
各シャッフルは以下の要領で個々のオーソリティによって実行される。
1.βiは、秘密裏に、ランダムに、かつ独立して選択される。
2.各投票
【０１５９】
【数４６】
【０１６０】
は、
【０１６１】
【数４７】
【０１６２】
と、順次、置き換えられる。Chaum-Pedersen証明はこの秘密を露出せずに公開される。
3.秘密指数cによるシャッフルが、結果的に暗号化された投票に関して実行される。
4.ステップ1-2が反復される。
5.この時点で、暗号化されたメッセージは元のメッセージのc乗である。これは、各投票の各座標を1/c乗することによって容易に決めることができる。この演算のChaum-Pedersen証明は等しく容易に提供され、したがって、gとC=gcの役割を単純に逆転させることによってベリファイアを納得させながらも、cを秘密に保つ。
【０１６３】
上記のステップ1および2は、入力データをランダム化することを助け、シャッフリングする前に票の間の関係を選択するなど、入力データを変更することを回避する。Chaum-Pedersen証明は、このランダム化のために追加された加算値が正確であることを保障する。代替実施形態では、ステップ1および2(およびステップ4)は省略される。
【０１６４】
7.セキュリティ保護されたメッセージ符号化
p-1が小さな素因数を有する場合、符号化されたメッセージに関する一部の情報が漏洩する可能性がある。これはシャッフルプロトコルでは問題ではなく、むしろ最初にmiを強力に暗号化する場合に問題である。これが心配するほど重大な問題かどうかは、符号化されるべきメッセージの期待値によって異なる。しかし、この問題は、符号化に特別な配慮をすることによっても解消することができる。各メッセージは、位数が大きな素因数だけを含んでいる部分群に投影することができる。本明細書に記載の大半の実施形態は、|<g>|が素数qである場合に限定されるので、p=2q+1の場合についてのみ議論する。しかし、これらの手法を拡張することによって、より一般的なケースを処理することができる。
【０１６５】
p=2q+1のビット長がbであるとすると、
【０１６６】
2b-1<p<2b
であり、したがって、
【０１６７】
2b-2≦(p-1)/2=q<2b-1 (15)
である。
【０１６８】
本発明では、すべてのメッセージmが、ビット長b-2以下であることを必要とされる。本発明では、各メッセージを標準のように(gα,hαm)として暗号化するのではなく、
【０１６９】
(gα,hα,m2)
として暗号化する。これは、すべてのメッセージは、
【０１７０】
【数４８】
【０１７１】
の順番2の部分群上への同一の自明な投影によって符号化されることを意味している。方程式15は、マップm→m2が定義域上で可逆であることを保障する。逆転させるには、(p-1)/2よりも小さな一意の平方根を取るだけである。したがって、実際のメッセージm2が一旦暗号解読されれば、元のメッセージmを回復するのは簡単なことである。
【０１７２】
8.適切なシステム
図1および以下の議論により、本発明の態様を実施することができる適切なコンピューティング環境の簡潔で一般的な説明が得られる。必須ではないが、本発明の実施形態は、汎用コンピュータ、例えばパーソナルコンピュータまたはウェブサーバによって実行されるコンピュータ実行可能命令、例えばルーチンの一般的なコンテクストで記述されるであろう。関連技術の精通者ならば、本発明の態様(小規模の選挙など)は、インターネット機器、ハンドヘルド装置、ウェアラブルコンピュータ、パーソナルデジタルアシスタンス(「PDA」)、マルチプロセッサシステム、マイクロプロセッサベースの、またはプログラム可能な家庭電化製品、ネットワークPC、ミニコンピュータ、携帯電話または移動電話、セットトップボックス、メインフレームコンピュータなどを含め、他のコンピュータシステム構成で実行することができることが理解されるであろう。本発明の態様は、特に本発明に記載の1つまたは2つ以上のコンピュータ実行可能命令を実行するようにプログラム、構成または構築された専用コンピュータまたはデータプロセッサで実施することができる。実際、本発明で一般に使用する「コンピュータ」という用語は、どの上記装置並びにどのデータプロセッサをも示す。
【０１７３】
本発明は、ローカルエリアネットワーク(LAN)、ワイドエリアネットワーク(WAN)またはインターネットなどの通信ネットワークを介してリンクされている遠隔処理装置によってタスクまたはモジュールが実行される、分散型コンピューティング環境で実行することもできる。分散型コンピューティング環境では、プログラムモジュールまたはサブルーチンは、ローカルメモリストレージとリモートメモリストレージの両方に配置することができる。本発明に記載の本発明は、磁気/光学読み取り可能/取り外し可能なコンピュータディスクなどのコンピュータ読み取り可能媒体に記憶または分配することも、チップにファームウェアとして記憶することも、また、インターネットまたは他のネットワーク(無線ネットワークを含めて)を介して電子的に分配することもできる。関連技術の精通者ならば、本発明に記載のプロトコルの部分は、対応する部分をクライアントコンピュータに常駐させながら、サーバコンピュータに常駐することができることが理解されるであろう。このようなプロトコルに特定のデータ構造とデータの伝送も、本発明の範囲内に含まれる。
【０１７４】
別途記載のない限り、図1の種々のブロックの構成および動作は従来のデザインである。したがって、これらのブロックは関連技術の精通者には容易に理解されるので、本発明ではさらに詳述する必要はない。
【０１７５】
図1を参照すると、システム100の適切な環境は、1つまたは2つ以上の投票者コンピュータまたはクライアントコンピュータ102を含むが、そのそれぞれは、コンピュータに、インターネットのワールドワイドウェブ部分106内のウェブサイトを含めてインターネットによってデータにアクセスし、データを交換することができるようにするブラウザプログラムモジュール104を含む。投票者コンピュータ102は、いずれも周知ではあるが図1には示さない、1つまたは2つ以上の中央演算処理装置または他の論理処理回路構成、メモリ、入力装置(例えば、キーボード、マイクロフォン、タッチスクリーン、およびポインティングデバイス)、出力装置(例えば、表示装置、オーディオスピーカー、およびプリンタ)、記憶装置(例えば、固定された、フロッピー(登録商標)および光学ディスクドライブ)を含むことができる。投票者コンピュータ102は、さらに、オペレーティングシステム、1つまたは複数のアプリケーションプログラム(例えば、ワードプロセッシングアプリケーションまたはスプレッドシートアプリケーション)などの他のプログラムモジュールを含むこともできる。図1に示すように、投票者1,2,3,．．．Nを表すN個の投票者コンピュータ102がある。
【０１７６】
インターネットまたはワールドワイドウェブ(「ウェブ」)106に接続されているサーバコンピュータシステム108または「投票収集センター」は、票の収集、記憶および他の処理の大半またはすべてを実行する。サーバコンピュータ108に接続されているデータベース110は、投票者コンピュータ102と、1つまたは複数の投票所コンピュータ112およびサーバコンピュータ108との間で交換されるウェブページとデータ(票およびシャッフル妥当性証明を含めて)の大半を記憶する。投票所コンピュータ112は、パーソナルコンピュータ、サーバコンピュータ、ミニコンピュータなどであり、インターネット106に接続されたコンピュータに即座にアクセスすることのできない市民または投票者が、本発明に記載のシステム下で電子的に投票できるようにするために、公共の投票所に配置されている。したがって、1つまたは複数の投票所コンピュータ112が公的な場所に配置されているか、または公共選挙で投票者にアクセス可能な場合、投票者コンピュータ102は、個々の投票者の家庭に配置することができる。投票所コンピュータ112は、1つのサーバコンピュータと、LANを介してそのサーバコンピュータに接続された複数のクライアントコンピュータまたは投票者端末を有するローカルエリアネットワーク(LAN)を含むことができ、それによって複数の投票者が同時に、または並行して投票することを可能にする。
【０１７７】
投票所コンピュータはさらに、Dallas Semiconductor社から供給される暗号法iButtonsなどのiButtonsを読むためのiButtonリーダーを含むこともできる。iButtonは、ステンレススチール缶に覆われた16mmのコンピュータチップであり、登録している投票者の署名などの情報を暗号化し暗号解読するために必須の高速算術計算用のマイクロプロセッサを含むことができる。さらなる情報は、http://www.ibutton.comで見ることができる。当然ながら、本発明に記載のコンピュータ読み取り可能媒体、無線周波数識別票(RFID)、1次元または2次元のバーコードまたは他のデータ収集装置、およびこれらに関連したリーダーなどの、iButton以外の他のデータ記憶装置を使用することができる。
【０１７８】
代替実施形態下では、会社役員や取締役の選出など、民間の選挙の状況ではシステム100を使用することができる。この実施形態下では、投票者コンピュータ102は、株主のラップトップコンピュータまたはデスクトップコンピュータであってよく、投票所コンピュータ112は選挙を実施している会社内(例えば、ロビー)に設置された1つまたは複数のコンピュータであってよい。したがって、株主は、会社に行って投票所コンピュータ112にアクセスして票を投じることができる。
【０１７９】
1つまたは2つ以上のオーソリティまたは組織コンピュータ114も、インターネット106を介してサーバコンピュータシステム108に接続されている。オーソリティコンピュータ114のそれぞれは、データベース110に記憶されている電子票を暗号解読するために必須のキーを保持する。閾値暗号化システムは、オーソリティの総数nの部分集合t(すなわち、t<n)が票の暗号解読に賛成することを必要としており、それによって、票の暗号解読にすべてのオーソリティが必要とされる必須条件が回避される。すなわち、閾値暗号化の目的は、群のn人の構成員間で秘密鍵sを共有することであり、事実上の部分集合Tが共同するときにメッセージを暗号解読することができるようにすることである。これが、(t,n)閾値暗号化システムである。プロトコルは、(1)その群間で共同してキーを生成し、(2)秘密鍵を再構成せずにメッセージを暗号解読するものと定義される。オーソリティコンピュータ114は、投票期間終了後にサーバコンピュータシステム108にオーソリティコンピュータ114の暗号解読の分担を提供することができ、その結果、サーバコンピュータシステムは票を暗号解読してその結果を総計することができる。
【０１８０】
さらに、記載の実施形態下では、オーソリティコンピュータの各々は、本発明に記載のように1回の票のシャッフルを実行する。各シャッフルに関して、各オーソリティコンピュータはシャッフル妥当性証明を生成し、そのシャッフル妥当性証明は、暗号化されてサーバコンピュータ108に転送されるか、オーソリティコンピュータによってローカルに記憶することができる。代替実施形態では、オーソリティコンピュータのさらなる集合が提供される。ここで、オーソリティコンピュータの1つの集合は暗号化された票をシャッフルしてシャッフル妥当性証明を生成し、一方、オーソリティコンピュータの第2の集合はその票を暗号解読するために鍵の分担を使用する。
【０１８１】
オーソリティコンピュータ114に類似の、1つまたは2つ以上の任意に選択可能なベリファイアコンピュータ130を提供することもできる。ベリファイアコンピュータは、当該選挙が損なわれていないことを検証するために、選挙の写しを受け取ることができる。例えば、ベリファイアコンピュータは、本発明に記載のように、オーソリティコンピュータのそれぞれからシャッフル妥当性証明を受け取ることができる。ベリファイアコンピュータは、選挙の後で検証を実行することができ、インターネットに接続されている必要はない。実際、検証は、本発明に図示または記載の他のコンピュータによって実行することもできる。
【０１８２】
サーバコンピュータ、ベリファイアコンピュータまたはオーソリティコンピュータが投票者登録プロトコルを実行することも、別個の登録コンピュータ(図示せず)を提供することもできる。登録コンピュータは、指紋データ、声紋データ、デジタル画像比較、および関連技術の精通者に周知の他の技術など、登録者の生物測定データを読み取るための生物測定リーダーを含むことができる。投票者の登録と、検証可能なシャッフルで使用するための匿名証明書の発行については後述する。
【０１８３】
サーバコンピュータ108は、サーバエンジン120、ウェブページ管理構成要素122、データベース管理構成要素124、並びに図示しない他の構成要素を含む。サーバエンジン120は、標準の機能の他に、電子投票プロトコルの部分を実行する。暗号化プロトコルはサーバコンピュータに記憶することができるが、このようなプロトコルの部分は適切な定数と共にクライアントコンピュータにも記憶される。実際、上記プロトコルは、磁気/光学読み取り可能/取り外し可能なコンピュータディスクなどのコンピュータ読み取り可能媒体、半導体チップ(例えば、EEPROM)に記憶されるマイクロコードに記憶し、および分配することも、インターネットまたは他のネットワークを介して電子的に分配することもできる。関連技術の精通者ならば、プロトコルの部分はサーバコンピュータに常駐するが、対応する部分はクライアントコンピュータに常駐することが理解されるであろう。上記プロトコルに特有なデータ構造およびデータの伝送も、本発明の範囲に含まれる。したがって、サーバエンジン120は、権限を付与された投票者に対するすべての必要な票の伝送、票の収集、票の検証(例えば、デジタル署名をチェックし、票に含まれる妥当性の証明の検証を通すこと)、投票の集計、票の暗号解読および/または投票の作表を実行する。代替実施形態下では、サーバエンジン120は、データ収集センターとしてすべての電子投票を収集するだけである。電子投票は、次いで記憶されて、票をシャッフルし、投票集計を暗号解読して選挙結果を提供するためのツールと共に、自治体などの選挙を管理する第三者機関に提供される。同様に、シャッフル妥当性証明などの選挙検査情報は、ローカルに記憶することも、自治体または他の機関に提供することができる。
【０１８４】
ウェブページ構成要素122は、後述するように、電子投票ボックスウェブページなどのウェブページの作成と表示、またはルーティングを取り扱う。投票者およびユーザは、http://www.votehere.netなどのサーバコンピュータ108に関連付けられたURL、または、自治体のURLなどの選挙に関連付けられたURLによってサーバコンピュータ108にアクセスすることができる。自治体は、サーバコンピュータシステム108を直接的に主催または運営したとしても、そのような受け取った電子投票を、サーバコンピュータシステムを操作することのできる第三者の投票権限付与者に転送することもできる。URLまたは本発明で示したリンクまたはアドレスはいかなる資源ロケータであってもよい。
【０１８５】
ウェブページ管理プロセス122およびサーバコンピュータ108は、権限を付与された投票者またはシステム管理者などの権限を付与された人物だけがアクセスすることのできるセキュリティ保護されたセクションまたはページを有することができる。サーバコンピュータ108は、そのようなユーザを認証するために、セキュアソケットレイヤ(「SSL」)およびトークンまたはクッキーを使用することができる。実際、小規模な選挙または不正行為の確率が低い(または、不正行為の結果が比較的重大でない)選挙の場合、システム100は、上記の特許出願明細書に記載の複雑な電子暗号化された票を使用するのではなく、後述するような投票を収集し記憶するための簡素なネットワークセキュリティ対策を使用することができる。ユーザを認証する方法(パスワードの使用によるなど)、セキュリティ保護された伝送接続を確立する方法、およびセキュリティ保護されたサーバとウェブページを提供する方法は、関連技術の精通者には周知である。
【０１８６】
この選挙方式およびシステムは、それぞれの掲示物がデジタル署名され、1つも消去されることのない「掲示板」を使用する。K.Sako,J.Kilian,R.およびCramer, R.Gennaro, B.Schoenmakersの論文を参照されたい。この掲示板はウェブサーバとして実施される。「投票箱」はこの掲示板上に常駐し、すべての暗号化された票を保持する。ウェブサーバのデータを、追記型光ディスク(WORM)永久記憶媒体または類似の装置に書き込むことによって、消去を防止することができる。このような掲示板システムに関するさらなる詳細は、「Electronic Voting Scheme Employing Permanent Ballot Storage」という名称の、米国特許出願第09/534,836号明細書に記載されている。
【０１８７】
本発明の一実施形態はコンピュータを接続するためにインターネットを使用するように本発明には記載されているが、他の代替実施形態も可能であることに留意されたい。例えば、本発明の態様は、スタンドアロンコンピュータによって使用することができる。本発明の態様は、どのような相互接続されたデータ処理マシンによって使用することもできる。本発明に記載の方法またはプロトコルの態様を実施するために、このようなマシンでは、ブラウザを使用せず、クライアントソフトウェアを使用することができる。
【０１８８】
9.選挙の実施例
一般的k-シャッフルプロトコルの一応用例は、電子投票の分野にある。選挙を「普遍的に検証可能」にするために、提出された票は最初に有効な(すなわち、登録された)投票者に絶対的に接続可能である必要がある。票は、「開票」が可能となる前に、検証可能プロセス、すなわち分離プロセスにおいて偽票が提出されることを許可しないことによって何とかして「署名と分離される」必要がある。
【０１８９】
本発明で提示されるプロトコルは、選挙結果に種々の関心を抱くN人の「作表オーソリティ」の集合に依存している。
1.このプロトコルは、完了されるべき作表のために、少なくともt人のオーソリティが正当に振舞わなければならない閾値スキーム(scheme)である。(パラメータtは、任意の値1≦t≦Nになるように選挙前に選択することができる)。したがって、具体的には、オーソリティが自分のシャッフルをいかなる特定の順序で完了することも必須ではなく、また、すべてのオーソリティが参加することさえも必須ではない(特殊なt=Nの場合を除いて)。
2.すべてのオーソリティが共謀したとしても、選挙結果を検証することを希望する外部の監査役によって見つからずに、偽の選挙結果を生成することはできない。
3.個々の投票のプライバシーは、少なくともt人のオーソリティが共謀することによってのみ侵害される可能性がある。
【０１９０】
このプロトコルは以下のように進捗する。
第1:選挙を開始する
1.オーソリティは、まず選挙パラメータについて一致している。
(a)どのような選挙にも必須のパラメータ:有権者の集合、投票の質問、投票の回答、投票スタイル、投票所が開かれ、閉じられる時刻が含まれる。
(b)作表オーソリティの集合:作表オーソリティら自身(この群のオーソリティ数を示すために以下ではNを使用する。)
(c)閾値パラメータt
(d)シャッフルパラメータ1≦s≦t(s=tはそのままの選択)
(e)群Gおよび部分群ジェネレータg∈G(安全な暗号化を達成するために、|g|の素因数は大きくすべきだが、当然ながら、この要件はオーソリティら自身によって理解できるようになっている。)
(f)1つまたは複数の応答に対する標準「ビット符号化」(例えば、ASCII)と小さな「メッセージの重複」整数d≧1。メッセージの重複は、一致した各票の分割を意味し、票の出力形式(各投票の質問への応答をどこに配置するかを示す投票用紙のレイアウトと類似している)に対応する。通常、dは、投票の応答サイズを、収容できる限り小さく選択される。ほとんどの場合、d=1でも機能する。何故ならば、メッセージ重複はそのキーの長さによって判定されるからであり、また、十分に大きなキーの長さ(例えば、1024ビット)は適度な数の質問を有する大部分の票を収容することができるからである。
(g)オーソリティによって実行される(N,t)-秘密共有方式によって作成される群要素h∈<g>。(T.Pedersenの論文を参照のこと。
2.選挙パラメータに関して同意に達すると、オーソリティは全員がそれらに「署名」し、署名された票が、この署名されたパラメータの集合を表現したものとなる。
【０１９１】
第2:投票
1.選挙中(すなわち、「投票所が開いている」間)、各投票者Vは、1つまたは2つ以上の自分の応答を、選挙標準「ビット符号化」(選挙開始期間中にオーソリティによって合意され署名されたもの。上記参照のこと。)によって、メッセージのシーケンスm1,．．．,md∈Gに符号化する。(これに関しては以下でさらに記載する。)「メッセージの重複」dは別の選挙パラメータである(上記参照のこと。)。
2.Vは、暗号化のために、指数α1,．．．,αdを、0≦αj<|g|からアトランダムに個別に選択する。
3.Vは、特定の有権者に試行することによってその応答を認証するため、「暗号化された応答のシーケンス」
【０１９２】
【数４９】
【０１９３】
を、Vによって生成された「添付の」デジタル署名と共に「投票収集センター」に戻す。
4.Vによって提出されたデジタル署名により検証され、かつVが以前に票を投じていなかった場合、中央収集機関によって署名された受領書がVに対して発行される。この受領書は、特定の選挙において当該投票者からの投票が受領されたことを承認するが、(暗号化またはハッシュされた情報さえも)その票の内容に関する情報は含まない。この受領書は、当該投票者に対しても送信することができる。この受領書は、また、当該投票者の票が消失せず、また、悪意をもって削除されなかったことを確認するためにも役立つ。
【０１９４】
第3:結果を作表する
1.最初に、投票者の応答の集合は、それぞれが受領された票の応答の総数である各長さがNcastの2d個のシーケンスに配列される。各シーケンスは、標準の票応答形式の1つの座標に対応する(方程式16)。各シーケンスの項目は投票者によって順序付けられる。各投票者に割り当てられる指標は、一貫性のある限り重要ではない。このようにして、外部オブザーバーは、署名された票が、非常に簡素な方法で変換され、データレイアウトに正しい解釈を適用することによって、依然として署名され受領された応答の同じ集合を表していることを確認することができる。
2.任意の便宜的な順序で、sオーソリティのシーケンスはそれぞれに以下のステップを実行する。
(a)Sをシーケンスに現在入っているオーソリティとする。
(b)Sは、dNcast指数
【０１９５】
1≦βjl≦|g|1≦j≦Ncastおよび1≦l≦d
を別個にアトランダムに選択する。
(c)Sは、群要素
【０１９６】
【数５０】
【０１９７】
および
【０１９８】
【数５１】
【０１９９】
を計算する。さらに、中間Chaum-Pedersen証明が(g,gs(j,l),h,hs(j,l))上に生成される。
(d)Sは次いで、2d個の入力シーケンスを2d個の中間シーケンスに変換する。gαm形式のl(エル)番目の入力シーケンスのj番目の項目は、それにgs(j,l)を乗じることによって変換され、hαm形式のl(エル)番目の入力シーケンスのj番目の項目は、それにhs(j,l)を乗じることによって変換される。変換された項目はすべて同じ順序で維持される。
(e)Sは、ランダムな指数0≦c<|g|と、ランダムな置換πl∈ΣNcastを選択し、hs=gcをコミットする。
(f)Sは次いで、秘密パラメータcおよびπlを使用し、かつ、各一般的ｋ-シャッフルの基礎と同じ簡素なk-シャッフルを再利用して、その2d個の中間シーケンスのそれぞれで(k=Ncastとして)一般的ｋ-シャッフルを実行する。(これは、2d個のシーケンスのそれぞれが同じ秘密の「置換」を受けることを保障する。)
(g)(i)Sは、新しいランダムβによってステップ(d)を繰り返す。
(ii)各票の各座標を1/c乗し、この演算のChaum-Pedersen証明を提供する。このようにしてgとC=gcの役割を単純に逆転させることによってベリファイアを確信させながら、cを秘密に維持する。
(h)(この段階でSは中間シーケンスを明白に計算する必要はないことに留意されたい。それらは外部ベリファイアには後で必要となるが、出力は直接的に計算することができ、中間シーケンスは監査役の要求で構成することができる。しかし、セキュリティ保護の問題から、次のシャッフルを開始する前に監査役に検証を実行させることが要求される場合がある。)
3.次に、2d個のシーケンスのそれぞれの項目を、それらが形成された方法と同様の方法で結合することによって、シャッフルされた票が再構成される。
4.最後に、t人のオーソリティが、各シャッフルされた票で閾値暗号解読プロトコルを実行する。
【０２００】
一般に、作表フェーズは2つのサブフェーズを含む。第1に、作表オーソリティのT≦tの集合は、それぞれに順次、検証可能なk×dシャッフルを実行する(ここで、kは投じられた票の総数である)。各シャッフルからの出力シーケンスと証明は署名され、次の作表オーソリティに渡される。(各作表オーソリティは、その入力が署名のチェックおよび(前回の)シャッフルゼロ知識証明(「ZKP」)と中間Chaum-Pedersen証明のチェックの両方をパスする場合だけ、シャッフルを実行する。) 第2に、シャッフルが完全に1回実行され、検証されると、t人の作表オーソリティの集合は、エルガマル対の最終集合の各mの暗号解読を共同で (かつ検証可能に) 計算するために、秘密鍵の分担を使用する。
【０２０１】
一般に、シャッフルする各オーソリティは、最初に置換の生成を担当するので、入力と出力の対応関係を知ることになる。しかし、シャッフルは行われ、1回のシャッフルの出力は、シャッフルする別のオーソリティによって実行される別のシャッフルへの入力として使用される。したがって、すべてのオーソリティが共謀しない限り、シャッフルするオーソリティの1人として、最初の入力と最後の出力との間の対応関係を知ることは全くない。しかし後述するように、さらなる強化によりこの可能性も排除される。
【０２０２】
第4:選挙を外部的に検証する
要求により、各オーソリティは、
(a)自分の中間シーケンス
(b)1≦j≦Ncastおよび1≦l≦dに対するChaum-Pedersen証明P(g,gs(j,l),h,hs(j,l))
(c)自分のk-シャッフル証明
(d)上記ステップ(g)下のChaum-Pedersen証明
を発行する。
【０２０３】
一般に、「選挙の写し」を公開することができ、これには以下のものが含まれる。
1.投票者のID情報と投票者の公開鍵を含む投票者名簿
2.k投票者の署名済みの票の元の集合
3. tk×dシャッフル(上記の証明を含めて)
4.最後の共有暗号解読の妥当性証明
5.最終的な投票集計
【０２０４】
注意:オーソリティが作表ステップ(上記の作表ステップ2(a)-(h))を実行する順序を変えたいくつかの形態が可能である。具体的には、これらのステップは、代替の実施形態下で交互に重ねることができる。
【０２０５】
注意:外部検証フェーズは、作表の続行中に実行することも、その後実行することもできる。オーソリティはそれらの段階のパラメータを保存するだけでよい。
【０２０６】
図2に参照される概略図は、方法200として示され、選挙に対するシャッフルプロトコルの基本的な応用例を示している。ブロック202では、3つの暗号化された票が、投票者Joe Smith, Sally Jones,およびIan Kelleighのそれぞれに1つずつ提出される。ブロック204では、投票者のリストすなわち名簿が、ブロック206に示される暗号化された票から分離される。その後、ブロック208に示される票のシャッフルを受けた集合を生成するために、票のワンウェイ再暗号化が実行される。この1回目のシャッフルに基づいて、ブロック210に示すようなシャッフル妥当性証明が生成される。このシャッフル妥当性証明によって、第三者機関は、すべての入力されたデータ(投票)に同じ演算が適用されたこと、および、票の変更がまったく行われなかったことを保障することができる。
【０２０７】
(既にシャッフルを受けた)票の2回目のシャッフルが実行されて、ブロック212に示すような2回目のシャッフルを受けた票の集合を生成する。ここでもまた、ブロック214に示すようなシャッフル妥当性証明が生成される。ブロック212のシャッフルを受けた票が3回目のシャッフルを受け、ブロック216下で最後のシャッフルを受けた票の集合を生成する。3回目のシャッフルに基づいて、第3のシャッフル妥当性証明218が同様に生成される。すなわち、この実施例では、3×3の配列が提供される。このシャッフリングに引き続き、票が暗号解読されて、ブロック220に示すような投票集計を生成する。第三者機関は、各シャッフラが選挙の公平性を維持したことを保障するために、特に各シャッフル妥当性証明を分析することによって選挙を検証することができる。
【０２０８】
シャッフルプロトコルをサブルーチンに効果的に分離し、電子投票方式などの種々の応用例に使用することができることが上記で示されている。第1のサブルーチンは、証明者とベリファイアとの間の、スケールされる反復対数乗法証明の機能を提供する。第2のサブルーチンは、簡素なシャッフルプロトコルの機能を提供し、スケールされる反復対数乗法証明を使用する。その後、第3のサブルールチンは、一般的シャッフル機能を実施するが、そこでは、シャッフラは簡素なシャッフルの第2のサブルーチン上に構築された指数を知らない。第4のサブルーチンは、kタプルの要素のシャッフリングまで第3のサブルーチンを拡張する。
【０２０９】
図3を参照すると、スケールされる反復対数乗法証明を実施するためのルーチン300が示されている。ブロック302では、初期暗号パラメータの合意が、例えば投票機構などによって行われる。これらの初期パラメータは、群(例えば、Zp)、部分群オペレータg、群のサイズG、および生成された部分群pおよびqを含む。この情報は、n人のシャッフラまたはオーソリティコンピュータ114およびベリファイアコンピュータ130に提供される。
【０２１０】
ブロック304では、シャッフラ(または証明者P)は秘密指数cを選択し、部分群ジェネレータgに基づいてCを生成する。さらに、シャッフラは、受け取ったXおよび1からkまでのインデックスiに対するY値を受け取るか、または生成し、X、Y、およびCをベリファイアに提供する。
【０２１１】
ブロック304では、シャッフラはさらに、ランダム指数をriとして秘密裏に生成するが、これは、部分群gジェネレータに基づいて、0からkまでのiの各値に対して値Riを生成するために使用される。同様に、ブロック304下では、シャッフラは、生成されたランダム指数riを使用してWiとZiを生成する。
【０２１２】
ブロック306では、シャッフラは、1からkの各要素に関して、RI-1,Xi,Ri,WiおよびYi,C,Wi,Ziの値にChaum-Pedersen証明を提供する。Chaum-Pesersen証明に関するこれらの値は、次いで値ziとR0と共にベリファイアに提供される。ベリファイアは次いで、ブロック308で、証明を受諾または拒否するために、証明の正確さを検証する。すなわち、ベリファイアは部分群ジェネレータgの指数として各zが対応するZを生成することを確認し、各Chuam-Pedersen証明をチェックし、ziの積がzと等しいことおよびz乗された値R0はRkに等しいことを確認する。
【０２１３】
図4を参照すると、上記のように簡素なシャッフルプロトコルを実行するルーチン400が示される。ブロック302に引き続き、ブロック404はブロック304と類似しているが、シャッフラは、Y要素を生成するために、X要素を置換πによってシャッフルする。ブロック406のベリファイアは、チャレンジとしてランダム値tを生成する。これに応答して、シャッフラはブロック408で、部分群ジェネレータgに対する指数としてtを使用して、秘密裏に値Tを生成するが、この値Tとシャッフラの秘密指数cとを組み合わせると、シャッフラは秘密裏に値Sを生成することが可能となる。図から分かるように、シャッフラは次いで値UおよびVを公然と生成し、(g,C,T,S)に対するChaum-Pedersen証明をブロック410下で提供する。ブロック410で、シャッフラはまた、1からkまでの一連のiの要素XおよびYのそれぞれに対するスケールされる反復対数乗法証明として証明データを生成する。この証明データは次いで、ブロック412でベリファイアに提供される。
【０２１４】
ベリファイアは、証明データの正確さを検証し、それを受諾または拒否する。すなわち、ベリファイアは、UおよびVのシーケンスに対して上記の、スケールされる反復対数乗法証明プロトコルを実行し、コミットメント値Cをチェックする。
【０２１５】
図5を参照すると、シャッフラが指数を知らない場合の、一般的シャッフルプロトコル500が示されている。プロトコル500の初期ステップは、ベリファイアがシャッフラの秘密指数にランダム化要素を加えることを除き、400の初期ステップと類似する。ブロック502に示すように、シャッフラは初期値のランダムシーケンスを秘密裏に生成するが、これは、初期シーケンス
【０２１６】
【数５２】
【０２１７】
を生成するために、部分群ジェネレータgによって指数として使用される。同様に、ブロック504では、ベリファイアは、1からkまでの値iに対する要素eの別のシーケンスを生成し、そのシーケンスをチャレンジとしてシャッフラに提供する。ブロック506では、シャッフラは前のシーケンスにそのシーケンスのチャレンジeを秘密裏に加え、その時までに一連の値
【０２１８】
【数５３】
【０２１９】
を公然と生成する。
【０２２０】
ブロック508では、シャッフラは、別の秘密裏に(シャッフラが選択した異なる秘密指数dを使用する)生成されたコミットメントDによってシーケンスU上に簡素なkシャッフルを構築し、値Vのシーケンスを生成する。次いで、公然と、シャッフラは1からkまでのインデックスに対する値AおよびBのシーケンスに対するChaum-Pedersen証明を露出し、そのシーケンスの積を値AおよびBとして公然と生成して、図示するようにD、A、CおよびBの間の関係にChaum-Pedersen証明を提供する。ブロック510の下では、この証明データはベリファイアに提供され、ベリファイアはこの証明データをブロック512の下で検証する。
【０２２１】
10.検証可能なシャッフルによって匿名証明書を発行する
上記で提示されたのは、暗号化データを検証可能にシャッフリングする新しくて効率的な構築と、この構築を「普遍的に検証可能」な電子選挙システムを実行するために使用することのできる特別な方法である。このシステムでは、投票時に収集された票データを「シャッフル」または「匿名化」することは、選挙オーソリティの集合に依存する。このプロセスは、すべての票が投じられた後、票が暗号解読されて作表される前に行われる。この妥当性の構築は、1人または2人以上の選挙オーソリティが、最終的な選挙の写しを検査しているいずれからも見つからずに、元の選挙データに変更を加えることを防止する。
【０２２２】
この手法の欠点は、選挙の公平性と同様の強固な機構によっては、投票者の匿名性が保護されないということである。選挙の公平性は、単に計算上の処理のしにくさによって保護される。すなわち、選挙オーソリティが、検出されずに偽の選挙結果を生成することは、たとえ全員が共謀したとしても基本的には不可能である。しかし、共謀することによって、彼らは、比較的容易にいかなる個々の投票者の票の内容をも判断することができる。
【０２２３】
この弱点を解消する新しい選挙プロトコルを構築するために、同じ基本的なシャッフル構築を使用することができる。このアイディアは、シャッフリングを、選挙の登録または票の要求のフェーズに移動し、それによって、厳重な管理と選挙の資格規定の検査、すなわち登録した投票者による票だけを数え、同一投票者からの複数の票は受理しないといった管理と検査を損なうことなく、投票者の識別を匿名化するということである。これが達成されると、もはや票を暗号化する必要さえなく、「普通文で」作表を実行することができる。これは、明らかに検査するのに容易なプロセスである。
【０２２４】
この構成を「匿名登録プロセス」の一部として使用するというアイディアは、投票以外にも応用例がある。サーバまたはファイルなどの資源へのアクセスは権限を付与された人員に限定される必要があるが、権限を付与された人員が個人の識別を保護することを希望する場合はいかなる状況でも、この構成を使用して両方の要件を同時に満たすことができる。例えば、グループ署名の応用例は、本発明に記載のプロトコルにおしなべて適用することができる。本発明では、一般に「投票者」という用語は、本発明に記載の一部またはすべてのプロトコルを利用するいかなる個人または組織を意味する。
【０２２５】
「プロトコルの概要」
2つの異なるプロトコルの形体が提供され、どちらも同じ高レベルの情報の流れに従う。各プロトコルは、公開鍵の集合がいくつかの中央認証データベースまたは証明書サーバに記憶されていることを推定するところから始まる。各対応する秘密鍵は、1人の、しかもたった1人の有権者にのみ知られている。さらに、公開鍵と個々の投票者の対応関係は、証明書サーバを管理する1つまたは2つ以上のエンティティによって知られる(これらの公開鍵/秘密鍵対の厳密な形式は、プロトコルの異なる形体ごとに若干相異する。)。実際には、公開鍵は、すべての識別情報を公開鍵と共に単一のフォーマットされたデータとして結合する「デジタル証明書」の形式で包まれるる可能性がある(これは、広く受け入れられている公開鍵基盤すなわちPKIが準拠している規則である。)
通常、このような鍵と証明書の分配は、厳重に管理された登録プロセスによって達成される。このプロセスの最も安全なものは、証明書生成時に投票者が物理的に識別される「本人による」登録プロセスであろう(このような登録プロセスは、米国特許出願第09/534,836号明細書で詳述されている。)。プロトコルに存在する2つの異なるタイプの証明書を区別することが重要である。第1のタイプは、上記の証明書(「標準証明書」)であり、この場合、公開鍵と個々の人物との間の関係が公然と、または少なくとも広く知られている。第2のタイプは、上記の初期登録のフェーズに続くプロトコルの段階で分配される証明書(「匿名証明書」)である。これらの匿名証明書は、少なくとも異なる公開鍵を含んでいるが、所与の匿名証明書の所有者を知っている個人だけが所有者自身であるという事実によって相互に区別することができる。このプロトコルの目的は、
標準証明書の1つを所有する個人だけに、匿名証明書を発行する
ことを保障することである。
【０２２６】
投票応用例などの大半の応用例では、このプロトコルの目的は、さらに、
各個人に、その個人が有する標準証明書と同数だけ匿名証明書を発行する(通常、標準証明書の各所有者は標準証明書を1つだけ有する。)
ことを保障することである。
【０２２７】
標準証明書の登録が完了すると、プロトコルの各形体はそれぞれに以下のように進められる。
【０２２８】
初期化:未処理の公開鍵の集合Kが証明書サーバ(例えば、サーバ108)で構成され、標準証明書の集合に関連付けられた公開鍵の集合になるように初期設定される。各個人が登録して、例えば標準デジタル証明書を受け取るという、各個人の初期登録プロセス中に公開鍵の集合が生成される。この初期登録プロセスの下で生成された公開鍵は一緒にプールされて、集合Kを生成する。各個人は、集合Kの公開鍵の1つに関連付けられた秘密鍵を保持する。
【０２２９】
1.個人Pは、(インターネットなどの)デジタル通信チャネルを介して証明書サーバSと接触し、匿名証明書の取得を希望することを示す。
2.Sは、(Sの秘密鍵を含む)公開鍵の集合H⊂KをPに戻し、集合J=K-Hを記憶する。(理想的には、H=KかつJ=0だが、通信帯域幅の理由から、上記包含が適切であろう。例えば、公開鍵の集合が非常に大きく、伝送するため帯域幅の制約の効果でそのような鍵の大きな集合の伝送が限定される場合、公開鍵Kの部分集合を個人Pに提供するかもしれない。他の理由から、証明書サーバは、公開鍵の部分集合だけを戻すことを希望する場合もある。)
3.Pは、すべてHである場合のある部分集合M⊂Hを選択し、
【０２３０】
M'=H-M
【０２３１】
をセットする。
4.Pは、Mのシャッフル変換であるＨ'を計算する(上節および次節を参照のこと。)。Pは、また、フォーマットされた匿名証明書要求を生成する。これは、ランダムな公開/秘密鍵対を生成し、指定の証明書形式に適合するようにある種の「ランダムID」データで公開部分をフォーマットすることによって行われる(当然ながら、Pは、何らかの安全な場所に秘密部分を記憶することも必要である。)。
5.PはH'、MおよびM'を、
(a)Sまたはどの監査役に対しても、H'が実際にMの有効なシャッフル変換であることを証明するシャッフルの写し、または妥当性の証拠、
(b)特定の要素h∈H'に対応する秘密鍵をPが知っているという証拠、
(c)フォーマットされた証明書要求
と共にSに戻す。
6.Sは、5aと5bの妥当性と共にH=M∪M'であることを確認する。
(a)この確認の1つでも失敗した場合、SはPに失敗であることを示し、Pとの通信を停止するか、またはPに再試行の適切な機会を与える。
(b)双方のチェックとも通った場合、
i.匿名証明書が、標準証明書の各所有者に1回だけ発行されることを目的とされている場合、Sは、
【０２３２】
H''=H'-{h} (17)
K=J∪M∪H' (18)
【０２３３】
をセットし、また、なんらかの理由で、匿名証明書を、標準証明書の各所有者に複数回発行することが望まれる場合、Sは、
【０２３４】
K=J∪M'∪H' (19)
【０２３５】
をセットする。および
ii.Sは、フォーマットされた証明書要求にデジタル署名し、それによって匿名証明書を作成し、(署名した)証明書をPに戻し、後の匿名認証のためにその証明書をデータベースに記憶する。
7.プロセスは、次に、新たなPの始めから続行し、Kは適切に変更される。
【０２３６】
すなわち、個人Pは、証明書サーバSに対して、その個人の選択した部分集合Mの公開鍵の1つに関連付けられた秘密鍵をその個人が保持していることを、公開鍵の部分集合Mをシャッフリングすることによって、それが公開鍵のいずれであるかを露出することなく証明することができる。匿名証明書の発行後、証明書サーバは、次の匿名証明書を要求する個人が使用するために、公開鍵のシャッフルされた集合から1つのシャッフルされた公開鍵を除去する。
【０２３７】
「匿名認証および署名」
上記シャッフルプロトコルを基本的に構築することにより、次の問題が解決されれる。
一般的ｋシャッフル問題:Zp,S={X1,．．．.Xk}およびT={Y1,．．．,Yk}のk要素の2つのシーケンスは公然と知られている。さらに、定数c∈ZqはPにだけ知られているが、cのコミットメントC=gcはVに知らされている。Pは、πまたは秘密cに関する情報を露出せずに、すべての1≦i≦kに関して、
【０２３８】
【数５４】
【０２３９】
という特性を有するある種の置換π∈Σkが存在することを、Vに確信させることが要求される。
【０２４０】
上記シャッフルプロトコルでは、この問題に対する解決法は、まずPおよびVによって実行される対話式証明プロトコルとして提示されるが、これはFiat-Shamirヒューリスティックの標準的な応用例では非対話式である。本発明では、T(S,T,g,C)によって、結果的に生じる検証の、シャッフラPによって生成される写しを示す。
【０２４１】
「匿名認証プロトコル1」
このプロトコルの形体では、
公開鍵は要素h∈<g>⊂Zpであり、対応する秘密鍵は単純に秘密指数s=logghである。
【０２４２】
集合Hは、常にすべてのKに対して取られなければならない。すなわち、H=Kである。
【０２４３】
集合Mも、常にすべてのHでなければならない。すなわち、M=HかつM'=0である。
【０２４４】
Sは、各認証セッション中に変更されるべき1つの追加のモジュラ整数G∈<g>を記憶しなければならない。初期設定で、Gはgに等しくなるようセットされる。
【０２４５】
プロトコルは、前節に記載の要領で以下の変更を加えるように進められる。
1.ステップ2で、SはさらにGをPに戻さなければならない。
2.ステップ5aでPに戻された写しは、正確に、
【０２４６】
T(M,H',G,C)=T(H,H',G,C) (21)
【０２４７】
である。
3.ステップ5bの秘密鍵ノリッジの証明は、
【０２４８】
h'=Ge (22)
【０２４９】
を満足させる特定の値h'∈H'(またはそのインデックス)と共に、正確に整数e=cs∈Zqである。
このような値は1つ、しかもたった1つだけであることに留意されたい。cはランダムでありsから独立しているので、eを露出してもsに関する情報は露出しないことにさらに留意されたい。Sが対応するチェックを実行するのは、単純に方程式22を検証するためである。
4.方程式22のチェックがすべて通った場合、1および2で実行された変換に加え、Sは変換
【０２５０】
G=C (23)
【０２５１】
も実行する。
【０２５２】
「匿名認証プロトコル2」
第1の匿名認証プロトコルの短所は、Pによってシャッフルされるべき集合は常にKの全てでなければならないということである。集合H=Kのすべての公開鍵に同じ変換(塁乗法)が適用される。すべての検査要件が満たされるまで、写しT(H,H',G,C)のそれぞれは記憶しておかなければならないということによって、標準証明書の元の集合が大きい場合、多量のデータが作成される可能性がある。この問題は、次の第2の匿名認証プロトコルによって扱われる。
【０２５３】
このプロトコルの形体では、
公開鍵は要素(k,h)∈<g>×<g>の対であり、対応する秘密鍵は単純に秘密指数s=logkhである。
【０２５４】
集合HはPの公開鍵を含まなければならない。これは種々の方法で達成することができる。
1.SおよびPは、Hのこの特性が達成されるまで一連の再試行に関与することができる。
2.または、初期登録において、標準証明書を「ブロック」に割り当てることができる。Pが最初にSに接触したとき、Pは自分のブロック番号がある限り、自己を特定する。
【０２５５】
効果的に、各個人Pに対して異なる基数Gがセットされ、個人は公開鍵の全体集合(その部分集合は、投票者の公開鍵対を含む)の部分集合だけをシャッフルする。このプロトコルは、前節に記載の要領で、次の変更に進められる。
1.ステップ5aでPに戻された写しは対の集合に対するシャッフルの写しである。この構成に関する詳細は上記を参照されたい。
2.ステップ5bの秘密鍵ノリッジの証明は、秘密鍵を露出することを防止するために、若干複雑にする必要がある。
(a)PはＳに対して、特定の対(k',h')∈H'、または、Pの秘密鍵に属する対の新たなインデックスであるインデックスを示す。すなわち、h'=(k')sである(このような対は、シャッフル演算がkとhの両方を同一の秘密指数cに指数のベキに上げるので、このような対は一意に存在することに留意されたい。したがって、hc=(kc)sの場合のみ、h=ksである。)。
(b)PはSに対して、Pがs=logg'h'を知っているという「ゼロ知識証明」を露出する(Chaumの論文を参照のこと。)。これは、Pが、対応する秘密鍵を露出せずに対応する秘密鍵を知ることを証明する。
3.Sが実行しなければならない対応するチェックは明らかである。
(a)SはPのシャッフルの写しの妥当性をチェックする。
(b)SはPがs=logg'h'を知っているというPの証明の妥当性をチェックする。
【０２５６】
注意:代替の実施形態下では、集合Kの一部またはすべての鍵(すなわち、部分集合H)は、いずれか一個人が匿名証明書を要求する前に、ある個人またはオーソリティによってシャッフルすることができる。すなわち、公開鍵のプールは、上記匿名認証プロトコルのどちらかが、要求している特定の個人に利用される前に、十分にランダム化することができる。したがって、公開鍵の小さな部分集合は、プロトコル2の下で各個人により選択することができる。
【０２５７】
図6を参照すると、匿名証明書分配の第1の変形体を実施するためのルーチン600の一例が示されている。ブロック302で暗号パラメータを初期化した後、公開鍵Hの標準集合がブロック604で提供されるが、これは、登録者または投票者の集合がそれぞれに(ブロック606に示すように、個々に保持した秘密鍵sに対応する)公開鍵hを登録して提出した後、登録サーバによって収集することができる。ブロック608では、部分群ジェネレータgがGにセットされる。
【０２５８】
ブロック610では、1人または2人以上のオーソリティによって実行される選択的ランダム化を実行することができる。ブロック610では、(G,C=Gc)をシャッフルコミットメントとして使用して、順次、各オーソリティが検証可能なシャッフルを標準公開鍵Hの集合で実行するが、ここでcはオーソリティによって保持される秘密鍵である。各オーソリティは、公開鍵のシャッフルされた集合H'を、上記の一般的シャッフルを使用してシャッフル検証の写しT(H,H',G,C)と共に戻す。検証の写しが正しい場合、登録サーバは、代入G=CおよびH=H'を実行し、前の値を、後の検査のためにシャッフル検証の写しと共に記憶する。ブロック610の下の選択的ランダム化は、前の初期化の一部として、あるいは後述する匿名証明書の生成のいかなる中間段階でも実行することができる。
【０２５９】
ブロック612-618は、集合Hの公開鍵hの1つを以前に提供した個人による匿名証明書の単一の要求を示す。これらのステップは、要求している各登録者によって反復される。ブロック612では、登録者(または、より正確には、投票者のコンピュータ102)は匿名証明書に対する要求を生成する。これに応答して、登録サーバは、ブロック614の下で値Gと公開鍵の集合Hを取り出し、それらを登録者に戻す。ブロック616では、登録者は、上記の一般的シャッフルプロトコル下で、シャッフルと、対応する検証の写しを計算し、各インデックス1≦j≦kに対してT(H,H',G,C)および(登録者にのみ知られているcsに等しい)eを戻す。さらに、ブロック616では、登録者は、ある種のランダムな識別情報によってPKI証明書要求を生成する。このランダムな識別情報は、登録者が使用するために選択したいかなるユーザIDであってもよいが、これは登録者を識別するために使用することはできない。ブロック616の下では、登録者は、また、この要求に基づいて、対応する秘密鍵を安全に記憶する(秘密鍵sjとは異なる)。
【０２６０】
ブロック618では、登録サーバはシャッフル検証の写しをチェックし、h'j=Geであることを確認する。これら双方のチェックが通ると、登録サーバはH=H'から証明書に対する登録によって使用される1つの公開鍵を減じた(h'j)、G=C、およびk=k-1をセットする。検査のために、ブロック618の登録サーバは、登録者の検証の写し(すなわち、T(H,H',G,C))も記憶する。登録サーバは、また、登録者に戻されるPKI証明書を作成するために、証明書要求Rにデジタル署名する。このルーチンは次の登録者の要求の準備ができる。
【０２６１】
図7を参照すると、ルーチン700は匿名証明書の分配に関して上記した第2の形体を示す。ルーチン700はルーチン600に類似している。ブロック704は、集合Hが公開/秘密鍵対を含んでおり、適切な部分集合であり得ることを除いて、ブロック604に同様である。同様に、ブロック710は、図7に示すようにブロック610に類似している。
【０２６２】
要求を受け取った後、ブロック714で登録サーバは公開鍵対の集合Hを取り出す。代替の実施形態下で、登録サーバは、登録者の公開鍵を含む部分集合だけを取り出す。ブロック716で、登録者は公開鍵対の部分集合Mを選択し、M'=H-Mをセットする。登録者は、MのシャッフルH'と、対応する検証の写し(T(M,H',g,C))を計算し、登録者は図7に示す秘密指数を知っているというゼロ知識証明Pを生成する。さらに、登録者は、上記のように、ランダムな識別情報によってPKI証明書要求を生成し、秘密鍵を記憶する。
【０２６３】
ブロック718では、登録者サーバはシャッフル検証の写しとPとをチェックする。どちらのチェックも通った場合、登録者サーバは、Kをセットし(方程式(18)または(19)の下で公開鍵対(g'j,h'j)を除去し)、k=k-1をセットする。ルーチン700の残りの部分は、ルーチン600の残りの部分とほぼ同一である。
【０２６４】
11.結論
当業者ならば、本発明の概念は、インターネット以外の種々の環境で使用することができることが理解されるであろう。例えば、この概念は、電子メール投票、トランザクション、フォームが処理され記憶される電子メール環境で使用することができる。一般に、ウェブページまたは表示内容(例えば、掲示板)は、HTML、XMLまたはWAP形式、電子メール形式、または情報を表示するのに適した(文字/コードベース形式、ビットマップ形式、およびベクトルベース形式を含めて)いかなる他の形式であってもよい。同様に、インターネットの代わりに、ローカルエリアネットワーク、ワイドエリアネットワーク、またはポイントツーポイントのダイヤルアップ接続などの種々の通信チャネルを使用することができる。種々のトランザクションもまた、クライアント/サーバ環境ではなく、単一コンピュータ環境内で実施することができる。各投票者コンピュータまたはクライアントコンピュータは、サーバコンピュータまたはシステムと対話するハードウェアまたはソフトウェアのいかなる組み合わせを含むこともできる。これらのクライアントシステムは、テレビジョンベースのシステム、インターネット機器、およびトランザクションを実行することができる種々の他の消費者製品を含むことができる。
【０２６５】
本発明で一般に使用される「リンク」という用語は、ネットワーク上にサイトまたはノードを有する投票オーソリティの表示内容などの、ネットワーク上の資源を識別する任意の資源ロケータを示す。一般に、投票者コンピュータ、端末およびサーバなどのハードウェアプラットフォームを本明細書では記載しているが、本発明の態様は、ノードを識別するための対応する資源ロケータを有するネットワーク上のノードにおしなべて適用可能である。
【０２６６】
文脈上明らかに要求されない限り、詳細な説明並びに特許請求の範囲を通して、「備える」「備えている」などの語句は、排他的意味または網羅的意味とは反対の、包含的な意味、すなわち「含むが、これに限定されない」という意味に解釈されるべきである。単数または複数を使用する単語も、それぞれに複数または単数を含む。さらに、「本発明において」「本発明では」という語句、および類似の意味の単語も、本願で使用される場合、本願を全体として意味しており、本願のいかなる特定の部分をも意味しない。
【０２６７】
本発明の例示の実施形態についての上記の説明は、本発明を、開示された正確な形式を網羅し、限定することを目的としていない。本発明の特定の実施形態および実施例を説明する目的で本明細書に記載したが、種々の異なる形態も本発明の範囲内で可能であることを関連技術の精通者ならば理解するであろう。本発明の教示するところは、上記の電子投票システムだけでなく他の暗号化の応用例にも適用することができる。例えば、このプロトコルの応用例には、匿名性と検査可能性の双方を必要とする電子商取引も含まれる。この実施例は、電子マネーによる支払い方式(「電子キャッシュ」)である。
【０２６８】
上記の種々の実施形態は、さらなる実施形態を提供するように組み合わせることができる。上記の参照および米国特許および出願のすべては、参照により本発明に組み込まれている。本発明の態様は、本発明のさらに別の実施形態を提供するために種々の特許および出願のシステム、機能、および概念を利用するように、必要に応じて変更することができる。
【０２６９】
上記の詳細な説明に鑑みて、本発明にはこれらおよび他の変更を加えることができる。一般に、特許請求の範囲で使用される用語は、本発明および特許請求の範囲で開示された特定の実施形態に本発明を限定するものと解釈されるべきでなく、データの安全性を実現するために特許請求の範囲で動作するすべての暗号化システムおよび方法を含むものと解釈されるべきである。したがって、本発明は開示によって限定されるのではなく、本発明の範囲は特許請求の範囲によって完全に確定されるべきである。
【０２７０】
本発明の特定の態様は特許請求の範囲の形式で表現されるが、いかなる数の特許請求の範囲形式においても本発明の種々の態様が検討される。例えば、本発明の1つの態様だけがコンピュータ読み取り可能媒体として実施されるように記載されているが、他の態様も同様にコンピュータ読み取り可能媒体として実施することができる。したがって、本発明の他の態様のためにそのような追加の請求項の形式を追求するため、本願出願後に追加の請求項を加える権利が留保されている。
【図面の簡単な説明】
【０２７１】
【図１】本発明の実施形態を実施するために適切な環境を示すブロック図である。
【図２】3人の投票者と3回のシャッフルによる1つの簡素な投票に適用された本明細書に記載のシャッフルプロトコルの簡素な実施を示す概略図である。
【図３】スケールされる反復対数乗法証明プロトコルを示すフロー図である。
【図４】シャッフラが暗号指数を知っている簡素なシャッフルプロトコルを示すフロー図である。
【図５】シャッフラが暗号指数を知らない一般的なシャッフルプロトコルを示すフロー図である。
【図６】匿名証明書分配ルーチンを示すフロー図である。
【図７】図6の匿名証明書分配ルーチンの代替実施形態を示すフロー図である。
【技術分野】
【０００１】
本発明は、一般に暗号化に関し、より詳細には、投票方式で使用するための電子暗号化に関する。
【背景技術】
【０００２】
(背景および概要)
オブジェクト、記録またはトークンの集合のシャッフルの概念は、簡素かつ直観的であり、有用な使用例が、人々の日常の種々の活動にあふれている。カジノのギャンブラーは、自分の持ち札を取り出すときは、その1枚1枚が52の一意の値のうちの1つであること、およびその持ち札と同じ持ち札を有する者はそのテーブルにはいないということを知っている。しかし、たとえディーラーがそれらのカードをシャッフルする前にそのギャンブラーがカードの正確な順序を記録しておくことができたとしても、そのギャンブラーは、それらのカードがどのように配られたかはまったく知ることはない。
【０００３】
電子データのコンテクストにおいては、入力されたシーケンスを同種のランダムだが検証が可能なように置換するという問題は驚くほど困難である。この問題は、データ自体、監査役(auditor)に常に明白であるか、そうでないかのどちらかしかないということである。明白である場合、入力された記録と出力された記録との間の対応は自明(trivial)で、監査役または他のオブザーバーが再構成することができる。明白でない場合、入力された記録と出力された記録は、同一の基礎となるデータの異なる表現でなければならない。しかし、出力が十分に異なっていて(すなわち、十分に暗号化されていて)監査役が対応関係を再構成することができない場合、監査役は、シャッフリングの過程でシャッフラが基礎となるデータを変更しなかったことをいかに確信するであろうか。
【０００４】
以下の説明の大半は、エルガマル（ElGamal）暗号化データという、重要なコンテクストにおいてこの問題を解決するための有効な(線形の)方法を提供するために費やされている。できる限り明瞭かつ簡潔な解説とするため、以下の説明の大部分は、大きな素数pを法とする乗法単位群である
【０００５】
【数１】
【０００６】
で演算が実行される具体的なケースをそのまま参照する。しかし、使用され基礎となる(乗法の)群の特性は、関連するエルガマル暗号システムが安全でなければならないということ、および、関係式loggX = loghY = uに対するChaum-Pedersen（チョム−ペダーセン）プロトコル(D.Chaum著、「Zero-knowledge undeniable signatures. Advances in Cryptology EUROCRYPT'90, volume 473, Lecture Notes in Computer Science」473巻、458-464頁、1991年Springer-Verlag。D.ChaumおよびT.P.Pedersen著、「Wallet Databases With Observers. In Advances in Cryptology CRYPTO '92, volume 740, Lecture Notes in Computer」740巻、89-105頁、ベルリン、1993年、Springer-Verlag。)は秘密指数uに関する情報を漏らしてはならないということだけである。実際、一実施形態では、普遍的に検証可能な複数オーソリティ選挙プロトコル−べリファイア(verifier)は、Fiat-Shamirヒューリスティック(A.FiatおよびA.Shamir著、「How to prove yourself: Practical solutions to identification and signature problems. Advances in Cryptology CRYPTO'86, Lecture Notes in Computer Science」186-194頁、Springer-Verlag、New York、1987年。) によって実施されるので、この場合には、公正なベリファイアに対してプロトコルはゼロ知識であれば十分である(R. Cramer、R.Gennaro、B. Schoenmakers著、「A secure and optimally efficient multi-authority election scheme. Advances in Cryptology EUROCRYPT '97, Lecture Notes in Computer Science」Springer-Verlag, 1997年。)。したがって、シャッフルプロトコルは、楕円曲線などの他の群までエルガマル暗号化を実施するときにも有用である。R.Cramer, I.Damgrd, B.Schoenmakers著、「Proofs of partial knowledge and simplified design of witness hiding protocols」(Advances in Cryptology CRYPTO'94, Lecture Notes in Computer Science, 174-187頁、Springer-Verlag、ベルリン、1994年)の、一般的なブールの証明（boolean proof）手法も、同じ特性を有する証明を構築するために使用することができるが、結果的に証明のサイズ(複雑さ)は入力シーケンスのサイズでは2次元またはそれよりも劣ることとなる。
【０００７】
後述するプロトコルまたは方法によっても、K.Sako, J. Kilian著、「Receipt-free mix-type voting scheme- A practical solution to the implementation of a voting booth, Advances in Cryptology EUROCRYPT '95, Lecture Notes in Computer Science」Springer-Verlag, 1995年で使用されたような、カットアンドチューズ手法のいくつかの利点が得られる。この手法では、証明のサイズは、すべての参加者を満足させることを要求される証明者の不正行為を行う確率に依存する。本発明に記載のシャッフルプロトコルでは、この不正行為の行われる確率は、kをシャッフルされるべき要素数とし、qをそれらの要素が暗号化される
【０００８】
【数２】
【０００９】
の部分群のサイズとすると、基本的にk/qである。K.Sakoの論文では証明のサイズの分析は行われていないが、同様に不正行為の行われる確率を低くするためには、本発明で提供する証明のサイズよりも数桁大きくする必要があると考えられる。(さらに、K.Sakoのプロトコルが非対話式に実施される場合、不正行為を行う確率は極めて小さく選択されなければならない。何故ならば、悪意のある参加者が、徹底したサーチにより偽造証明を生成するため、多量のオフライン計算を使用する可能性があるからである。これは、当然ながら、上記プロトコルではこの通りであり得るが、確率k/qは、kとqのすべての現実的な値に関して十分小さいことは確実である。)
【発明の開示】
【発明が解決しようとする課題】
【００１０】
結果的に普遍的に検証可能となる選挙プロトコルのコンテクストにおいて見るとき、現行方式の利点はさらに明確になる。K.Sakoにおいて、各投票者は、実際に票を投じる前に各「集計センター」と連続して対話する必要がある。このような理由から、近い将来、大規模な公共セクタの選挙のために有効な実施がなされる可能性は低いと考えられる。反対に、後述するプロトコルでは、純粋に作表の目的で選挙終了時にすべてのオーソリティを参加させる(場合によっては、基本的な選挙パラメータの作成は除く)。
【課題を解決するための手段】
【００１１】
この素晴らしい特性は、R.Cramer, R.GennaroおよびB. Schoenmakersの論文に記載の洗練された準同形選挙プロトコルにも見られる。しかし、このプロトコルは、「nの中のm(以下)を選択せよ」という簡素なタイプの質問を有する投票に適用できるだけである。これは効果的に、投票者が優先順位で回答を示すことが要求され、質問項目はその優先順位に従って作表されることとなる、「記入式」応答、並びに「比例タイプの」質問を除外する。R.Cramer, R.GennaroおよびB.Schoenmakersスキームの欠点は、これに比べて若干重要度は低いが、投票データサイズを大幅に拡張すること、および、投票者に「妥当性証明」を要求することである。この証明によると、投票データのサイズは約1桁だけ拡張され、実用的な観点からは魅力的ではない。なぜなら、投票者のコンピュータで専用コードが実行していることが前提とされるからである。
【００１２】
このプロトコルは後述するが、Chaum-Pedersen(チョム-ペダーセン)証明のシーケンスと基本的な算術演算だけで構成されている。したがって、これは、容易に実施される。
【発明を実施するための最良の形態】
【００１３】
(詳細な説明)
図面では、同一またはほぼ同一の要素または動作は同一の参照番号で示す。いかなる特定の要素または動作の説明をも容易に識別するために、参照番号の1つまたは2つ以上の最上位桁は、その要素が最初に紹介された図番を示している(例えば、要素204は最初に図2で紹介され、図2に関して説明されている。)。
【００１４】
本発明に設けられている表題は便宜上のみのためのものであり、請求の範囲に記載の発明の範囲または意味には必ずしも影響を与えるものではない。
【００１５】
1.概要
以下で詳述するのは、一連の要素、例えば離散対数形式またはk入力エルガマル暗号化による公開鍵の入力シーケンスを「検証可能にシャッフルする」ための暗号化プロトコルであり、これらはセキュリティ保護された普遍的に検証可能な複数オーソリティ選挙スキームに応用例を持つ。k入力エルガマル暗号化の場合、シャッフル演算の出力はkエルガマル暗号の別のシーケンスであり、その各々は入力された暗号の中の正確に1つを再暗号化する(すなわち、同一のクリアなテキストを正確に暗号化するエルガマル対)が、出力の中の要素の順序は秘密に保持される。(適用されるべき要素の並べ替えおよび使用される暗号化鍵を選択する)「シャッフラ」にとって、入力から出力を計算することは些細なことではあるが、その構築は重要である。なぜなら、任意のベリファイアによってチェックされる可能性のある出力シーケンスのための正確さについてのリニアなサイズの証明(すなわち、請求された形式の証明)が提供されるからである。証明プロトコルのセキュリティは、関係式loggx = loghyに対するChaum-Pedersenプロトコルのそれと同じであり、使用される選挙の応用例に関し、これで十分である。
【００１６】
以下の説明では、本発明の実施形態を完全に理解するための具体的な詳細、および実施可能な説明が提供される。しかし、当業者ならば、本発明はこれらの詳細なくしても実施可能であることが理解されるであろう。他の例においては、本発明の実施形態の説明を不必要に不明瞭化することを避けるため、周知の構造および関数は詳細に図示または説明しない。
【００１７】
以下に提供される詳細な説明の大半は、上記の仮出願で明示的に開示されている；追加資料の多くは、そのような仮出願に提供された詳細な説明に固有のものとして関連技術の精通者に理解されるものであり、あるいは周知のものである。関連技術の精通者は、仮出願に提供された詳細な説明に基づいて本発明の態様を実施することができる。
【００１８】
本発明で使用される数学的表記法の多くは、関連技術の精通者には容易に理解することができるが、当技術分野に精通していない技術者のために以下のように定義して説明する。これらの定義は簡略ではあるが、当技術分野に全般的に精通していない技術者が、本明細書に記載の詳細な説明に基づいて本発明の実施態様をさらに完全に理解するのに役立つであろう。これらの定義は、全体として(特許請求の範囲を含めて)本発明の説明によってさらに定義されるものであり、これらの定義にだけよるものではない。
【００１９】
図1-5は、本明細書に記載の詳細な説明に加えて、当事者(例えば、投票者)とベリファイアの間(または、証明側当事者と検証側当事者の間)のプロトコルを説明する。これらの当事者によって実行される動作は、流れ図のボックスに共に分類される。一般に、ボックス内の各行のテキストまたは方程式は、計算、情報の伝送、あるいは記憶または検索関数などのステップを説明している。このような流れ図は1行ごとに、また、ボックスごとに読まれる。
【００２０】
本発明で一般に使用される「当事者」という用語は、エンティティを示しているが、このプロトコルの下で、ステップまたはステップの集合を実行するエージェントとすることができる。この用語はまた、これらステップの一部またはすべてを実行する手段または方法のことを言う場合もある。したがって、デジタル論理回路中の適当ないかなる構成の下でも、プロトコルの一部またはすべての部分を実行することができる。例えば、プロトコルの下の任意のステップまたはすべてのステップは、パーソナルコンピュータなどの汎用コンピュータだけでなく、組み込み型または専用の組み合わせ論理装置、またはいかなる種類の適切にプログラムされたマシン乃至マイクロプロセッサによっても、以上の装置またはマシンが必要な処理ステップ、ストレージ、入力および出力などを実行する場合に限り、実現することができる。
【００２１】
記号「∈R」は、一般に、略均一で独立した(ランダムな)確率分布に従って、右側の集合から左側の1つまたは複数の数字が選択されることを示している。実際、場合によっては付加的な事後処理または決定論的擬似乱数ジェネレータと共に、物理的な乱数ジェネレータを使用することができる。乱数を生成する方法は、関連技術の精通者には周知である。
【００２２】
記号「Π」および「Σ」は、それぞれインデックス付きの積と和を示す。
【００２３】
記号「Zp」は整数0からp-1の数の集合、またはpを法とする整数の環を示す。環Zpでの要素の加法および乗法はpを法として定義される。
【００２４】
記号「∈」は、左側の要素が右側の集合の構成要素または要素であることを示している。
【００２５】
記号「⊂」は、左側の集合が右側の集合の部分集合であること、すなわち左側の集合が右側の集合に含まれることを示している。
【００２６】
角括弧記号(すなわち、「<>」)は、それらに挟まれた1つまたは複数の項が所与の群または整数の環(例えば、環Zp)の部分集合によって生成された部分群であることを示している。部分群は、これもまた同じバイナリオペレーション下の群である別の群(または環)の部分集合である(例えば、整数は加法下の実数の部分群であるが、nを法とする整数は、演算が別に定義されるので、それらの部分群ではない。
【００２７】
以下では、別途明示しない限り、公知のように、nは正の整数であり、pとqは素数の整数である。算術演算は、モジュラ環Zp(またはZnである場合がある)で実行され、g∈Zpは(素数の)乗法の階数qを有することになる。(したがって、単にq|(p-1)である)。各証明プロトコルでは、Pは証明者(シャッフラ)でありVはベリファイア(監査役)である。
【００２８】
後述する一実施形態は、Zp(エルガマル)暗号システムを使用するが、楕円曲線暗号システムと、一般群下の暗号システムを使用することもできる。このような暗号システムは、非対称暗号システムに対する公開鍵を使用する。公開鍵システムは、所謂一方向性関数と落し戸関数を使用する。「一方向性関数」とは出力を計算するのは比較的容易だが、その逆関数は計算することが遥かに困難な関数のことである。例えば、ベキ関数は等しい因数の数の積を計算することは容易であるが、数量の根を探す逆演算はより複雑である。「トラップドア」関数は一方向性関数と類似しているが、何らかの追加情報が入手できない限り、逆関数は極めて困難である。この追加情報は、通常、投票者などの当事者によって保持される「公開鍵」である。
【００２９】
下記の方法およびプロトコルは、離散対数に対するChaum-Pedersenの等式(equality)の証明を頻繁に使用する。g、X、h、Y ∈ Zpの場合、これは関係式
【００３０】
logg X = logh Y (1)
【００３１】
に関する知識の証明である。
【００３２】
ゼロ知識であることは知られていない。しかし、公正なベリファイアに対してはゼロ知識であることが知られているが、これは、Fiat-Shamirヒューリスティックによってベリファイアを実施する、主要な応用例にとっては十分である。
【００３３】
「ゼロ知識証明」では、投票者または証明側当事者は、秘密のノリッジを証明することができるが、使用している情報が何であれ、ノリッジのその証明の伝達する際に検証側当事者にそれを露出することはない。単一ビットの情報、すなわち、証明側当事者が実際にその秘密を知っているということだけが伝達される。換言すると、投票者と検証するオーソリティはメッセージを交換するが、投票者の目的は、票の各質問に投票者がどのように投票したか、または一連の要素がどのようにシャッフルされたかを露出することなく、主張が真実であることをベリファイアに確信させることであり、その主張とは、例えば暗号化された投票または、投票または要素のシャッフルされたシーケンスは完全であり正確であるというような主張である。このようなゼロ知識証明の下では、各投票者または証明側当事者は、効果的に、自分の秘密鍵を有する人物だけが生成することのできる特定の数を生成する。ベリファイアまたは認証する当事者は、次いで、それぞれの計算された数が本当に周知のアルゴリズムで生成され、それによって投票者を認証すること、および、投票者の電子投票が完全かつ正確であるかまたは許容される選択と制約に関し「良好に形成されている」ことを確認し、あるいは一連の要素が(シャッフルされ暗号化された以外に)変更されていないことを確認する。
【００３４】
定義1
上記のChaum-Pedersen証明の一例は、
【００３５】
CP(g,X,h,Y)
【００３６】
によって示される。
【００３７】
定義2
固定された
【００３８】
【数３】
【００３９】
が<g>x<g>上のバイナリオペレータの場合、すべてのx、y ∈ <g>に対する
【００４０】
【数４】
【００４１】
によって定義された環の部分集合によって生成された部分群を示す。あるいはこれに替えて、すべてのa、b ∈ Zqに関する
【００４２】
【数５】
【００４３】
である。加法および乗法に使用されるインデックスを付ける規則に従って、
【００４４】
【数６】
【００４５】
の表記法も使用する。
【００４６】
このオペレーションを、本発明では対数乗法基数gと称する。
【００４７】
以上の定義における各々の表記法では、下付き添え字gの値が前後関係から明らかな場合は、これを省略することができる。本発明で一般に使用するように、「バイナリオペレータ」とは入力として集合から2つの要素をとり、1つの要素を戻すような集合で定義されるオペレータを意味する。
【００４８】
注意1
Chaum-Pedersen証明では、h = gSであり、かつその常用対数がu = loggX = loghYである場合、CP(g、X、h、Y)は明らかに関係式
【００４９】
【数７】
【００５０】
を証明してもいることに注意されたい。
【００５１】
注意2
上記の証明は、明らかにsに関してゼロ知識である。これは証明者が、証明を構成するためにこの値を知る必要は全くないからである。
【００５２】
詳細な説明の以下の部分で非常に多く使用されるので、以下のよく知られた結果のコレクション(collection)に注目されたい。
【００５３】
補助定理1
f(x)∈Zq[x]を次数dの多項式とする。この場合、d以下の値z1,．．．zd∈Zqがあり、したがって、f(zi) = 0である。
【００５４】
系1
f(x), g(x)∈Zq[x]を、f≠gとして、次数d以上の2つの多項式とする。この場合、d以上の値z1,．．．zd∈Zqが存在し、したがって、f(zi) = g(zi)である。
【００５５】
系2
f(x), g(x)∈Zq[x]を、f≠gとして、次数d以上の2つの多項式とする。c∈RZq、(cはZqからアトランダムに選択された)とすると、以下の確率が得られる。
【００５６】
【数８】
補助定理2
【００５７】
【数９】
【００５８】
をZqに亘る標準的なk次元のベクトル空間とし、
【００５９】
【数１０】
【００６０】
をv≠0に固定する。
【００６１】
【数１１】
【００６２】
がアトランダムに選択されると、
【００６３】
【数１２】
【００６４】
となる。
【００６５】
2.反復対数乗法の証明
この節の以下の部分で、すべての対数乗法は、固定された要素gに関して計算されるので、表記法の下付き添え字は省略される。以下の問題は、後に出て来るシャッフル証明の基礎となるものである。
【００６６】
反復対数乗法問題:2つのシーケンス
【００６７】
【数１３】
【００６８】
と、
【００６９】
【数１４】
【００７０】
は公然と知られている。証明者Pはすべてのiに関するui=loggXiおよびvi=loggYiも知っているが、これらはベリファイアVには知られていない。Pは、秘密対数uiとviに関する情報を露出せずに、関係式
【００７１】
【数１５】
【００７２】
をVに確信させることが要求される。
【００７３】
直観的に、注意1を考慮するとこの問題は簡潔である。証明者はk Chaum-Pedersen証明の2つのシーケンスを構築して、Vに、
【００７４】
【数１６】
【００７５】
の値と、
【００７６】
【数１７】
【００７７】
の値の両方を確信させることができ、次いでVはそれらの2つの値が同一であるとチェックすることができる。すべてのXiとYiがランダムかつ独立であることが知られている場合、このことはuiとviとを秘密に保持する目的で受け入れることができ、本発明の一実施形態で実施することができる。しかし、このプロトコルは、中間対数乗法に加え、V自身では計算することができない一部の情報、すなわち
【００７８】
【数１８】
【００７９】
の値を露出することは明らかである。このプロトコルを強化するために、上述の実施形態と以下で詳述される方法はある程度のランダム性を導入し、基礎となるChaum-Pedersenプロトコルよりも多く情報を漏洩しないことを保障する。
反復対数乗法証明:
1.Pは秘密裏に、k+1個の値
【００８０】
【数１９】
【００８１】
をランダムかつ独立に生成し、指数のベキにあげる値
【００８２】
【数２０】
【００８３】
を露出する。
2. 1≦i≦kの各々に関して、Pは秘密裏にwi=riui/ri-1を計算し、
【００８４】
【数２１】
【００８５】
と、zi=wi/viを露出する。
3.Pは
【００８６】
【数２２】
【００８７】
をセットし、Vに対してPが露出する2つのChaum-Pedersen証明
【００８８】
CP(Ri-1,Xi,Ri,Wi) (3)
CP(Yi,gi,Wi,Zi) (4)
【００８９】
を構築する。これら2つの共になされたChaum-Pedersen証明では、別個に行われて各々から露出される情報以上に秘密に関する情報を露出する可能性はない。これを理解するキーは注意2である。第1の証明はri/ri-1に関してゼロ知識であるが、ui/ri-1に関しては、公正なベリファイアだけがゼロ知識である。しかし、第2の証明はri,ri-1とuiに関しゼロ知識である。これは、証明者さえも、証明を生成するためにそれらの値を知る必要がないからである。しかし、もちろん、露出されたziからこれらの値に関する情報の一部を、viに関して一部の情報が知られる場合だけ、得ることができる。不正なベリファイアによってこのようなことが起こる可能性があるかどうかは知られていないが、ベリファイアが公正な場合は起こらない。これは、後述する実施形態と応用例でも同様である。
【００９０】
明らかに商ri/ri-1はすべて均一に分配されて独立しているので、値zi自体は、uiとviに関していかなる情報もそれら自体によっては露出しない。
4.Vは
【００９１】
【数２３】
【００９２】
であることをチェックし、各Chaum-Pedersen証明をチェックする。
5.Vは最終的に
【００９３】
【数２４】
【００９４】
を評価し、
【００９５】
【数２５】
【００９６】
であることをチェックする。
【００９７】
注意1を参照し、単純にその指数を乗算することによって、このプロトコルが反復対数乗法問題を解決することは、容易に確認することができる。偽造証明の確率は、1つまたは2つ以上のChaum-Pedersen証明が偽造された確率だけ上に有界である。これらの確率のそれぞれは1/qである。したがって、偽造される証明の全体的な確率は2k/qだけ上に有界である。
【００９８】
後で明らかになる理由から、この方法に対しては、実際上次の別の反復対数乗法問題はより有益である。
【００９９】
スケールされる反復対数乗法問題:元の問題と同様に、2つのシーケンス
【０１００】
【数２６】
【０１０１】
と、
【０１０２】
【数２７】
【０１０３】
は公然と知られており、すべてのiに関するui=loggXおよびvi=loggYiはPに知られているが、Vには秘密である。さらに、定数c∈ZqはPにだけ知られているが、cのコミットメントであるC=gcはVに知られることになる。Pは、秘密対数ui,vi,およびcに関する情報を露出せずに、関係式
【０１０４】
【数２８】
【０１０５】
をVに確信させることが要求される。
【０１０６】
スケールされる反復対数乗法証明:この証明は、元の値に対するより小さい変分しか必要としない。4のChaum-Pedersen証明は、類似の証明
【０１０７】
CP(Yi,Ci,Wi,Zi) (6)
【０１０８】
で置き換える必要がある。
【０１０９】
3.簡素なKシャッフル
本発明で構築した第1のシャッフル証明は、条件の限定的な集合を必要とする。これは2つの理由から有用であろう。第1に、これは、後で出てくる、より一般的なシャッフル証明の基本的なビルディングブロックとなる。偶然にも、これは第2の重要な目的にも役立つ。この証明の一例を、特定の置換を効果的に「コミットする」ために構築することができる。Zpの要素のタプル上でシャッフルを実施する必要がある場合に、これは重要となる可能性があるが、これはまさしく投票応用例で必要とされるものである(「タプル」はシーケンスまたは順序集合のことである。例えば、5-タプルまたは5倍は5つの要素をもつ順序集合であり、k-タプルは不特定数の構成要素による有限の順序集合のことである。)。
【０１１０】
簡素なkシャッフル問題:k要素の2つのシーケンス、ZP,X1,．．．XkおよびY1,．．．Ykは公然と知られている。証明者Pもui,=loggXiおよびvi=loggYiを知っているが、それらはベリファイアVには知られていない。さらに、定数c∈ZqはPだけに知られているが、cのコミットメントであるC=gcはVに知らされる。Pは、πまたは秘密cに関する情報を露出せずに、すべての1≦i≦kに関して、
【０１１１】
【数２９】
【０１１２】
という特性を有するある種の置換π∈ΣkがあることをVに確信させることが要求される。関数πは入力される要素の集合を置換された出力される要素の集合にマッピングするための関数に対応する。
【０１１３】
簡素なkシャッフル証明:この証明の構築は、前節および系2を考慮すると略自明である。
1.Vはランダムなt∈Zqを生成し、それをチャレンジとしてPに与える。
2.PはT=gt(また知られているV)とS=Tc=gctとを計算する。
3.PはChaum-Pedersen証明CP(g,C,T,S)を生成し、これをVに露出する。
4.Pは公然と(すなわち、Vによってチェックされる)Ui=T/XiおよびVi=S/Yiの値を計算する。注意:UiおよびViは、系2の表記法によって行内にさらに入るように選択される。一実施形態では、除法は計算上は乗法よりも費用が掛かるので、この方法はUi=Xi/TおよびVi=Yi/Sによってプロトコルを実施する。
【０１１４】
証明者は、シーケンス
【０１１５】
【数３０】
【０１１６】
と、
【０１１７】
【数３１】
【０１１８】
および、コミットメントCに対してスケールされる反復対数乗法証明を実行する。スケールされる対数乗法証明をUおよびVの上でチェックすることによって、ベリファイアは、要素Xの初期入力シーケンスとシーケンスYの間の所望の関係が(系2に基づいて)保たれることを保障する。
【０１１９】
スケールされる反復対数乗法証明が偽造されるか、またはS=Tcの単一の証明が偽造されるか、あるいはVが系2の除外集合からcを偶然に選択した場合、偽造された証明が生成される可能性がある。したがって、偽造された証明の全体的な確率は(3k+1)/qだけ上に有界である。本発明に記載のシャッフルプロトコルの下で提供される証明に関するさらなる情報は、上記で参照した米国仮出願明細書に記載されている。
【０１２０】
一般に、ある応用例では簡素なkシャッフルで十分かもしれない。項目をシャッフルするには、結果的に生じたY要素を生成したのは、元のX要素のうちのいずれであるかを露出せずに、一連の出力要素Y1からYkまたはそれらのシーケンスが、定数暗号化情報に基づいて、元の要素X1からXkまたはそれらの入力シーケンスから導出されたことが確実な場合、各々暗号変換(例えば、累乗法)を使用する必要がある。さらに、十分なレベルの証明のためには多数の反復を必要とする先行技術で周知の、カットアンドチューズタイプの妥当性証明などの、煩わしい妥当性の証明を使用することも必要とせずに、個々にこのようなシャッフルを実現することが希望される。その代わりに、秘密累乗法値cに基づく一連のk独立Chaum-Pedersen証明が本明細書に記載されたように使用される。
【０１２１】
4.一般的ｋシャッフル
シャッフラPがすべての元の指数s1,．．．,skを知る必要があるということが、簡素なkシャッフルプロトコルの明らかな限界である。多くの応用例では、これはこの通りではない。次のステップは、この制約を解消することである。
【０１２２】
一般的ｋシャッフル問題:Zp,X1,．．．,XkとY1,．．．Ykのk要素の2つのシーケンスは、公然と知られている。さらに、定数c∈ZqはPだけに知られているが、cのコミットメントであるC=gcはVに知らされている。Pは、πまたは秘密cに関する情報を露出せずに、すべての1≦i≦kに関して、
【０１２３】
【数３２】
【０１２４】
という特性を有するある種の置換π∈ΣkがあることをVに確信させることが要求される。
【０１２５】
一般的ｋシャッフル証明:この証明は、ベリファイアによって「適切にランダム化された」簡素なkシャッフルと、補助定理2の適用から構築される。
1.Pはシーケンス
【０１２６】
【数３３】
【０１２７】
をランダムに、かつ独立して生成し、シーケンス
【０１２８】
【数３４】
【０１２９】
を露出する。
2.Vは別のシーケンス
【０１３０】
【数３５】
【０１３１】
をランダムに、かつ独立して生成し、これをチャレンジとしてPに与える。
3.Pは公然と
【０１３２】
【数３６】
【０１３３】
をセットし、秘密裏に
【０１３４】
【数３７】
【０１３５】
をセットする。ベリファイアが生成した値を加えるように証明者に要求することによって、証明者が特定の秘密(指数)を選択することを防止し、そうでない場合は暗号の堅固さを保障するために役立つ。
4.Pはシーケンス
【０１３６】
【数３８】
【０１３７】
上で、別のコミットメントD=gd(異なる秘密指数)と逆置換π-1によって簡素なkシャッフルを構築し、簡素なkシャッフルの節にあるように、結果的にシーケンス
【０１３８】
【数３９】
【０１３９】
および対応する証明を生じる(Viは公開だが、viはPに対して秘密であることを想起されたい。)。
5.Pは公然と
【０１４０】
【数４０】
【０１４１】
および
【０１４２】
【数４１】
【０１４３】
をセットし、Chaum-Pedersen証明
【０１４４】
CP(g,Vi,Xi,Ai) (9)
CP(g,Ui,Yi,Bi) (10)
を露出する。
したがって、要素AおよびBのシーケンスは要素XおよびYの入力シーケンスに対応する。
6.値
【０１４５】
【数４２】
【０１４６】
【数４３】
【０１４７】
が公然と評価される。
7.PはChaum-Pedersen証明
【０１４８】
CP(D,A,C,B) (13)
を露出する。
【０１４９】
上記のステップ5-7は、証明者が元のデータを改ざんしていないことを保障するために役立つようにデータを留めておくことを証明者に効果的に要求する(これらのステップは、上記の簡素なシャッフルの説明とは異なる)。簡素なkシャッフル証明が偽造されるか、Chaum-Pedersen証明の1つが偽造されるか、補助定理2の除外集合からタプル(ui,．．．uk)が選択される場合だけ、偽造された証明が生成される可能性がある。したがって、偽造の全体的な確率は
【０１５０】
【数４４】
【０１５１】
だけ上に有界である。
【０１５２】
5.タプルのKシャッフル
関連技術の精通者ならば、前節で、簡素なシャッフルを選択することによって、証明される可能性のあった置換を基本的に「凍結した」ことが理解されるであろう。これによって、前節を、<g>の要素のkタプルのシャッフルまでどのようにして拡張すべきかを理解することが容易になる。k個のl-タプルのシーケンスをk×lの配列と考えると、すべてのシーケンスは同じ置換に従って置換されたが、各行は変更されずにあることを証明するために、単一の簡素なk-シャッフルを利用することができる。したがって、上述のkシャッフルは、k要素の配列の各シーケンスに1回ずつ、l(エル)回実行される(kシャッフルの各々はこの簡素なシャッフルを再利用する)。具体的には、これはエルガマル対のタプルまで拡張される。
【０１５３】
6.投票応用例
投票者の登録、票の形成および分配、票の記憶、および暗号化された電子投票を利用する選挙の実行に関する情報は、2000年3月24日出願の「Multi-Way Election Method and Apparatus」という名称の米国特許出願第09/535,927号明細書、2000年3月24日出願の「Electronic Voting Scheme Employing Permanent Ballot Storage」という名称の米国特許出願第09/534,835号明細書、2000年3月24日出願の「Method, Article and Apparatus for Registering Registrants, Such as Voter Registrants」という名称の米国特許出願第09/534,836号明細書、2000年11月22日出願の「Election System」という名称の米国仮出願第60/252,762号明細書、2001年2月20日出願、「Method and Apparatus for Detection and Correction of Compromised Ballots in Secret, Remote, Electronic Voting Systems」という名称の米国仮出願第60/270,182号明細書、および2001年3月2日出願、「Information Theoretically Anonymous Signatures with Discrete Log Security」という名称の米国仮出願第60/272,883号明細書に記載されている。
【０１５４】
一実施形態では、投票は、
【０１５５】
【数４５】
【０１５６】
という形式のエルガマル対 (または、さらに多くのデータが必要とされる場合は、それらの対のシーケンス) として提供される。ここで、mは投票者の選択した(本明細書に記載の)ある種の標準符号化、αiは投票者によって秘密裏に生成され、hはディーラーのいない秘密共有方式によって構築された公開パラメータである(例えば、T.Pedersen著、「A threshold cryptosystem without a trusted party, Advances in Cryptology EUROCRYPT '91, Lecture Notes in Computer Science」522-526頁。Springer-Verlag、1991年を参照のこと)。投票所が閉まると(投票が終了すると)、オーソリティの独立したコレクションが連続して票をシャッフルする。最後のシャッフルを出力する際、暗号化された票の最後のコレクションが、この閾値方式に従って暗号解読され、明確なテキストの票決が通常の選挙規則によって全景で作表される。
【０１５７】
連続的なシャッフルに参加するオーソリティは、任意の数でよく、選挙の秘密鍵を分担して保持する者とは完全に異なっていてもよい。シャッフリングするオーソリティのすべてが共謀している場合、最後に暗号解読される票のシーケンスは、提出された票の元のシーケンスと一致することだけが可能である。これは、これらの置換の各々が完全に任意だからである。
【０１５８】
各シャッフルは以下の要領で個々のオーソリティによって実行される。
1.βiは、秘密裏に、ランダムに、かつ独立して選択される。
2.各投票
【０１５９】
【数４６】
【０１６０】
は、
【０１６１】
【数４７】
【０１６２】
と、順次、置き換えられる。Chaum-Pedersen証明はこの秘密を露出せずに公開される。
3.秘密指数cによるシャッフルが、結果的に暗号化された投票に関して実行される。
4.ステップ1-2が反復される。
5.この時点で、暗号化されたメッセージは元のメッセージのc乗である。これは、各投票の各座標を1/c乗することによって容易に決めることができる。この演算のChaum-Pedersen証明は等しく容易に提供され、したがって、gとC=gcの役割を単純に逆転させることによってベリファイアを納得させながらも、cを秘密に保つ。
【０１６３】
上記のステップ1および2は、入力データをランダム化することを助け、シャッフリングする前に票の間の関係を選択するなど、入力データを変更することを回避する。Chaum-Pedersen証明は、このランダム化のために追加された加算値が正確であることを保障する。代替実施形態では、ステップ1および2(およびステップ4)は省略される。
【０１６４】
7.セキュリティ保護されたメッセージ符号化
p-1が小さな素因数を有する場合、符号化されたメッセージに関する一部の情報が漏洩する可能性がある。これはシャッフルプロトコルでは問題ではなく、むしろ最初にmiを強力に暗号化する場合に問題である。これが心配するほど重大な問題かどうかは、符号化されるべきメッセージの期待値によって異なる。しかし、この問題は、符号化に特別な配慮をすることによっても解消することができる。各メッセージは、位数が大きな素因数だけを含んでいる部分群に投影することができる。本明細書に記載の大半の実施形態は、|<g>|が素数qである場合に限定されるので、p=2q+1の場合についてのみ議論する。しかし、これらの手法を拡張することによって、より一般的なケースを処理することができる。
【０１６５】
p=2q+1のビット長がbであるとすると、
【０１６６】
2b-1<p<2b
であり、したがって、
【０１６７】
2b-2≦(p-1)/2=q<2b-1 (15)
である。
【０１６８】
本発明では、すべてのメッセージmが、ビット長b-2以下であることを必要とされる。本発明では、各メッセージを標準のように(gα,hαm)として暗号化するのではなく、
【０１６９】
(gα,hα,m2)
として暗号化する。これは、すべてのメッセージは、
【０１７０】
【数４８】
【０１７１】
の順番2の部分群上への同一の自明な投影によって符号化されることを意味している。方程式15は、マップm→m2が定義域上で可逆であることを保障する。逆転させるには、(p-1)/2よりも小さな一意の平方根を取るだけである。したがって、実際のメッセージm2が一旦暗号解読されれば、元のメッセージmを回復するのは簡単なことである。
【０１７２】
8.適切なシステム
図1および以下の議論により、本発明の態様を実施することができる適切なコンピューティング環境の簡潔で一般的な説明が得られる。必須ではないが、本発明の実施形態は、汎用コンピュータ、例えばパーソナルコンピュータまたはウェブサーバによって実行されるコンピュータ実行可能命令、例えばルーチンの一般的なコンテクストで記述されるであろう。関連技術の精通者ならば、本発明の態様(小規模の選挙など)は、インターネット機器、ハンドヘルド装置、ウェアラブルコンピュータ、パーソナルデジタルアシスタンス(「PDA」)、マルチプロセッサシステム、マイクロプロセッサベースの、またはプログラム可能な家庭電化製品、ネットワークPC、ミニコンピュータ、携帯電話または移動電話、セットトップボックス、メインフレームコンピュータなどを含め、他のコンピュータシステム構成で実行することができることが理解されるであろう。本発明の態様は、特に本発明に記載の1つまたは2つ以上のコンピュータ実行可能命令を実行するようにプログラム、構成または構築された専用コンピュータまたはデータプロセッサで実施することができる。実際、本発明で一般に使用する「コンピュータ」という用語は、どの上記装置並びにどのデータプロセッサをも示す。
【０１７３】
本発明は、ローカルエリアネットワーク(LAN)、ワイドエリアネットワーク(WAN)またはインターネットなどの通信ネットワークを介してリンクされている遠隔処理装置によってタスクまたはモジュールが実行される、分散型コンピューティング環境で実行することもできる。分散型コンピューティング環境では、プログラムモジュールまたはサブルーチンは、ローカルメモリストレージとリモートメモリストレージの両方に配置することができる。本発明に記載の本発明は、磁気/光学読み取り可能/取り外し可能なコンピュータディスクなどのコンピュータ読み取り可能媒体に記憶または分配することも、チップにファームウェアとして記憶することも、また、インターネットまたは他のネットワーク(無線ネットワークを含めて)を介して電子的に分配することもできる。関連技術の精通者ならば、本発明に記載のプロトコルの部分は、対応する部分をクライアントコンピュータに常駐させながら、サーバコンピュータに常駐することができることが理解されるであろう。このようなプロトコルに特定のデータ構造とデータの伝送も、本発明の範囲内に含まれる。
【０１７４】
別途記載のない限り、図1の種々のブロックの構成および動作は従来のデザインである。したがって、これらのブロックは関連技術の精通者には容易に理解されるので、本発明ではさらに詳述する必要はない。
【０１７５】
図1を参照すると、システム100の適切な環境は、1つまたは2つ以上の投票者コンピュータまたはクライアントコンピュータ102を含むが、そのそれぞれは、コンピュータに、インターネットのワールドワイドウェブ部分106内のウェブサイトを含めてインターネットによってデータにアクセスし、データを交換することができるようにするブラウザプログラムモジュール104を含む。投票者コンピュータ102は、いずれも周知ではあるが図1には示さない、1つまたは2つ以上の中央演算処理装置または他の論理処理回路構成、メモリ、入力装置(例えば、キーボード、マイクロフォン、タッチスクリーン、およびポインティングデバイス)、出力装置(例えば、表示装置、オーディオスピーカー、およびプリンタ)、記憶装置(例えば、固定された、フロッピー(登録商標)および光学ディスクドライブ)を含むことができる。投票者コンピュータ102は、さらに、オペレーティングシステム、1つまたは複数のアプリケーションプログラム(例えば、ワードプロセッシングアプリケーションまたはスプレッドシートアプリケーション)などの他のプログラムモジュールを含むこともできる。図1に示すように、投票者1,2,3,．．．Nを表すN個の投票者コンピュータ102がある。
【０１７６】
インターネットまたはワールドワイドウェブ(「ウェブ」)106に接続されているサーバコンピュータシステム108または「投票収集センター」は、票の収集、記憶および他の処理の大半またはすべてを実行する。サーバコンピュータ108に接続されているデータベース110は、投票者コンピュータ102と、1つまたは複数の投票所コンピュータ112およびサーバコンピュータ108との間で交換されるウェブページとデータ(票およびシャッフル妥当性証明を含めて)の大半を記憶する。投票所コンピュータ112は、パーソナルコンピュータ、サーバコンピュータ、ミニコンピュータなどであり、インターネット106に接続されたコンピュータに即座にアクセスすることのできない市民または投票者が、本発明に記載のシステム下で電子的に投票できるようにするために、公共の投票所に配置されている。したがって、1つまたは複数の投票所コンピュータ112が公的な場所に配置されているか、または公共選挙で投票者にアクセス可能な場合、投票者コンピュータ102は、個々の投票者の家庭に配置することができる。投票所コンピュータ112は、1つのサーバコンピュータと、LANを介してそのサーバコンピュータに接続された複数のクライアントコンピュータまたは投票者端末を有するローカルエリアネットワーク(LAN)を含むことができ、それによって複数の投票者が同時に、または並行して投票することを可能にする。
【０１７７】
投票所コンピュータはさらに、Dallas Semiconductor社から供給される暗号法iButtonsなどのiButtonsを読むためのiButtonリーダーを含むこともできる。iButtonは、ステンレススチール缶に覆われた16mmのコンピュータチップであり、登録している投票者の署名などの情報を暗号化し暗号解読するために必須の高速算術計算用のマイクロプロセッサを含むことができる。さらなる情報は、http://www.ibutton.comで見ることができる。当然ながら、本発明に記載のコンピュータ読み取り可能媒体、無線周波数識別票(RFID)、1次元または2次元のバーコードまたは他のデータ収集装置、およびこれらに関連したリーダーなどの、iButton以外の他のデータ記憶装置を使用することができる。
【０１７８】
代替実施形態下では、会社役員や取締役の選出など、民間の選挙の状況ではシステム100を使用することができる。この実施形態下では、投票者コンピュータ102は、株主のラップトップコンピュータまたはデスクトップコンピュータであってよく、投票所コンピュータ112は選挙を実施している会社内(例えば、ロビー)に設置された1つまたは複数のコンピュータであってよい。したがって、株主は、会社に行って投票所コンピュータ112にアクセスして票を投じることができる。
【０１７９】
1つまたは2つ以上のオーソリティまたは組織コンピュータ114も、インターネット106を介してサーバコンピュータシステム108に接続されている。オーソリティコンピュータ114のそれぞれは、データベース110に記憶されている電子票を暗号解読するために必須のキーを保持する。閾値暗号化システムは、オーソリティの総数nの部分集合t(すなわち、t<n)が票の暗号解読に賛成することを必要としており、それによって、票の暗号解読にすべてのオーソリティが必要とされる必須条件が回避される。すなわち、閾値暗号化の目的は、群のn人の構成員間で秘密鍵sを共有することであり、事実上の部分集合Tが共同するときにメッセージを暗号解読することができるようにすることである。これが、(t,n)閾値暗号化システムである。プロトコルは、(1)その群間で共同してキーを生成し、(2)秘密鍵を再構成せずにメッセージを暗号解読するものと定義される。オーソリティコンピュータ114は、投票期間終了後にサーバコンピュータシステム108にオーソリティコンピュータ114の暗号解読の分担を提供することができ、その結果、サーバコンピュータシステムは票を暗号解読してその結果を総計することができる。
【０１８０】
さらに、記載の実施形態下では、オーソリティコンピュータの各々は、本発明に記載のように1回の票のシャッフルを実行する。各シャッフルに関して、各オーソリティコンピュータはシャッフル妥当性証明を生成し、そのシャッフル妥当性証明は、暗号化されてサーバコンピュータ108に転送されるか、オーソリティコンピュータによってローカルに記憶することができる。代替実施形態では、オーソリティコンピュータのさらなる集合が提供される。ここで、オーソリティコンピュータの1つの集合は暗号化された票をシャッフルしてシャッフル妥当性証明を生成し、一方、オーソリティコンピュータの第2の集合はその票を暗号解読するために鍵の分担を使用する。
【０１８１】
オーソリティコンピュータ114に類似の、1つまたは2つ以上の任意に選択可能なベリファイアコンピュータ130を提供することもできる。ベリファイアコンピュータは、当該選挙が損なわれていないことを検証するために、選挙の写しを受け取ることができる。例えば、ベリファイアコンピュータは、本発明に記載のように、オーソリティコンピュータのそれぞれからシャッフル妥当性証明を受け取ることができる。ベリファイアコンピュータは、選挙の後で検証を実行することができ、インターネットに接続されている必要はない。実際、検証は、本発明に図示または記載の他のコンピュータによって実行することもできる。
【０１８２】
サーバコンピュータ、ベリファイアコンピュータまたはオーソリティコンピュータが投票者登録プロトコルを実行することも、別個の登録コンピュータ(図示せず)を提供することもできる。登録コンピュータは、指紋データ、声紋データ、デジタル画像比較、および関連技術の精通者に周知の他の技術など、登録者の生物測定データを読み取るための生物測定リーダーを含むことができる。投票者の登録と、検証可能なシャッフルで使用するための匿名証明書の発行については後述する。
【０１８３】
サーバコンピュータ108は、サーバエンジン120、ウェブページ管理構成要素122、データベース管理構成要素124、並びに図示しない他の構成要素を含む。サーバエンジン120は、標準の機能の他に、電子投票プロトコルの部分を実行する。暗号化プロトコルはサーバコンピュータに記憶することができるが、このようなプロトコルの部分は適切な定数と共にクライアントコンピュータにも記憶される。実際、上記プロトコルは、磁気/光学読み取り可能/取り外し可能なコンピュータディスクなどのコンピュータ読み取り可能媒体、半導体チップ(例えば、EEPROM)に記憶されるマイクロコードに記憶し、および分配することも、インターネットまたは他のネットワークを介して電子的に分配することもできる。関連技術の精通者ならば、プロトコルの部分はサーバコンピュータに常駐するが、対応する部分はクライアントコンピュータに常駐することが理解されるであろう。上記プロトコルに特有なデータ構造およびデータの伝送も、本発明の範囲に含まれる。したがって、サーバエンジン120は、権限を付与された投票者に対するすべての必要な票の伝送、票の収集、票の検証(例えば、デジタル署名をチェックし、票に含まれる妥当性の証明の検証を通すこと)、投票の集計、票の暗号解読および/または投票の作表を実行する。代替実施形態下では、サーバエンジン120は、データ収集センターとしてすべての電子投票を収集するだけである。電子投票は、次いで記憶されて、票をシャッフルし、投票集計を暗号解読して選挙結果を提供するためのツールと共に、自治体などの選挙を管理する第三者機関に提供される。同様に、シャッフル妥当性証明などの選挙検査情報は、ローカルに記憶することも、自治体または他の機関に提供することができる。
【０１８４】
ウェブページ構成要素122は、後述するように、電子投票ボックスウェブページなどのウェブページの作成と表示、またはルーティングを取り扱う。投票者およびユーザは、http://www.votehere.netなどのサーバコンピュータ108に関連付けられたURL、または、自治体のURLなどの選挙に関連付けられたURLによってサーバコンピュータ108にアクセスすることができる。自治体は、サーバコンピュータシステム108を直接的に主催または運営したとしても、そのような受け取った電子投票を、サーバコンピュータシステムを操作することのできる第三者の投票権限付与者に転送することもできる。URLまたは本発明で示したリンクまたはアドレスはいかなる資源ロケータであってもよい。
【０１８５】
ウェブページ管理プロセス122およびサーバコンピュータ108は、権限を付与された投票者またはシステム管理者などの権限を付与された人物だけがアクセスすることのできるセキュリティ保護されたセクションまたはページを有することができる。サーバコンピュータ108は、そのようなユーザを認証するために、セキュアソケットレイヤ(「SSL」)およびトークンまたはクッキーを使用することができる。実際、小規模な選挙または不正行為の確率が低い(または、不正行為の結果が比較的重大でない)選挙の場合、システム100は、上記の特許出願明細書に記載の複雑な電子暗号化された票を使用するのではなく、後述するような投票を収集し記憶するための簡素なネットワークセキュリティ対策を使用することができる。ユーザを認証する方法(パスワードの使用によるなど)、セキュリティ保護された伝送接続を確立する方法、およびセキュリティ保護されたサーバとウェブページを提供する方法は、関連技術の精通者には周知である。
【０１８６】
この選挙方式およびシステムは、それぞれの掲示物がデジタル署名され、1つも消去されることのない「掲示板」を使用する。K.Sako,J.Kilian,R.およびCramer, R.Gennaro, B.Schoenmakersの論文を参照されたい。この掲示板はウェブサーバとして実施される。「投票箱」はこの掲示板上に常駐し、すべての暗号化された票を保持する。ウェブサーバのデータを、追記型光ディスク(WORM)永久記憶媒体または類似の装置に書き込むことによって、消去を防止することができる。このような掲示板システムに関するさらなる詳細は、「Electronic Voting Scheme Employing Permanent Ballot Storage」という名称の、米国特許出願第09/534,836号明細書に記載されている。
【０１８７】
本発明の一実施形態はコンピュータを接続するためにインターネットを使用するように本発明には記載されているが、他の代替実施形態も可能であることに留意されたい。例えば、本発明の態様は、スタンドアロンコンピュータによって使用することができる。本発明の態様は、どのような相互接続されたデータ処理マシンによって使用することもできる。本発明に記載の方法またはプロトコルの態様を実施するために、このようなマシンでは、ブラウザを使用せず、クライアントソフトウェアを使用することができる。
【０１８８】
9.選挙の実施例
一般的k-シャッフルプロトコルの一応用例は、電子投票の分野にある。選挙を「普遍的に検証可能」にするために、提出された票は最初に有効な(すなわち、登録された)投票者に絶対的に接続可能である必要がある。票は、「開票」が可能となる前に、検証可能プロセス、すなわち分離プロセスにおいて偽票が提出されることを許可しないことによって何とかして「署名と分離される」必要がある。
【０１８９】
本発明で提示されるプロトコルは、選挙結果に種々の関心を抱くN人の「作表オーソリティ」の集合に依存している。
1.このプロトコルは、完了されるべき作表のために、少なくともt人のオーソリティが正当に振舞わなければならない閾値スキーム(scheme)である。(パラメータtは、任意の値1≦t≦Nになるように選挙前に選択することができる)。したがって、具体的には、オーソリティが自分のシャッフルをいかなる特定の順序で完了することも必須ではなく、また、すべてのオーソリティが参加することさえも必須ではない(特殊なt=Nの場合を除いて)。
2.すべてのオーソリティが共謀したとしても、選挙結果を検証することを希望する外部の監査役によって見つからずに、偽の選挙結果を生成することはできない。
3.個々の投票のプライバシーは、少なくともt人のオーソリティが共謀することによってのみ侵害される可能性がある。
【０１９０】
このプロトコルは以下のように進捗する。
第1:選挙を開始する
1.オーソリティは、まず選挙パラメータについて一致している。
(a)どのような選挙にも必須のパラメータ:有権者の集合、投票の質問、投票の回答、投票スタイル、投票所が開かれ、閉じられる時刻が含まれる。
(b)作表オーソリティの集合:作表オーソリティら自身(この群のオーソリティ数を示すために以下ではNを使用する。)
(c)閾値パラメータt
(d)シャッフルパラメータ1≦s≦t(s=tはそのままの選択)
(e)群Gおよび部分群ジェネレータg∈G(安全な暗号化を達成するために、|g|の素因数は大きくすべきだが、当然ながら、この要件はオーソリティら自身によって理解できるようになっている。)
(f)1つまたは複数の応答に対する標準「ビット符号化」(例えば、ASCII)と小さな「メッセージの重複」整数d≧1。メッセージの重複は、一致した各票の分割を意味し、票の出力形式(各投票の質問への応答をどこに配置するかを示す投票用紙のレイアウトと類似している)に対応する。通常、dは、投票の応答サイズを、収容できる限り小さく選択される。ほとんどの場合、d=1でも機能する。何故ならば、メッセージ重複はそのキーの長さによって判定されるからであり、また、十分に大きなキーの長さ(例えば、1024ビット)は適度な数の質問を有する大部分の票を収容することができるからである。
(g)オーソリティによって実行される(N,t)-秘密共有方式によって作成される群要素h∈<g>。(T.Pedersenの論文を参照のこと。
2.選挙パラメータに関して同意に達すると、オーソリティは全員がそれらに「署名」し、署名された票が、この署名されたパラメータの集合を表現したものとなる。
【０１９１】
第2:投票
1.選挙中(すなわち、「投票所が開いている」間)、各投票者Vは、1つまたは2つ以上の自分の応答を、選挙標準「ビット符号化」(選挙開始期間中にオーソリティによって合意され署名されたもの。上記参照のこと。)によって、メッセージのシーケンスm1,．．．,md∈Gに符号化する。(これに関しては以下でさらに記載する。)「メッセージの重複」dは別の選挙パラメータである(上記参照のこと。)。
2.Vは、暗号化のために、指数α1,．．．,αdを、0≦αj<|g|からアトランダムに個別に選択する。
3.Vは、特定の有権者に試行することによってその応答を認証するため、「暗号化された応答のシーケンス」
【０１９２】
【数４９】
【０１９３】
を、Vによって生成された「添付の」デジタル署名と共に「投票収集センター」に戻す。
4.Vによって提出されたデジタル署名により検証され、かつVが以前に票を投じていなかった場合、中央収集機関によって署名された受領書がVに対して発行される。この受領書は、特定の選挙において当該投票者からの投票が受領されたことを承認するが、(暗号化またはハッシュされた情報さえも)その票の内容に関する情報は含まない。この受領書は、当該投票者に対しても送信することができる。この受領書は、また、当該投票者の票が消失せず、また、悪意をもって削除されなかったことを確認するためにも役立つ。
【０１９４】
第3:結果を作表する
1.最初に、投票者の応答の集合は、それぞれが受領された票の応答の総数である各長さがNcastの2d個のシーケンスに配列される。各シーケンスは、標準の票応答形式の1つの座標に対応する(方程式16)。各シーケンスの項目は投票者によって順序付けられる。各投票者に割り当てられる指標は、一貫性のある限り重要ではない。このようにして、外部オブザーバーは、署名された票が、非常に簡素な方法で変換され、データレイアウトに正しい解釈を適用することによって、依然として署名され受領された応答の同じ集合を表していることを確認することができる。
2.任意の便宜的な順序で、sオーソリティのシーケンスはそれぞれに以下のステップを実行する。
(a)Sをシーケンスに現在入っているオーソリティとする。
(b)Sは、dNcast指数
【０１９５】
1≦βjl≦|g|1≦j≦Ncastおよび1≦l≦d
を別個にアトランダムに選択する。
(c)Sは、群要素
【０１９６】
【数５０】
【０１９７】
および
【０１９８】
【数５１】
【０１９９】
を計算する。さらに、中間Chaum-Pedersen証明が(g,gs(j,l),h,hs(j,l))上に生成される。
(d)Sは次いで、2d個の入力シーケンスを2d個の中間シーケンスに変換する。gαm形式のl(エル)番目の入力シーケンスのj番目の項目は、それにgs(j,l)を乗じることによって変換され、hαm形式のl(エル)番目の入力シーケンスのj番目の項目は、それにhs(j,l)を乗じることによって変換される。変換された項目はすべて同じ順序で維持される。
(e)Sは、ランダムな指数0≦c<|g|と、ランダムな置換πl∈ΣNcastを選択し、hs=gcをコミットする。
(f)Sは次いで、秘密パラメータcおよびπlを使用し、かつ、各一般的ｋ-シャッフルの基礎と同じ簡素なk-シャッフルを再利用して、その2d個の中間シーケンスのそれぞれで(k=Ncastとして)一般的ｋ-シャッフルを実行する。(これは、2d個のシーケンスのそれぞれが同じ秘密の「置換」を受けることを保障する。)
(g)(i)Sは、新しいランダムβによってステップ(d)を繰り返す。
(ii)各票の各座標を1/c乗し、この演算のChaum-Pedersen証明を提供する。このようにしてgとC=gcの役割を単純に逆転させることによってベリファイアを確信させながら、cを秘密に維持する。
(h)(この段階でSは中間シーケンスを明白に計算する必要はないことに留意されたい。それらは外部ベリファイアには後で必要となるが、出力は直接的に計算することができ、中間シーケンスは監査役の要求で構成することができる。しかし、セキュリティ保護の問題から、次のシャッフルを開始する前に監査役に検証を実行させることが要求される場合がある。)
3.次に、2d個のシーケンスのそれぞれの項目を、それらが形成された方法と同様の方法で結合することによって、シャッフルされた票が再構成される。
4.最後に、t人のオーソリティが、各シャッフルされた票で閾値暗号解読プロトコルを実行する。
【０２００】
一般に、作表フェーズは2つのサブフェーズを含む。第1に、作表オーソリティのT≦tの集合は、それぞれに順次、検証可能なk×dシャッフルを実行する(ここで、kは投じられた票の総数である)。各シャッフルからの出力シーケンスと証明は署名され、次の作表オーソリティに渡される。(各作表オーソリティは、その入力が署名のチェックおよび(前回の)シャッフルゼロ知識証明(「ZKP」)と中間Chaum-Pedersen証明のチェックの両方をパスする場合だけ、シャッフルを実行する。) 第2に、シャッフルが完全に1回実行され、検証されると、t人の作表オーソリティの集合は、エルガマル対の最終集合の各mの暗号解読を共同で (かつ検証可能に) 計算するために、秘密鍵の分担を使用する。
【０２０１】
一般に、シャッフルする各オーソリティは、最初に置換の生成を担当するので、入力と出力の対応関係を知ることになる。しかし、シャッフルは行われ、1回のシャッフルの出力は、シャッフルする別のオーソリティによって実行される別のシャッフルへの入力として使用される。したがって、すべてのオーソリティが共謀しない限り、シャッフルするオーソリティの1人として、最初の入力と最後の出力との間の対応関係を知ることは全くない。しかし後述するように、さらなる強化によりこの可能性も排除される。
【０２０２】
第4:選挙を外部的に検証する
要求により、各オーソリティは、
(a)自分の中間シーケンス
(b)1≦j≦Ncastおよび1≦l≦dに対するChaum-Pedersen証明P(g,gs(j,l),h,hs(j,l))
(c)自分のk-シャッフル証明
(d)上記ステップ(g)下のChaum-Pedersen証明
を発行する。
【０２０３】
一般に、「選挙の写し」を公開することができ、これには以下のものが含まれる。
1.投票者のID情報と投票者の公開鍵を含む投票者名簿
2.k投票者の署名済みの票の元の集合
3. tk×dシャッフル(上記の証明を含めて)
4.最後の共有暗号解読の妥当性証明
5.最終的な投票集計
【０２０４】
注意:オーソリティが作表ステップ(上記の作表ステップ2(a)-(h))を実行する順序を変えたいくつかの形態が可能である。具体的には、これらのステップは、代替の実施形態下で交互に重ねることができる。
【０２０５】
注意:外部検証フェーズは、作表の続行中に実行することも、その後実行することもできる。オーソリティはそれらの段階のパラメータを保存するだけでよい。
【０２０６】
図2に参照される概略図は、方法200として示され、選挙に対するシャッフルプロトコルの基本的な応用例を示している。ブロック202では、3つの暗号化された票が、投票者Joe Smith, Sally Jones,およびIan Kelleighのそれぞれに1つずつ提出される。ブロック204では、投票者のリストすなわち名簿が、ブロック206に示される暗号化された票から分離される。その後、ブロック208に示される票のシャッフルを受けた集合を生成するために、票のワンウェイ再暗号化が実行される。この1回目のシャッフルに基づいて、ブロック210に示すようなシャッフル妥当性証明が生成される。このシャッフル妥当性証明によって、第三者機関は、すべての入力されたデータ(投票)に同じ演算が適用されたこと、および、票の変更がまったく行われなかったことを保障することができる。
【０２０７】
(既にシャッフルを受けた)票の2回目のシャッフルが実行されて、ブロック212に示すような2回目のシャッフルを受けた票の集合を生成する。ここでもまた、ブロック214に示すようなシャッフル妥当性証明が生成される。ブロック212のシャッフルを受けた票が3回目のシャッフルを受け、ブロック216下で最後のシャッフルを受けた票の集合を生成する。3回目のシャッフルに基づいて、第3のシャッフル妥当性証明218が同様に生成される。すなわち、この実施例では、3×3の配列が提供される。このシャッフリングに引き続き、票が暗号解読されて、ブロック220に示すような投票集計を生成する。第三者機関は、各シャッフラが選挙の公平性を維持したことを保障するために、特に各シャッフル妥当性証明を分析することによって選挙を検証することができる。
【０２０８】
シャッフルプロトコルをサブルーチンに効果的に分離し、電子投票方式などの種々の応用例に使用することができることが上記で示されている。第1のサブルーチンは、証明者とベリファイアとの間の、スケールされる反復対数乗法証明の機能を提供する。第2のサブルーチンは、簡素なシャッフルプロトコルの機能を提供し、スケールされる反復対数乗法証明を使用する。その後、第3のサブルールチンは、一般的シャッフル機能を実施するが、そこでは、シャッフラは簡素なシャッフルの第2のサブルーチン上に構築された指数を知らない。第4のサブルーチンは、kタプルの要素のシャッフリングまで第3のサブルーチンを拡張する。
【０２０９】
図3を参照すると、スケールされる反復対数乗法証明を実施するためのルーチン300が示されている。ブロック302では、初期暗号パラメータの合意が、例えば投票機構などによって行われる。これらの初期パラメータは、群(例えば、Zp)、部分群オペレータg、群のサイズG、および生成された部分群pおよびqを含む。この情報は、n人のシャッフラまたはオーソリティコンピュータ114およびベリファイアコンピュータ130に提供される。
【０２１０】
ブロック304では、シャッフラ(または証明者P)は秘密指数cを選択し、部分群ジェネレータgに基づいてCを生成する。さらに、シャッフラは、受け取ったXおよび1からkまでのインデックスiに対するY値を受け取るか、または生成し、X、Y、およびCをベリファイアに提供する。
【０２１１】
ブロック304では、シャッフラはさらに、ランダム指数をriとして秘密裏に生成するが、これは、部分群gジェネレータに基づいて、0からkまでのiの各値に対して値Riを生成するために使用される。同様に、ブロック304下では、シャッフラは、生成されたランダム指数riを使用してWiとZiを生成する。
【０２１２】
ブロック306では、シャッフラは、1からkの各要素に関して、RI-1,Xi,Ri,WiおよびYi,C,Wi,Ziの値にChaum-Pedersen証明を提供する。Chaum-Pesersen証明に関するこれらの値は、次いで値ziとR0と共にベリファイアに提供される。ベリファイアは次いで、ブロック308で、証明を受諾または拒否するために、証明の正確さを検証する。すなわち、ベリファイアは部分群ジェネレータgの指数として各zが対応するZを生成することを確認し、各Chuam-Pedersen証明をチェックし、ziの積がzと等しいことおよびz乗された値R0はRkに等しいことを確認する。
【０２１３】
図4を参照すると、上記のように簡素なシャッフルプロトコルを実行するルーチン400が示される。ブロック302に引き続き、ブロック404はブロック304と類似しているが、シャッフラは、Y要素を生成するために、X要素を置換πによってシャッフルする。ブロック406のベリファイアは、チャレンジとしてランダム値tを生成する。これに応答して、シャッフラはブロック408で、部分群ジェネレータgに対する指数としてtを使用して、秘密裏に値Tを生成するが、この値Tとシャッフラの秘密指数cとを組み合わせると、シャッフラは秘密裏に値Sを生成することが可能となる。図から分かるように、シャッフラは次いで値UおよびVを公然と生成し、(g,C,T,S)に対するChaum-Pedersen証明をブロック410下で提供する。ブロック410で、シャッフラはまた、1からkまでの一連のiの要素XおよびYのそれぞれに対するスケールされる反復対数乗法証明として証明データを生成する。この証明データは次いで、ブロック412でベリファイアに提供される。
【０２１４】
ベリファイアは、証明データの正確さを検証し、それを受諾または拒否する。すなわち、ベリファイアは、UおよびVのシーケンスに対して上記の、スケールされる反復対数乗法証明プロトコルを実行し、コミットメント値Cをチェックする。
【０２１５】
図5を参照すると、シャッフラが指数を知らない場合の、一般的シャッフルプロトコル500が示されている。プロトコル500の初期ステップは、ベリファイアがシャッフラの秘密指数にランダム化要素を加えることを除き、400の初期ステップと類似する。ブロック502に示すように、シャッフラは初期値のランダムシーケンスを秘密裏に生成するが、これは、初期シーケンス
【０２１６】
【数５２】
【０２１７】
を生成するために、部分群ジェネレータgによって指数として使用される。同様に、ブロック504では、ベリファイアは、1からkまでの値iに対する要素eの別のシーケンスを生成し、そのシーケンスをチャレンジとしてシャッフラに提供する。ブロック506では、シャッフラは前のシーケンスにそのシーケンスのチャレンジeを秘密裏に加え、その時までに一連の値
【０２１８】
【数５３】
【０２１９】
を公然と生成する。
【０２２０】
ブロック508では、シャッフラは、別の秘密裏に(シャッフラが選択した異なる秘密指数dを使用する)生成されたコミットメントDによってシーケンスU上に簡素なkシャッフルを構築し、値Vのシーケンスを生成する。次いで、公然と、シャッフラは1からkまでのインデックスに対する値AおよびBのシーケンスに対するChaum-Pedersen証明を露出し、そのシーケンスの積を値AおよびBとして公然と生成して、図示するようにD、A、CおよびBの間の関係にChaum-Pedersen証明を提供する。ブロック510の下では、この証明データはベリファイアに提供され、ベリファイアはこの証明データをブロック512の下で検証する。
【０２２１】
10.検証可能なシャッフルによって匿名証明書を発行する
上記で提示されたのは、暗号化データを検証可能にシャッフリングする新しくて効率的な構築と、この構築を「普遍的に検証可能」な電子選挙システムを実行するために使用することのできる特別な方法である。このシステムでは、投票時に収集された票データを「シャッフル」または「匿名化」することは、選挙オーソリティの集合に依存する。このプロセスは、すべての票が投じられた後、票が暗号解読されて作表される前に行われる。この妥当性の構築は、1人または2人以上の選挙オーソリティが、最終的な選挙の写しを検査しているいずれからも見つからずに、元の選挙データに変更を加えることを防止する。
【０２２２】
この手法の欠点は、選挙の公平性と同様の強固な機構によっては、投票者の匿名性が保護されないということである。選挙の公平性は、単に計算上の処理のしにくさによって保護される。すなわち、選挙オーソリティが、検出されずに偽の選挙結果を生成することは、たとえ全員が共謀したとしても基本的には不可能である。しかし、共謀することによって、彼らは、比較的容易にいかなる個々の投票者の票の内容をも判断することができる。
【０２２３】
この弱点を解消する新しい選挙プロトコルを構築するために、同じ基本的なシャッフル構築を使用することができる。このアイディアは、シャッフリングを、選挙の登録または票の要求のフェーズに移動し、それによって、厳重な管理と選挙の資格規定の検査、すなわち登録した投票者による票だけを数え、同一投票者からの複数の票は受理しないといった管理と検査を損なうことなく、投票者の識別を匿名化するということである。これが達成されると、もはや票を暗号化する必要さえなく、「普通文で」作表を実行することができる。これは、明らかに検査するのに容易なプロセスである。
【０２２４】
この構成を「匿名登録プロセス」の一部として使用するというアイディアは、投票以外にも応用例がある。サーバまたはファイルなどの資源へのアクセスは権限を付与された人員に限定される必要があるが、権限を付与された人員が個人の識別を保護することを希望する場合はいかなる状況でも、この構成を使用して両方の要件を同時に満たすことができる。例えば、グループ署名の応用例は、本発明に記載のプロトコルにおしなべて適用することができる。本発明では、一般に「投票者」という用語は、本発明に記載の一部またはすべてのプロトコルを利用するいかなる個人または組織を意味する。
【０２２５】
「プロトコルの概要」
2つの異なるプロトコルの形体が提供され、どちらも同じ高レベルの情報の流れに従う。各プロトコルは、公開鍵の集合がいくつかの中央認証データベースまたは証明書サーバに記憶されていることを推定するところから始まる。各対応する秘密鍵は、1人の、しかもたった1人の有権者にのみ知られている。さらに、公開鍵と個々の投票者の対応関係は、証明書サーバを管理する1つまたは2つ以上のエンティティによって知られる(これらの公開鍵/秘密鍵対の厳密な形式は、プロトコルの異なる形体ごとに若干相異する。)。実際には、公開鍵は、すべての識別情報を公開鍵と共に単一のフォーマットされたデータとして結合する「デジタル証明書」の形式で包まれるる可能性がある(これは、広く受け入れられている公開鍵基盤すなわちPKIが準拠している規則である。)
通常、このような鍵と証明書の分配は、厳重に管理された登録プロセスによって達成される。このプロセスの最も安全なものは、証明書生成時に投票者が物理的に識別される「本人による」登録プロセスであろう(このような登録プロセスは、米国特許出願第09/534,836号明細書で詳述されている。)。プロトコルに存在する2つの異なるタイプの証明書を区別することが重要である。第1のタイプは、上記の証明書(「標準証明書」)であり、この場合、公開鍵と個々の人物との間の関係が公然と、または少なくとも広く知られている。第2のタイプは、上記の初期登録のフェーズに続くプロトコルの段階で分配される証明書(「匿名証明書」)である。これらの匿名証明書は、少なくとも異なる公開鍵を含んでいるが、所与の匿名証明書の所有者を知っている個人だけが所有者自身であるという事実によって相互に区別することができる。このプロトコルの目的は、
標準証明書の1つを所有する個人だけに、匿名証明書を発行する
ことを保障することである。
【０２２６】
投票応用例などの大半の応用例では、このプロトコルの目的は、さらに、
各個人に、その個人が有する標準証明書と同数だけ匿名証明書を発行する(通常、標準証明書の各所有者は標準証明書を1つだけ有する。)
ことを保障することである。
【０２２７】
標準証明書の登録が完了すると、プロトコルの各形体はそれぞれに以下のように進められる。
【０２２８】
初期化:未処理の公開鍵の集合Kが証明書サーバ(例えば、サーバ108)で構成され、標準証明書の集合に関連付けられた公開鍵の集合になるように初期設定される。各個人が登録して、例えば標準デジタル証明書を受け取るという、各個人の初期登録プロセス中に公開鍵の集合が生成される。この初期登録プロセスの下で生成された公開鍵は一緒にプールされて、集合Kを生成する。各個人は、集合Kの公開鍵の1つに関連付けられた秘密鍵を保持する。
【０２２９】
1.個人Pは、(インターネットなどの)デジタル通信チャネルを介して証明書サーバSと接触し、匿名証明書の取得を希望することを示す。
2.Sは、(Sの秘密鍵を含む)公開鍵の集合H⊂KをPに戻し、集合J=K-Hを記憶する。(理想的には、H=KかつJ=0だが、通信帯域幅の理由から、上記包含が適切であろう。例えば、公開鍵の集合が非常に大きく、伝送するため帯域幅の制約の効果でそのような鍵の大きな集合の伝送が限定される場合、公開鍵Kの部分集合を個人Pに提供するかもしれない。他の理由から、証明書サーバは、公開鍵の部分集合だけを戻すことを希望する場合もある。)
3.Pは、すべてHである場合のある部分集合M⊂Hを選択し、
【０２３０】
M'=H-M
【０２３１】
をセットする。
4.Pは、Mのシャッフル変換であるＨ'を計算する(上節および次節を参照のこと。)。Pは、また、フォーマットされた匿名証明書要求を生成する。これは、ランダムな公開/秘密鍵対を生成し、指定の証明書形式に適合するようにある種の「ランダムID」データで公開部分をフォーマットすることによって行われる(当然ながら、Pは、何らかの安全な場所に秘密部分を記憶することも必要である。)。
5.PはH'、MおよびM'を、
(a)Sまたはどの監査役に対しても、H'が実際にMの有効なシャッフル変換であることを証明するシャッフルの写し、または妥当性の証拠、
(b)特定の要素h∈H'に対応する秘密鍵をPが知っているという証拠、
(c)フォーマットされた証明書要求
と共にSに戻す。
6.Sは、5aと5bの妥当性と共にH=M∪M'であることを確認する。
(a)この確認の1つでも失敗した場合、SはPに失敗であることを示し、Pとの通信を停止するか、またはPに再試行の適切な機会を与える。
(b)双方のチェックとも通った場合、
i.匿名証明書が、標準証明書の各所有者に1回だけ発行されることを目的とされている場合、Sは、
【０２３２】
H''=H'-{h} (17)
K=J∪M∪H' (18)
【０２３３】
をセットし、また、なんらかの理由で、匿名証明書を、標準証明書の各所有者に複数回発行することが望まれる場合、Sは、
【０２３４】
K=J∪M'∪H' (19)
【０２３５】
をセットする。および
ii.Sは、フォーマットされた証明書要求にデジタル署名し、それによって匿名証明書を作成し、(署名した)証明書をPに戻し、後の匿名認証のためにその証明書をデータベースに記憶する。
7.プロセスは、次に、新たなPの始めから続行し、Kは適切に変更される。
【０２３６】
すなわち、個人Pは、証明書サーバSに対して、その個人の選択した部分集合Mの公開鍵の1つに関連付けられた秘密鍵をその個人が保持していることを、公開鍵の部分集合Mをシャッフリングすることによって、それが公開鍵のいずれであるかを露出することなく証明することができる。匿名証明書の発行後、証明書サーバは、次の匿名証明書を要求する個人が使用するために、公開鍵のシャッフルされた集合から1つのシャッフルされた公開鍵を除去する。
【０２３７】
「匿名認証および署名」
上記シャッフルプロトコルを基本的に構築することにより、次の問題が解決されれる。
一般的ｋシャッフル問題:Zp,S={X1,．．．.Xk}およびT={Y1,．．．,Yk}のk要素の2つのシーケンスは公然と知られている。さらに、定数c∈ZqはPにだけ知られているが、cのコミットメントC=gcはVに知らされている。Pは、πまたは秘密cに関する情報を露出せずに、すべての1≦i≦kに関して、
【０２３８】
【数５４】
【０２３９】
という特性を有するある種の置換π∈Σkが存在することを、Vに確信させることが要求される。
【０２４０】
上記シャッフルプロトコルでは、この問題に対する解決法は、まずPおよびVによって実行される対話式証明プロトコルとして提示されるが、これはFiat-Shamirヒューリスティックの標準的な応用例では非対話式である。本発明では、T(S,T,g,C)によって、結果的に生じる検証の、シャッフラPによって生成される写しを示す。
【０２４１】
「匿名認証プロトコル1」
このプロトコルの形体では、
公開鍵は要素h∈<g>⊂Zpであり、対応する秘密鍵は単純に秘密指数s=logghである。
【０２４２】
集合Hは、常にすべてのKに対して取られなければならない。すなわち、H=Kである。
【０２４３】
集合Mも、常にすべてのHでなければならない。すなわち、M=HかつM'=0である。
【０２４４】
Sは、各認証セッション中に変更されるべき1つの追加のモジュラ整数G∈<g>を記憶しなければならない。初期設定で、Gはgに等しくなるようセットされる。
【０２４５】
プロトコルは、前節に記載の要領で以下の変更を加えるように進められる。
1.ステップ2で、SはさらにGをPに戻さなければならない。
2.ステップ5aでPに戻された写しは、正確に、
【０２４６】
T(M,H',G,C)=T(H,H',G,C) (21)
【０２４７】
である。
3.ステップ5bの秘密鍵ノリッジの証明は、
【０２４８】
h'=Ge (22)
【０２４９】
を満足させる特定の値h'∈H'(またはそのインデックス)と共に、正確に整数e=cs∈Zqである。
このような値は1つ、しかもたった1つだけであることに留意されたい。cはランダムでありsから独立しているので、eを露出してもsに関する情報は露出しないことにさらに留意されたい。Sが対応するチェックを実行するのは、単純に方程式22を検証するためである。
4.方程式22のチェックがすべて通った場合、1および2で実行された変換に加え、Sは変換
【０２５０】
G=C (23)
【０２５１】
も実行する。
【０２５２】
「匿名認証プロトコル2」
第1の匿名認証プロトコルの短所は、Pによってシャッフルされるべき集合は常にKの全てでなければならないということである。集合H=Kのすべての公開鍵に同じ変換(塁乗法)が適用される。すべての検査要件が満たされるまで、写しT(H,H',G,C)のそれぞれは記憶しておかなければならないということによって、標準証明書の元の集合が大きい場合、多量のデータが作成される可能性がある。この問題は、次の第2の匿名認証プロトコルによって扱われる。
【０２５３】
このプロトコルの形体では、
公開鍵は要素(k,h)∈<g>×<g>の対であり、対応する秘密鍵は単純に秘密指数s=logkhである。
【０２５４】
集合HはPの公開鍵を含まなければならない。これは種々の方法で達成することができる。
1.SおよびPは、Hのこの特性が達成されるまで一連の再試行に関与することができる。
2.または、初期登録において、標準証明書を「ブロック」に割り当てることができる。Pが最初にSに接触したとき、Pは自分のブロック番号がある限り、自己を特定する。
【０２５５】
効果的に、各個人Pに対して異なる基数Gがセットされ、個人は公開鍵の全体集合(その部分集合は、投票者の公開鍵対を含む)の部分集合だけをシャッフルする。このプロトコルは、前節に記載の要領で、次の変更に進められる。
1.ステップ5aでPに戻された写しは対の集合に対するシャッフルの写しである。この構成に関する詳細は上記を参照されたい。
2.ステップ5bの秘密鍵ノリッジの証明は、秘密鍵を露出することを防止するために、若干複雑にする必要がある。
(a)PはＳに対して、特定の対(k',h')∈H'、または、Pの秘密鍵に属する対の新たなインデックスであるインデックスを示す。すなわち、h'=(k')sである(このような対は、シャッフル演算がkとhの両方を同一の秘密指数cに指数のベキに上げるので、このような対は一意に存在することに留意されたい。したがって、hc=(kc)sの場合のみ、h=ksである。)。
(b)PはSに対して、Pがs=logg'h'を知っているという「ゼロ知識証明」を露出する(Chaumの論文を参照のこと。)。これは、Pが、対応する秘密鍵を露出せずに対応する秘密鍵を知ることを証明する。
3.Sが実行しなければならない対応するチェックは明らかである。
(a)SはPのシャッフルの写しの妥当性をチェックする。
(b)SはPがs=logg'h'を知っているというPの証明の妥当性をチェックする。
【０２５６】
注意:代替の実施形態下では、集合Kの一部またはすべての鍵(すなわち、部分集合H)は、いずれか一個人が匿名証明書を要求する前に、ある個人またはオーソリティによってシャッフルすることができる。すなわち、公開鍵のプールは、上記匿名認証プロトコルのどちらかが、要求している特定の個人に利用される前に、十分にランダム化することができる。したがって、公開鍵の小さな部分集合は、プロトコル2の下で各個人により選択することができる。
【０２５７】
図6を参照すると、匿名証明書分配の第1の変形体を実施するためのルーチン600の一例が示されている。ブロック302で暗号パラメータを初期化した後、公開鍵Hの標準集合がブロック604で提供されるが、これは、登録者または投票者の集合がそれぞれに(ブロック606に示すように、個々に保持した秘密鍵sに対応する)公開鍵hを登録して提出した後、登録サーバによって収集することができる。ブロック608では、部分群ジェネレータgがGにセットされる。
【０２５８】
ブロック610では、1人または2人以上のオーソリティによって実行される選択的ランダム化を実行することができる。ブロック610では、(G,C=Gc)をシャッフルコミットメントとして使用して、順次、各オーソリティが検証可能なシャッフルを標準公開鍵Hの集合で実行するが、ここでcはオーソリティによって保持される秘密鍵である。各オーソリティは、公開鍵のシャッフルされた集合H'を、上記の一般的シャッフルを使用してシャッフル検証の写しT(H,H',G,C)と共に戻す。検証の写しが正しい場合、登録サーバは、代入G=CおよびH=H'を実行し、前の値を、後の検査のためにシャッフル検証の写しと共に記憶する。ブロック610の下の選択的ランダム化は、前の初期化の一部として、あるいは後述する匿名証明書の生成のいかなる中間段階でも実行することができる。
【０２５９】
ブロック612-618は、集合Hの公開鍵hの1つを以前に提供した個人による匿名証明書の単一の要求を示す。これらのステップは、要求している各登録者によって反復される。ブロック612では、登録者(または、より正確には、投票者のコンピュータ102)は匿名証明書に対する要求を生成する。これに応答して、登録サーバは、ブロック614の下で値Gと公開鍵の集合Hを取り出し、それらを登録者に戻す。ブロック616では、登録者は、上記の一般的シャッフルプロトコル下で、シャッフルと、対応する検証の写しを計算し、各インデックス1≦j≦kに対してT(H,H',G,C)および(登録者にのみ知られているcsに等しい)eを戻す。さらに、ブロック616では、登録者は、ある種のランダムな識別情報によってPKI証明書要求を生成する。このランダムな識別情報は、登録者が使用するために選択したいかなるユーザIDであってもよいが、これは登録者を識別するために使用することはできない。ブロック616の下では、登録者は、また、この要求に基づいて、対応する秘密鍵を安全に記憶する(秘密鍵sjとは異なる)。
【０２６０】
ブロック618では、登録サーバはシャッフル検証の写しをチェックし、h'j=Geであることを確認する。これら双方のチェックが通ると、登録サーバはH=H'から証明書に対する登録によって使用される1つの公開鍵を減じた(h'j)、G=C、およびk=k-1をセットする。検査のために、ブロック618の登録サーバは、登録者の検証の写し(すなわち、T(H,H',G,C))も記憶する。登録サーバは、また、登録者に戻されるPKI証明書を作成するために、証明書要求Rにデジタル署名する。このルーチンは次の登録者の要求の準備ができる。
【０２６１】
図7を参照すると、ルーチン700は匿名証明書の分配に関して上記した第2の形体を示す。ルーチン700はルーチン600に類似している。ブロック704は、集合Hが公開/秘密鍵対を含んでおり、適切な部分集合であり得ることを除いて、ブロック604に同様である。同様に、ブロック710は、図7に示すようにブロック610に類似している。
【０２６２】
要求を受け取った後、ブロック714で登録サーバは公開鍵対の集合Hを取り出す。代替の実施形態下で、登録サーバは、登録者の公開鍵を含む部分集合だけを取り出す。ブロック716で、登録者は公開鍵対の部分集合Mを選択し、M'=H-Mをセットする。登録者は、MのシャッフルH'と、対応する検証の写し(T(M,H',g,C))を計算し、登録者は図7に示す秘密指数を知っているというゼロ知識証明Pを生成する。さらに、登録者は、上記のように、ランダムな識別情報によってPKI証明書要求を生成し、秘密鍵を記憶する。
【０２６３】
ブロック718では、登録者サーバはシャッフル検証の写しとPとをチェックする。どちらのチェックも通った場合、登録者サーバは、Kをセットし(方程式(18)または(19)の下で公開鍵対(g'j,h'j)を除去し)、k=k-1をセットする。ルーチン700の残りの部分は、ルーチン600の残りの部分とほぼ同一である。
【０２６４】
11.結論
当業者ならば、本発明の概念は、インターネット以外の種々の環境で使用することができることが理解されるであろう。例えば、この概念は、電子メール投票、トランザクション、フォームが処理され記憶される電子メール環境で使用することができる。一般に、ウェブページまたは表示内容(例えば、掲示板)は、HTML、XMLまたはWAP形式、電子メール形式、または情報を表示するのに適した(文字/コードベース形式、ビットマップ形式、およびベクトルベース形式を含めて)いかなる他の形式であってもよい。同様に、インターネットの代わりに、ローカルエリアネットワーク、ワイドエリアネットワーク、またはポイントツーポイントのダイヤルアップ接続などの種々の通信チャネルを使用することができる。種々のトランザクションもまた、クライアント/サーバ環境ではなく、単一コンピュータ環境内で実施することができる。各投票者コンピュータまたはクライアントコンピュータは、サーバコンピュータまたはシステムと対話するハードウェアまたはソフトウェアのいかなる組み合わせを含むこともできる。これらのクライアントシステムは、テレビジョンベースのシステム、インターネット機器、およびトランザクションを実行することができる種々の他の消費者製品を含むことができる。
【０２６５】
本発明で一般に使用される「リンク」という用語は、ネットワーク上にサイトまたはノードを有する投票オーソリティの表示内容などの、ネットワーク上の資源を識別する任意の資源ロケータを示す。一般に、投票者コンピュータ、端末およびサーバなどのハードウェアプラットフォームを本明細書では記載しているが、本発明の態様は、ノードを識別するための対応する資源ロケータを有するネットワーク上のノードにおしなべて適用可能である。
【０２６６】
文脈上明らかに要求されない限り、詳細な説明並びに特許請求の範囲を通して、「備える」「備えている」などの語句は、排他的意味または網羅的意味とは反対の、包含的な意味、すなわち「含むが、これに限定されない」という意味に解釈されるべきである。単数または複数を使用する単語も、それぞれに複数または単数を含む。さらに、「本発明において」「本発明では」という語句、および類似の意味の単語も、本願で使用される場合、本願を全体として意味しており、本願のいかなる特定の部分をも意味しない。
【０２６７】
本発明の例示の実施形態についての上記の説明は、本発明を、開示された正確な形式を網羅し、限定することを目的としていない。本発明の特定の実施形態および実施例を説明する目的で本明細書に記載したが、種々の異なる形態も本発明の範囲内で可能であることを関連技術の精通者ならば理解するであろう。本発明の教示するところは、上記の電子投票システムだけでなく他の暗号化の応用例にも適用することができる。例えば、このプロトコルの応用例には、匿名性と検査可能性の双方を必要とする電子商取引も含まれる。この実施例は、電子マネーによる支払い方式(「電子キャッシュ」)である。
【０２６８】
上記の種々の実施形態は、さらなる実施形態を提供するように組み合わせることができる。上記の参照および米国特許および出願のすべては、参照により本発明に組み込まれている。本発明の態様は、本発明のさらに別の実施形態を提供するために種々の特許および出願のシステム、機能、および概念を利用するように、必要に応じて変更することができる。
【０２６９】
上記の詳細な説明に鑑みて、本発明にはこれらおよび他の変更を加えることができる。一般に、特許請求の範囲で使用される用語は、本発明および特許請求の範囲で開示された特定の実施形態に本発明を限定するものと解釈されるべきでなく、データの安全性を実現するために特許請求の範囲で動作するすべての暗号化システムおよび方法を含むものと解釈されるべきである。したがって、本発明は開示によって限定されるのではなく、本発明の範囲は特許請求の範囲によって完全に確定されるべきである。
【０２７０】
本発明の特定の態様は特許請求の範囲の形式で表現されるが、いかなる数の特許請求の範囲形式においても本発明の種々の態様が検討される。例えば、本発明の1つの態様だけがコンピュータ読み取り可能媒体として実施されるように記載されているが、他の態様も同様にコンピュータ読み取り可能媒体として実施することができる。したがって、本発明の他の態様のためにそのような追加の請求項の形式を追求するため、本願出願後に追加の請求項を加える権利が留保されている。
【図面の簡単な説明】
【０２７１】
【図１】本発明の実施形態を実施するために適切な環境を示すブロック図である。
【図２】3人の投票者と3回のシャッフルによる1つの簡素な投票に適用された本明細書に記載のシャッフルプロトコルの簡素な実施を示す概略図である。
【図３】スケールされる反復対数乗法証明プロトコルを示すフロー図である。
【図４】シャッフラが暗号指数を知っている簡素なシャッフルプロトコルを示すフロー図である。
【図５】シャッフラが暗号指数を知らない一般的なシャッフルプロトコルを示すフロー図である。
【図６】匿名証明書分配ルーチンを示すフロー図である。
【図７】図6の匿名証明書分配ルーチンの代替実施形態を示すフロー図である。
【特許請求の範囲】
【請求項１】
コンピュータネットワークに結合したサーバコンピュータを備えたシーケンスの受信を行うコンピュータシステムにおいて、前記サーバコンピュータは、
個々のデータファイルを示す電子データのシーケンスを受信し、
少なくとも１つの秘密鍵を用いて前記電子データのシーケンスを匿名で置換し、および前記サーバコンピュータが該電子データのシーケンスとの対応関係を知っているシャッフルされた電子データのシーケンスを生成するように暗号変換を行うよう構成されたコンピュータシステムであって、
前記サーバコンピュータは、
第１の暗号化されたデータのシーケンスの暗号化されない値を前記生成することは、第２の暗号化されたデータのシーケンスの暗号化されない値を前記生成することと等価であるとの証明に基づいて前記置換を行うために、正確さの証明を生成するようさらに構成されたことを特徴とするシステム。
【請求項２】
前記受信した電子データのシーケンスは、前記サーバコンピュータに知られていない鍵によって群Zpまたは楕円曲線を用いて暗号化され、および前記サーバコンピュータは、
一連のランダムに生成された値eiを受信し、および少なくともいくつかの前記ランダムに生成された値eiの少なくとも一部に基づく非反復証明として前記正確さの証明を生成するようさらに構成されたことを特徴とする請求項１に記載のシステム。
【請求項３】
各々が複数の公開鍵の１つに対応する秘密鍵を有する、対応する複数の個人からの前記複数の公開鍵を受信し、
１つの秘密鍵を有する前記複数の個人の１人から証明書の要求を受信し、
前記複数の公開鍵のうち少なくとも１つの部分集合を前記要求している個人に提供し、
第１の暗号化されたデータのシーケンスの暗号化されない値を前記生成することは、第２の暗号化されたデータのシーケンスの暗号化されない値を前記生成することと等価であるとの証明に基づいて前記置換を行うため、前記複数の公開鍵のシャッフル、および正確さの非反復証明を受信し、
前記正確さの証明をチェックし、
前記1人の個人に証明書を発行し、および
前記複数の公開鍵を前記１つの公開鍵だけ減らすよう構成されたことを特徴とする請求項１に記載のシステム。
【請求項４】
前記電子データのシーケンスは、公開鍵であり、並びに
前記サーバは、個人からの要求に対応して、前記公開鍵の１つに一意かつ数学的に関連付けられた秘密鍵を前記個人が有するかどうかをチェックし、および
前記有する場合は該個人に証明書を発行するようさらに構成されたことを特徴とする請求項１に記載のシステム。
【請求項５】
前記電子データのシーケンスは、電子選挙における投票の選択のシーケンスであることを特徴とする請求項１に記載のシステム。
【請求項６】
前記正確さの証明は、前記電子データのシーケンスおよび前記生成されシャッフルされた電子データのシーケンスが与えられれば、前記電子データのシーケンス中の解読されたものすべてについて、対応する置換され解読されたものが前記生成されシャッフルされた電子データのシーケンス中に存在するような置換が存在することを証明することを特徴とする請求項１に記載のシステム。
【請求項７】
前記置換のための前記正確さの証明は、
第１の暗号化された線形因子のシーケンスによって定められる第１の多項式は、第２の暗号化された線形因子のシーケンスによって定められる第２の多項式の一定の倍数に等しいとの証明に基づくことを特徴とする請求項１に記載のシステム。
【請求項８】
コンテンツとして、電子データのシーケンスと関連するデータとを格納するコンピュータ読取可能な媒体であって、前記電子データのシーケンスはコンピュータに実装される方法によって処理されてシャッフルされ、前記方法は、
電子データのシーケンスを受信するステップと、
少なくとも第１の秘密鍵を用いて前記電子データのシーケンスを匿名で置換し、および第１のシャッフルされた電子データのシーケンスを生成するように秘密のワンウェイ暗号変換を行うステップと
を備え、第１の暗号化されたデータのシーケンスの暗号化されない値を前記生成することは、第２の暗号化されたデータのシーケンスの暗号化されない値を前記生成することと等価であるとの証明に基づいて前記置換を行うために、正確さの証明を生成するステップをさらに備えたことを特徴とするコンピュータ読取可能な媒体。
【請求項９】
前記受け取った電子データのシーケンスは、モジュラス整数値p(Zp)を有する整数の環である基礎となる数学的群によって暗号化されることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１０】
前記電子データのシーケンスと前記正確さの証明を受け取るコンピュータネットワーク内の論理ノードであることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１１】
コンピュータ読取可能なディスクであることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１２】
前記電子データのシーケンスと前記正確さの証明を含む生成されたデータ信号を伝送するデータ伝送媒体であることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１３】
コンピュータシステムのメモリであることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１４】
投票オーソリティサーバコンピュータへのインターネット接続リンクであることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１５】
前記電子データは、少なくとも公開鍵または公開鍵に関連付けられたデジタル証明書を含むことを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１６】
前記電子データのシーケンスは、電子投票または電子投票の選択であることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１７】
前記受信した電子データのシーケンスは、基礎となる楕円曲線群で暗号化されることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１８】
前記正確さの証明は、正確さの非反復証明であることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１９】
電子データのシーケンスのシャッフルを実行するコンピュータに実装される方法であって、
各々が複数の秘密鍵のうちの１つに対応する複数の公開鍵のうち、１つの公開鍵に対応する秘密鍵に関連付けられたコンピュータからの要求を提供するステップと、
前記複数の公開鍵のうちの少なくともいくつかをシャッフルした組を受信するステップと、
前記シャッフルのため、前記複数の公開鍵と、第１の暗号化されたデータのシーケンスの暗号化されない値を前記生成することは、第２の暗号化されたデータのシーケンスの暗号化されない値を前記生成することと等価であるとの証明に基づく正確さの証明との新たにシャッフルした組を生成するステップと
をさらに備えたことを特徴とする方法。
【請求項２０】
ファイルを提供するステップと、
第１の暗号化されたデータのシーケンスの暗号化されない値を前記生成することは、第２の暗号化されたデータのシーケンスの暗号化されない値を前記生成することと等価であるとの非反復証明に基づく前記公開鍵の新たにシャッフルした組について前記正確さの証明を生成するステップと
をさらに備えたことを特徴とする請求項１９に記載の方法。
【請求項１】
コンピュータネットワークに結合したサーバコンピュータを備えたシーケンスの受信を行うコンピュータシステムにおいて、前記サーバコンピュータは、
個々のデータファイルを示す電子データのシーケンスを受信し、
少なくとも１つの秘密鍵を用いて前記電子データのシーケンスを匿名で置換し、および前記サーバコンピュータが該電子データのシーケンスとの対応関係を知っているシャッフルされた電子データのシーケンスを生成するように暗号変換を行うよう構成されたコンピュータシステムであって、
前記サーバコンピュータは、
第１の暗号化されたデータのシーケンスの暗号化されない値を前記生成することは、第２の暗号化されたデータのシーケンスの暗号化されない値を前記生成することと等価であるとの証明に基づいて前記置換を行うために、正確さの証明を生成するようさらに構成されたことを特徴とするシステム。
【請求項２】
前記受信した電子データのシーケンスは、前記サーバコンピュータに知られていない鍵によって群Zpまたは楕円曲線を用いて暗号化され、および前記サーバコンピュータは、
一連のランダムに生成された値eiを受信し、および少なくともいくつかの前記ランダムに生成された値eiの少なくとも一部に基づく非反復証明として前記正確さの証明を生成するようさらに構成されたことを特徴とする請求項１に記載のシステム。
【請求項３】
各々が複数の公開鍵の１つに対応する秘密鍵を有する、対応する複数の個人からの前記複数の公開鍵を受信し、
１つの秘密鍵を有する前記複数の個人の１人から証明書の要求を受信し、
前記複数の公開鍵のうち少なくとも１つの部分集合を前記要求している個人に提供し、
第１の暗号化されたデータのシーケンスの暗号化されない値を前記生成することは、第２の暗号化されたデータのシーケンスの暗号化されない値を前記生成することと等価であるとの証明に基づいて前記置換を行うため、前記複数の公開鍵のシャッフル、および正確さの非反復証明を受信し、
前記正確さの証明をチェックし、
前記1人の個人に証明書を発行し、および
前記複数の公開鍵を前記１つの公開鍵だけ減らすよう構成されたことを特徴とする請求項１に記載のシステム。
【請求項４】
前記電子データのシーケンスは、公開鍵であり、並びに
前記サーバは、個人からの要求に対応して、前記公開鍵の１つに一意かつ数学的に関連付けられた秘密鍵を前記個人が有するかどうかをチェックし、および
前記有する場合は該個人に証明書を発行するようさらに構成されたことを特徴とする請求項１に記載のシステム。
【請求項５】
前記電子データのシーケンスは、電子選挙における投票の選択のシーケンスであることを特徴とする請求項１に記載のシステム。
【請求項６】
前記正確さの証明は、前記電子データのシーケンスおよび前記生成されシャッフルされた電子データのシーケンスが与えられれば、前記電子データのシーケンス中の解読されたものすべてについて、対応する置換され解読されたものが前記生成されシャッフルされた電子データのシーケンス中に存在するような置換が存在することを証明することを特徴とする請求項１に記載のシステム。
【請求項７】
前記置換のための前記正確さの証明は、
第１の暗号化された線形因子のシーケンスによって定められる第１の多項式は、第２の暗号化された線形因子のシーケンスによって定められる第２の多項式の一定の倍数に等しいとの証明に基づくことを特徴とする請求項１に記載のシステム。
【請求項８】
コンテンツとして、電子データのシーケンスと関連するデータとを格納するコンピュータ読取可能な媒体であって、前記電子データのシーケンスはコンピュータに実装される方法によって処理されてシャッフルされ、前記方法は、
電子データのシーケンスを受信するステップと、
少なくとも第１の秘密鍵を用いて前記電子データのシーケンスを匿名で置換し、および第１のシャッフルされた電子データのシーケンスを生成するように秘密のワンウェイ暗号変換を行うステップと
を備え、第１の暗号化されたデータのシーケンスの暗号化されない値を前記生成することは、第２の暗号化されたデータのシーケンスの暗号化されない値を前記生成することと等価であるとの証明に基づいて前記置換を行うために、正確さの証明を生成するステップをさらに備えたことを特徴とするコンピュータ読取可能な媒体。
【請求項９】
前記受け取った電子データのシーケンスは、モジュラス整数値p(Zp)を有する整数の環である基礎となる数学的群によって暗号化されることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１０】
前記電子データのシーケンスと前記正確さの証明を受け取るコンピュータネットワーク内の論理ノードであることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１１】
コンピュータ読取可能なディスクであることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１２】
前記電子データのシーケンスと前記正確さの証明を含む生成されたデータ信号を伝送するデータ伝送媒体であることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１３】
コンピュータシステムのメモリであることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１４】
投票オーソリティサーバコンピュータへのインターネット接続リンクであることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１５】
前記電子データは、少なくとも公開鍵または公開鍵に関連付けられたデジタル証明書を含むことを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１６】
前記電子データのシーケンスは、電子投票または電子投票の選択であることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１７】
前記受信した電子データのシーケンスは、基礎となる楕円曲線群で暗号化されることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１８】
前記正確さの証明は、正確さの非反復証明であることを特徴とする請求項８に記載のコンピュータ読取可能な媒体。
【請求項１９】
電子データのシーケンスのシャッフルを実行するコンピュータに実装される方法であって、
各々が複数の秘密鍵のうちの１つに対応する複数の公開鍵のうち、１つの公開鍵に対応する秘密鍵に関連付けられたコンピュータからの要求を提供するステップと、
前記複数の公開鍵のうちの少なくともいくつかをシャッフルした組を受信するステップと、
前記シャッフルのため、前記複数の公開鍵と、第１の暗号化されたデータのシーケンスの暗号化されない値を前記生成することは、第２の暗号化されたデータのシーケンスの暗号化されない値を前記生成することと等価であるとの証明に基づく正確さの証明との新たにシャッフルした組を生成するステップと
をさらに備えたことを特徴とする方法。
【請求項２０】
ファイルを提供するステップと、
第１の暗号化されたデータのシーケンスの暗号化されない値を前記生成することは、第２の暗号化されたデータのシーケンスの暗号化されない値を前記生成することと等価であるとの非反復証明に基づく前記公開鍵の新たにシャッフルした組について前記正確さの証明を生成するステップと
をさらに備えたことを特徴とする請求項１９に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００６−１１５５５０（Ｐ２００６−１１５５５０Ａ）
【公開日】平成１８年４月２７日（２００６．４．２７）
【国際特許分類】
【出願番号】特願２００６−１１４５６（Ｐ２００６−１１４５６）
【出願日】平成１８年１月１９日（２００６．１．１９）
【分割の表示】特願２００１−５７１３３７（Ｐ２００１−５７１３３７）の分割
【原出願日】平成１３年３月２４日（２００１．３．２４）
【出願人】（５０２０５７７６２）ヴォートヒア インコーポレイテッド (1)
【Ｆターム（参考）】
【公開日】平成１８年４月２７日（２００６．４．２７）
【国際特許分類】
【出願日】平成１８年１月１９日（２００６．１．１９）
【分割の表示】特願２００１−５７１３３７（Ｐ２００１−５７１３３７）の分割
【原出願日】平成１３年３月２４日（２００１．３．２４）
【出願人】（５０２０５７７６２）ヴォートヒア インコーポレイテッド (1)
【Ｆターム（参考）】
[ Back to top ]