JP2003529256A - 安全な複数オーソリティ選挙のためのエルガマル暗号化データのように暗号化されたデータの検証可能な秘密シャッフル - Google Patents
安全な複数オーソリティ選挙のためのエルガマル暗号化データのように暗号化されたデータの検証可能な秘密シャッフルInfo
- Publication number
- JP2003529256A JP2003529256A JP2001571337A JP2001571337A JP2003529256A JP 2003529256 A JP2003529256 A JP 2003529256A JP 2001571337 A JP2001571337 A JP 2001571337A JP 2001571337 A JP2001571337 A JP 2001571337A JP 2003529256 A JP2003529256 A JP 2003529256A
- Authority
- JP
- Japan
- Prior art keywords
- computer
- sequence
- proof
- elements
- shuffled
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 claims abstract description 62
- 230000008569 process Effects 0.000 claims abstract description 16
- 230000009466 transformation Effects 0.000 claims description 30
- 238000012795 verification Methods 0.000 claims description 17
- 230000004044 response Effects 0.000 claims description 14
- 230000002452 interceptive effect Effects 0.000 claims description 8
- 230000005540 biological transmission Effects 0.000 claims description 6
- 238000006243 chemical reaction Methods 0.000 claims description 3
- 238000000844 transformation Methods 0.000 claims description 2
- 238000010276 construction Methods 0.000 abstract description 6
- 230000006870 function Effects 0.000 description 13
- 238000010200 validation analysis Methods 0.000 description 12
- 239000013256 coordination polymer Substances 0.000 description 9
- 238000010586 diagram Methods 0.000 description 7
- 238000012545 processing Methods 0.000 description 7
- 238000007689 inspection Methods 0.000 description 6
- 238000013459 approach Methods 0.000 description 4
- 238000004891 communication Methods 0.000 description 4
- 230000008901 benefit Effects 0.000 description 3
- 230000000694 effects Effects 0.000 description 3
- 238000007726 management method Methods 0.000 description 3
- 230000009471 action Effects 0.000 description 2
- 239000003795 chemical substances by application Substances 0.000 description 2
- 238000013461 design Methods 0.000 description 2
- 230000007717 exclusion Effects 0.000 description 2
- 230000007246 mechanism Effects 0.000 description 2
- 230000003287 optical effect Effects 0.000 description 2
- 230000008520 organization Effects 0.000 description 2
- 230000002441 reversible effect Effects 0.000 description 2
- 239000004065 semiconductor Substances 0.000 description 2
- 238000006467 substitution reaction Methods 0.000 description 2
- OVSKIKFHRZPJSS-UHFFFAOYSA-N 2,4-D Chemical compound OC(=O)COC1=CC=C(Cl)C=C1Cl OVSKIKFHRZPJSS-UHFFFAOYSA-N 0.000 description 1
- DIWRORZWFLOCLC-UHFFFAOYSA-N Lorazepam Chemical compound C12=CC(Cl)=CC=C2NC(=O)C(O)N=C1C1=CC=CC=C1Cl DIWRORZWFLOCLC-UHFFFAOYSA-N 0.000 description 1
- 230000015572 biosynthetic process Effects 0.000 description 1
- 238000004364 calculation method Methods 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 230000001010 compromised effect Effects 0.000 description 1
- 238000012790 confirmation Methods 0.000 description 1
- 239000000470 constituent Substances 0.000 description 1
- 235000014510 cooky Nutrition 0.000 description 1
- 238000012937 correction Methods 0.000 description 1
- 238000013480 data collection Methods 0.000 description 1
- 238000013500 data storage Methods 0.000 description 1
- 238000001514 detection method Methods 0.000 description 1
- 230000008676 import Effects 0.000 description 1
- 230000000670 limiting effect Effects 0.000 description 1
- 238000013507 mapping Methods 0.000 description 1
- 239000000463 material Substances 0.000 description 1
- 230000005055 memory storage Effects 0.000 description 1
- 230000036961 partial effect Effects 0.000 description 1
- 238000012805 post-processing Methods 0.000 description 1
- 238000000926 separation method Methods 0.000 description 1
- 229910001220 stainless steel Inorganic materials 0.000 description 1
- 239000010935 stainless steel Substances 0.000 description 1
- 238000005728 strengthening Methods 0.000 description 1
- 238000012546 transfer Methods 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
- H04L9/321—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving a third party or a trusted authority
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/006—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols involving public key infrastructure [PKI] trust models
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/14—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols using a plurality of keys or algorithms
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
- H04L9/3013—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L9/3066—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
- H04L9/3073—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
- H04L9/3218—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
- H04L2209/42—Anonymization, e.g. involving pseudonyms
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
- H04L2209/46—Secure multiparty computation, e.g. millionaire problem
- H04L2209/463—Electronic voting
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
- H04L2209/60—Digital content management, e.g. content distribution
Landscapes
- Engineering & Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- General Physics & Mathematics (AREA)
- Algebra (AREA)
- Physics & Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Mathematical Physics (AREA)
- Pure & Applied Mathematics (AREA)
- Storage Device Security (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
- Electroluminescent Light Sources (AREA)
- Time Recorders, Dirve Recorders, Access Control (AREA)
- Signal Processing For Digital Recording And Reproducing (AREA)
Abstract
(57)【要約】
暗号化プロセスは、一連の入力データ要素を検証可能にシャッフルすることを可能にする。1つまたは2つ以上のオーソリティまたは個人は、入力データ(例えば、離散対数形式またはエルガマル暗号化投票データにおける公開鍵)を「シャッフル」または「匿名化」する。このプロセスは、結果的に生じる証明の写しを検査する誰からも見つからずに1つまたは2つ以上のオーソリティまたは個人が元のデータに変更を加えることを防止する有効な構築を含む。シャッフリングは、種々の時点で実行することができる。選挙の実施例では、シャッフリングは、例えば票の収集後、または登録中、または選挙の票要求フェーズで実行することができ、それによって投票者の識別を匿名化する。
Description
【０００１】
(関連出願の相互参照)
本願は、すべて同じ発明者によるものであり、現在、係属中の、いずれも「Ve
rifiable, Secret Shuffles of El-Gamal Encrypted Data」という名称の、2000
年3月24日出願の米国仮出願第60/191,785号および2000年11月21日出願の米国仮
出願第60/252,376号並びに2001年2月14日出願の「Verifiable, Secret Shuffles
of El-Gamal Encrypted Data for Secure Multi-Authority Elections」という
名称の米国仮出願第60/268,551号の出願の利益を主張する。
rifiable, Secret Shuffles of El-Gamal Encrypted Data」という名称の、2000
年3月24日出願の米国仮出願第60/191,785号および2000年11月21日出願の米国仮
出願第60/252,376号並びに2001年2月14日出願の「Verifiable, Secret Shuffles
of El-Gamal Encrypted Data for Secure Multi-Authority Elections」という
名称の米国仮出願第60/268,551号の出願の利益を主張する。
【０００２】
(技術分野)
以下の技術は、一般に暗号化に関し、より詳細には、投票方式で使用するため
の電子暗号化に関する。
の電子暗号化に関する。
【０００３】
(背景および概要)
オブジェクト、記録またはトークンの集合のシャッフルの概念は、簡素かつ直
観的であり、有用な使用例が、人々の日常の種々の活動にあふれている。カジノ
のギャンブラーは、自分の持ち札を取り出すときは、その1枚1枚が52の一意の値
のうちの1つであること、およびその持ち札と同じ持ち札を有する者はそのテー
ブルにはいないということを知っている。しかし、たとえディーラーがそれらの
カードをシャッフルする前にそのギャンブラーがカードの正確な順序を記録して
おくことができたとしても、そのギャンブラーは、それらのカードがどのように
配られたかはまったく知ることはない。
観的であり、有用な使用例が、人々の日常の種々の活動にあふれている。カジノ
のギャンブラーは、自分の持ち札を取り出すときは、その1枚1枚が52の一意の値
のうちの1つであること、およびその持ち札と同じ持ち札を有する者はそのテー
ブルにはいないということを知っている。しかし、たとえディーラーがそれらの
カードをシャッフルする前にそのギャンブラーがカードの正確な順序を記録して
おくことができたとしても、そのギャンブラーは、それらのカードがどのように
配られたかはまったく知ることはない。
【０００４】
電子データのコンテクストにおいては、入力されたシーケンスを同種のランダ
ムだが検証が可能なように置換するという問題は驚くほど困難である。この問題
は、データ自体、監査役(auditor)に常に明白であるか、そうでないかのどちら
かしかないということである。明白である場合、入力された記録と出力された記
録との間の対応は自明(trivial)で、監査役または他のオブザーバーが再構成す
ることができる。明白でない場合、入力された記録と出力された記録は、同一の
基礎となるデータの異なる表現でなければならない。しかし、出力が十分に異な
っていて(すなわち、十分に暗号化されていて)監査役が対応関係を再構成するこ
とができない場合、監査役は、シャッフリングの過程でシャッフラが基礎となる
データを変更しなかったことをいかに確信するであろうか。
ムだが検証が可能なように置換するという問題は驚くほど困難である。この問題
は、データ自体、監査役(auditor)に常に明白であるか、そうでないかのどちら
かしかないということである。明白である場合、入力された記録と出力された記
録との間の対応は自明(trivial)で、監査役または他のオブザーバーが再構成す
ることができる。明白でない場合、入力された記録と出力された記録は、同一の
基礎となるデータの異なる表現でなければならない。しかし、出力が十分に異な
っていて(すなわち、十分に暗号化されていて)監査役が対応関係を再構成するこ
とができない場合、監査役は、シャッフリングの過程でシャッフラが基礎となる
データを変更しなかったことをいかに確信するであろうか。
【０００５】
以下の説明の大半は、エルガマル（ElGamal）暗号化データという、重要なコ
ンテクストにおいてこの問題を解決するための有効な(線形の)方法を提供するた
めに費やされている。できる限り明瞭かつ簡潔な解説とするため、以下の説明の
大部分は、大きな素数pを法とする乗法単位群である
ンテクストにおいてこの問題を解決するための有効な(線形の)方法を提供するた
めに費やされている。できる限り明瞭かつ簡潔な解説とするため、以下の説明の
大部分は、大きな素数pを法とする乗法単位群である
【０００６】
【数１１】
【０００７】
で演算が実行される具体的なケースをそのまま参照する。しかし、使用され基礎
となる(乗法の)群の特性は、関連するエルガマル暗号システムが安全でなければ
ならないということ、および、関係式loggX = loghY = uに対するChaum-Pederse
n（チョム−ペダーセン）プロトコル(D.Chaum著、「Zero-knowledge undeniable
signatures. Advances in Cryptology EUROCRYPT'90, volume 473, Lecture N
otes in Computer Science」473巻、458-464頁、1991年Springer-Verlag。D.Cha
umおよび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 yoursel
f: Practical solutions to identification and signature problems. Advance
s 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 efficie
nt multi-authority election scheme. Advances in Cryptology EUROCRYPT '
97, Lecture Notes in Computer Science」Springer-Verlag, 1997年。)。した
がって、シャッフルプロトコルは、楕円曲線などの他の群までエルガマル暗号化
を実施するときにも有用である。R.Cramer, I.Damgrd, B.Schoenmakers著、「Pr
oofs of partial knowledge and simplified design of witness hiding protoc
ols」(Advances in Cryptology CRYPTO'94, Lecture Notes in Computer Scien
ce, 174-187頁、Springer-Verlag、ベルリン、1994年)の、一般的なブールの証
明（boolean proof）手法も、同じ特性を有する証明を構築するために使用する
ことができるが、結果的に証明のサイズ(複雑さ)は入力シーケンスのサイズでは
2次元またはそれよりも劣ることとなる。
となる(乗法の)群の特性は、関連するエルガマル暗号システムが安全でなければ
ならないということ、および、関係式loggX = loghY = uに対するChaum-Pederse
n（チョム−ペダーセン）プロトコル(D.Chaum著、「Zero-knowledge undeniable
signatures. Advances in Cryptology EUROCRYPT'90, volume 473, Lecture N
otes in Computer Science」473巻、458-464頁、1991年Springer-Verlag。D.Cha
umおよび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 yoursel
f: Practical solutions to identification and signature problems. Advance
s 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 efficie
nt multi-authority election scheme. Advances in Cryptology EUROCRYPT '
97, Lecture Notes in Computer Science」Springer-Verlag, 1997年。)。した
がって、シャッフルプロトコルは、楕円曲線などの他の群までエルガマル暗号化
を実施するときにも有用である。R.Cramer, I.Damgrd, B.Schoenmakers著、「Pr
oofs of partial knowledge and simplified design of witness hiding protoc
ols」(Advances in Cryptology CRYPTO'94, Lecture Notes in Computer Scien
ce, 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をそれらの要素が暗号化され
る
-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のプロトコルが非対話式に実施される場合、不正行為を行
う確率は極めて小さく選択されなければならない。何故ならば、悪意のある参加
者が、徹底したサーチにより偽造証明を生成するため、多量のオフライン計算を
使用する可能性があるからである。これは、当然ながら、上記プロトコルではこ
の通りであり得るが、確率k/qは、kとqのすべての現実的な値に関して十分小さ
いことは確実である。)
【００１１】
結果的に普遍的に検証可能となる選挙プロトコルのコンテクストにおいて見る
とき、現行方式の利点はさらに明確になる。K.Sakoにおいて、各投票者は、実際
に票を投じる前に各「集計センター」と連続して対話する必要がある。このよう
な理由から、近い将来、大規模な公共セクタの選挙のために有効な実施がなされ
る可能性は低いと考えられる。反対に、後述するプロトコルでは、純粋に作表の
目的で選挙終了時にすべてのオーソリティを参加させる(場合によっては、基本
的な選挙パラメータの作成は除く)。
とき、現行方式の利点はさらに明確になる。K.Sakoにおいて、各投票者は、実際
に票を投じる前に各「集計センター」と連続して対話する必要がある。このよう
な理由から、近い将来、大規模な公共セクタの選挙のために有効な実施がなされ
る可能性は低いと考えられる。反対に、後述するプロトコルでは、純粋に作表の
目的で選挙終了時にすべてのオーソリティを参加させる(場合によっては、基本
的な選挙パラメータの作成は除く)。
【００１２】
この素晴らしい特性は、R.Cramer, R.GennaroおよびB. Schoenmakersの論文に
記載の洗練された準同形選挙プロトコルにも見られる。しかし、このプロトコル
は、「nの中のm(以下)を選択せよ」という簡素なタイプの質問を有する投票に適
用できるだけである。これは効果的に、投票者が優先順位で回答を示すことが要
求され、質問項目はその優先順位に従って作表されることとなる、「記入式」応
答、並びに「比例タイプの」質問を除外する。R.Cramer, R.GennaroおよびB.Sch
oenmakersスキームの欠点は、これに比べて若干重要度は低いが、投票データサ
イズを大幅に拡張すること、および、投票者に「妥当性証明」を要求することで
ある。この証明によると、投票データのサイズは約1桁だけ拡張され、実用的な
観点からは魅力的ではない。なぜなら、投票者のコンピュータで専用コードが実
行していることが前提とされるからである。
記載の洗練された準同形選挙プロトコルにも見られる。しかし、このプロトコル
は、「nの中のm(以下)を選択せよ」という簡素なタイプの質問を有する投票に適
用できるだけである。これは効果的に、投票者が優先順位で回答を示すことが要
求され、質問項目はその優先順位に従って作表されることとなる、「記入式」応
答、並びに「比例タイプの」質問を除外する。R.Cramer, R.GennaroおよびB.Sch
oenmakersスキームの欠点は、これに比べて若干重要度は低いが、投票データサ
イズを大幅に拡張すること、および、投票者に「妥当性証明」を要求することで
ある。この証明によると、投票データのサイズは約1桁だけ拡張され、実用的な
観点からは魅力的ではない。なぜなら、投票者のコンピュータで専用コードが実
行していることが前提とされるからである。
【００１３】
このプロトコルは後述するが、Chaum-Pedersen(チョム-ペダーセン)証明のシ
ーケンスと基本的な算術演算だけで構成されている。したがって、これは、容易
に実施される。
ーケンスと基本的な算術演算だけで構成されている。したがって、これは、容易
に実施される。
【００１４】
図面では、同一またはほぼ同一の要素または動作は同一の参照番号で示す。い
かなる特定の要素または動作の説明をも容易に識別するために、参照番号の1つ
または2つ以上の最上位桁は、その要素が最初に紹介された図番を示している(例
えば、要素204は最初に図2で紹介され、図2に関して説明されている。)。
かなる特定の要素または動作の説明をも容易に識別するために、参照番号の1つ
または2つ以上の最上位桁は、その要素が最初に紹介された図番を示している(例
えば、要素204は最初に図2で紹介され、図2に関して説明されている。)。
【００１５】
本発明に設けられている表題は便宜上のみのためのものであり、請求の範囲に
記載の発明の範囲または意味には必ずしも影響を与えるものではない。
記載の発明の範囲または意味には必ずしも影響を与えるものではない。
【００１６】
(詳細な説明)
1.概要
以下で詳述するのは、一連の要素、例えば離散対数形式またはk入力エルガマ
ル暗号化による公開鍵の入力シーケンスを「検証可能にシャッフルする」ための
暗号化プロトコルであり、これらはセキュリティ保護された普遍的に検証可能な
複数オーソリティ選挙スキームに応用例を持つ。k入力エルガマル暗号化の場合
、シャッフル演算の出力はkエルガマル暗号の別のシーケンスであり、その各々
は入力された暗号の中の正確に1つを再暗号化する(すなわち、同一のクリアなテ
キストを正確に暗号化するエルガマル対)が、出力の中の要素の順序は秘密に保
持される。(適用されるべき要素の並べ替えおよび使用される暗号化鍵を選択す
る)「シャッフラ」にとって、入力から出力を計算することは些細なことではあ
るが、その構築は重要である。なぜなら、任意のベリファイアによってチェック
される可能性のある出力シーケンスのための正確さについてのリニアなサイズの
証明(すなわち、請求された形式の証明)が提供されるからである。証明プロトコ
ルのセキュリティは、関係式loggx = loghyに対するChaum-Pedersenプロトコル
のそれと同じであり、使用される選挙の応用例に関し、これで十分である。
ル暗号化による公開鍵の入力シーケンスを「検証可能にシャッフルする」ための
暗号化プロトコルであり、これらはセキュリティ保護された普遍的に検証可能な
複数オーソリティ選挙スキームに応用例を持つ。k入力エルガマル暗号化の場合
、シャッフル演算の出力はkエルガマル暗号の別のシーケンスであり、その各々
は入力された暗号の中の正確に1つを再暗号化する(すなわち、同一のクリアなテ
キストを正確に暗号化するエルガマル対)が、出力の中の要素の順序は秘密に保
持される。(適用されるべき要素の並べ替えおよび使用される暗号化鍵を選択す
る)「シャッフラ」にとって、入力から出力を計算することは些細なことではあ
るが、その構築は重要である。なぜなら、任意のベリファイアによってチェック
される可能性のある出力シーケンスのための正確さについてのリニアなサイズの
証明(すなわち、請求された形式の証明)が提供されるからである。証明プロトコ
ルのセキュリティは、関係式loggx = loghyに対するChaum-Pedersenプロトコル
のそれと同じであり、使用される選挙の応用例に関し、これで十分である。
【００１７】
以下の説明では、本発明の実施形態を完全に理解するための具体的な詳細、お
よび実施可能な説明が提供される。しかし、当業者ならば、本発明はこれらの詳
細なくしても実施可能であることが理解されるであろう。他の例においては、本
発明の実施形態の説明を不必要に不明瞭化することを避けるため、周知の構造お
よび関数は詳細に図示または説明しない。
よび実施可能な説明が提供される。しかし、当業者ならば、本発明はこれらの詳
細なくしても実施可能であることが理解されるであろう。他の例においては、本
発明の実施形態の説明を不必要に不明瞭化することを避けるため、周知の構造お
よび関数は詳細に図示または説明しない。
【００１８】
以下に提供される詳細な説明の大半は、上記の仮出願で明示的に開示されてい
る；追加資料の多くは、そのような仮出願に提供された詳細な説明に固有のもの
として関連技術の精通者に理解されるものであり、あるいは周知のものである。
関連技術の精通者は、仮出願に提供された詳細な説明に基づいて本発明の態様を
実施することができる。
る；追加資料の多くは、そのような仮出願に提供された詳細な説明に固有のもの
として関連技術の精通者に理解されるものであり、あるいは周知のものである。
関連技術の精通者は、仮出願に提供された詳細な説明に基づいて本発明の態様を
実施することができる。
【００１９】
本発明で使用される数学的表記法の多くは、関連技術の精通者には容易に理解
することができるが、当技術分野に精通していない技術者のために以下のように
定義して説明する。これらの定義は簡略ではあるが、当技術分野に全般的に精通
していない技術者が、本明細書に記載の詳細な説明に基づいて本発明の実施態様
をさらに完全に理解するのに役立つであろう。これらの定義は、全体として(特
許請求の範囲を含めて)本発明の説明によってさらに定義されるものであり、こ
れらの定義にだけよるものではない。
することができるが、当技術分野に精通していない技術者のために以下のように
定義して説明する。これらの定義は簡略ではあるが、当技術分野に全般的に精通
していない技術者が、本明細書に記載の詳細な説明に基づいて本発明の実施態様
をさらに完全に理解するのに役立つであろう。これらの定義は、全体として(特
許請求の範囲を含めて)本発明の説明によってさらに定義されるものであり、こ
れらの定義にだけよるものではない。
【００２０】
図1-5は、本明細書に記載の詳細な説明に加えて、当事者(例えば、投票者)と
ベリファイアの間(または、証明側当事者と検証側当事者の間)のプロトコルを説
明する。これらの当事者によって実行される動作は、流れ図のボックスに共に分
類される。一般に、ボックス内の各行のテキストまたは方程式は、計算、情報の
伝送、あるいは記憶または検索関数などのステップを説明している。このような
流れ図は1行ごとに、また、ボックスごとに読まれる。
ベリファイアの間(または、証明側当事者と検証側当事者の間)のプロトコルを説
明する。これらの当事者によって実行される動作は、流れ図のボックスに共に分
類される。一般に、ボックス内の各行のテキストまたは方程式は、計算、情報の
伝送、あるいは記憶または検索関数などのステップを説明している。このような
流れ図は1行ごとに、また、ボックスごとに読まれる。
【００２１】
本発明で一般に使用される「当事者」という用語は、エンティティを示してい
るが、このプロトコルの下で、ステップまたはステップの集合を実行するエージ
ェントとすることができる。この用語はまた、これらステップの一部またはすべ
てを実行する手段または方法のことを言う場合もある。したがって、デジタル論
理回路中の適当ないかなる構成の下でも、プロトコルの一部またはすべての部分
を実行することができる。例えば、プロトコルの下の任意のステップまたはすべ
てのステップは、パーソナルコンピュータなどの汎用コンピュータだけでなく、
組み込み型または専用の組み合わせ論理装置、またはいかなる種類の適切にプロ
グラムされたマシン乃至マイクロプロセッサによっても、以上の装置またはマシ
ンが必要な処理ステップ、ストレージ、入力および出力などを実行する場合に限
り、実現することができる。
るが、このプロトコルの下で、ステップまたはステップの集合を実行するエージ
ェントとすることができる。この用語はまた、これらステップの一部またはすべ
てを実行する手段または方法のことを言う場合もある。したがって、デジタル論
理回路中の適当ないかなる構成の下でも、プロトコルの一部またはすべての部分
を実行することができる。例えば、プロトコルの下の任意のステップまたはすべ
てのステップは、パーソナルコンピュータなどの汎用コンピュータだけでなく、
組み込み型または専用の組み合わせ論理装置、またはいかなる種類の適切にプロ
グラムされたマシン乃至マイクロプロセッサによっても、以上の装置またはマシ
ンが必要な処理ステップ、ストレージ、入力および出力などを実行する場合に限
り、実現することができる。
【００２２】
記号「∈R」は、一般に、略均一で独立した(ランダムな)確率分布に従って、
右側の集合から左側の1つまたは複数の数字が選択されることを示している。実
際、場合によっては付加的な事後処理または決定論的擬似乱数ジェネレータと共
に、物理的な乱数ジェネレータを使用することができる。乱数を生成する方法は
、関連技術の精通者には周知である。
右側の集合から左側の1つまたは複数の数字が選択されることを示している。実
際、場合によっては付加的な事後処理または決定論的擬似乱数ジェネレータと共
に、物理的な乱数ジェネレータを使用することができる。乱数を生成する方法は
、関連技術の精通者には周知である。
【００２３】
記号「Π」および「Σ」は、それぞれインデックス付きの積と和を示す。
【００２４】
記号「Zp」は整数0からp-1の数の集合、またはpを法とする整数の環を示す。
環Zpでの要素の加法および乗法はpを法として定義される。
環Zpでの要素の加法および乗法はpを法として定義される。
【００２５】
記号「∈」は、左側の要素が右側の集合の構成要素または要素であることを示
している。
している。
【００２６】
記号「⊂」は、左側の集合が右側の集合の部分集合であること、すなわち左側
の集合が右側の集合に含まれることを示している。
の集合が右側の集合に含まれることを示している。
【００２７】
角括弧記号(すなわち、「<>」)は、それらに挟まれた1つまたは複数の項が所
与の群または整数の環(例えば、環Zp)の部分集合によって生成された部分群であ
ることを示している。部分群は、これもまた同じバイナリオペレーション下の群
である別の群(または環)の部分集合である(例えば、整数は加法下の実数の部分
群であるが、nを法とする整数は、演算が別に定義されるので、それらの部分群
ではない。
与の群または整数の環(例えば、環Zp)の部分集合によって生成された部分群であ
ることを示している。部分群は、これもまた同じバイナリオペレーション下の群
である別の群(または環)の部分集合である(例えば、整数は加法下の実数の部分
群であるが、nを法とする整数は、演算が別に定義されるので、それらの部分群
ではない。
【００２８】
以下では、別途明示しない限り、公知のように、nは正の整数であり、pとqは
素数の整数である。算術演算は、モジュラ環Zp(またはZnである場合がある)で実
行され、g∈Zpは(素数の)乗法の階数qを有することになる。(したがって、単にq
|(p-1)である)。各証明プロトコルでは、Pは証明者(シャッフラ)でありVはベリ
ファイア(監査役)である。
素数の整数である。算術演算は、モジュラ環Zp(またはZnである場合がある)で実
行され、g∈Zpは(素数の)乗法の階数qを有することになる。(したがって、単にq
|(p-1)である)。各証明プロトコルでは、Pは証明者(シャッフラ)でありVはベリ
ファイア(監査役)である。
【００２９】
後述する一実施形態は、Zp(エルガマル)暗号システムを使用するが、楕円曲線
暗号システムと、一般群下の暗号システムを使用することもできる。このような
暗号システムは、非対称暗号システムに対する公開鍵を使用する。公開鍵システ
ムは、所謂一方向性関数と落し戸関数を使用する。「一方向性関数」とは出力を
計算するのは比較的容易だが、その逆関数は計算することが遥かに困難な関数の
ことである。例えば、ベキ関数は等しい因数の数の積を計算することは容易であ
るが、数量の根を探す逆演算はより複雑である。「トラップドア」関数は一方向
性関数と類似しているが、何らかの追加情報が入手できない限り、逆関数は極め
て困難である。この追加情報は、通常、投票者などの当事者によって保持される
「公開鍵」である。
暗号システムと、一般群下の暗号システムを使用することもできる。このような
暗号システムは、非対称暗号システムに対する公開鍵を使用する。公開鍵システ
ムは、所謂一方向性関数と落し戸関数を使用する。「一方向性関数」とは出力を
計算するのは比較的容易だが、その逆関数は計算することが遥かに困難な関数の
ことである。例えば、ベキ関数は等しい因数の数の積を計算することは容易であ
るが、数量の根を探す逆演算はより複雑である。「トラップドア」関数は一方向
性関数と類似しているが、何らかの追加情報が入手できない限り、逆関数は極め
て困難である。この追加情報は、通常、投票者などの当事者によって保持される
「公開鍵」である。
【００３０】
下記の方法およびプロトコルは、離散対数に対するChaum-Pedersenの等式(equ
ality)の証明を頻繁に使用する。g、X、h、Y ∈ Zpの場合、これは関係式
ality)の証明を頻繁に使用する。g、X、h、Y ∈ Zpの場合、これは関係式
【００３１】
logg X = logh Y (1)
【００３２】
に関する知識の証明である。
【００３３】
ゼロ知識であることは知られていない。しかし、公正なベリファイアに対して
はゼロ知識であることが知られているが、これは、Fiat-Shamirヒューリスティ
ックによってベリファイアを実施する、主要な応用例にとっては十分である。
はゼロ知識であることが知られているが、これは、Fiat-Shamirヒューリスティ
ックによってベリファイアを実施する、主要な応用例にとっては十分である。
【００３４】
「ゼロ知識証明」では、投票者または証明側当事者は、秘密のノリッジを証明
することができるが、使用している情報が何であれ、ノリッジのその証明の伝達
する際に検証側当事者にそれを露出することはない。単一ビットの情報、すなわ
ち、証明側当事者が実際にその秘密を知っているということだけが伝達される。
換言すると、投票者と検証するオーソリティはメッセージを交換するが、投票者
の目的は、票の各質問に投票者がどのように投票したか、または一連の要素がど
のようにシャッフルされたかを露出することなく、主張が真実であることをベリ
ファイアに確信させることであり、その主張とは、例えば暗号化された投票また
は、投票または要素のシャッフルされたシーケンスは完全であり正確であるとい
うような主張である。このようなゼロ知識証明の下では、各投票者または証明側
当事者は、効果的に、自分の秘密鍵を有する人物だけが生成することのできる特
定の数を生成する。ベリファイアまたは認証する当事者は、次いで、それぞれの
計算された数が本当に周知のアルゴリズムで生成され、それによって投票者を認
証すること、および、投票者の電子投票が完全かつ正確であるかまたは許容され
る選択と制約に関し「良好に形成されている」ことを確認し、あるいは一連の要
素が(シャッフルされ暗号化された以外に)変更されていないことを確認する。
することができるが、使用している情報が何であれ、ノリッジのその証明の伝達
する際に検証側当事者にそれを露出することはない。単一ビットの情報、すなわ
ち、証明側当事者が実際にその秘密を知っているということだけが伝達される。
換言すると、投票者と検証するオーソリティはメッセージを交換するが、投票者
の目的は、票の各質問に投票者がどのように投票したか、または一連の要素がど
のようにシャッフルされたかを露出することなく、主張が真実であることをベリ
ファイアに確信させることであり、その主張とは、例えば暗号化された投票また
は、投票または要素のシャッフルされたシーケンスは完全であり正確であるとい
うような主張である。このようなゼロ知識証明の下では、各投票者または証明側
当事者は、効果的に、自分の秘密鍵を有する人物だけが生成することのできる特
定の数を生成する。ベリファイアまたは認証する当事者は、次いで、それぞれの
計算された数が本当に周知のアルゴリズムで生成され、それによって投票者を認
証すること、および、投票者の電子投票が完全かつ正確であるかまたは許容され
る選択と制約に関し「良好に形成されている」ことを確認し、あるいは一連の要
素が(シャッフルされ暗号化された以外に)変更されていないことを確認する。
【００３５】
定義1
上記のChaum-Pedersen証明の一例は、
【００３６】
CP(g,X,h,Y)
【００３７】
によって示される。
【００３８】
定義2
固定された
【００３９】
【数１３】
【００４０】
が<g>x<g>上のバイナリオペレータの場合、すべてのx、y ∈ <g>に対する
【００４１】
【数１４】
【００４２】
によって定義された環の部分集合によって生成された部分群を示す。あるいはこ
れに替えて、すべてのa、b ∈ Zqに関する
れに替えて、すべてのa、b ∈ Zqに関する
【００４３】
【数１５】
【００４４】
である。加法および乗法に使用されるインデックスを付ける規則に従って、
【００４５】
【数１６】
【００４６】
の表記法も使用する。
【００４７】
このオペレーションを、本発明では対数乗法基数gと称する。
【００４８】
以上の定義における各々の表記法では、下付き添え字gの値が前後関係から明
らかな場合は、これを省略することができる。本発明で一般に使用するように、
「バイナリオペレータ」とは入力として集合から2つの要素をとり、1つの要素を
戻すような集合で定義されるオペレータを意味する。
らかな場合は、これを省略することができる。本発明で一般に使用するように、
「バイナリオペレータ」とは入力として集合から2つの要素をとり、1つの要素を
戻すような集合で定義されるオペレータを意味する。
【００４９】
注意1
Chaum-Pedersen証明では、h = gSであり、かつその常用対数がu = loggX = lo
ghYである場合、CP(g、X、h、Y)は明らかに関係式
ghYである場合、CP(g、X、h、Y)は明らかに関係式
【００５０】
【数１７】
【００５１】
を証明してもいることに注意されたい。
【００５２】
注意2
上記の証明は、明らかにsに関してゼロ知識である。これは証明者が、証明を
構成するためにこの値を知る必要は全くないからである。
構成するためにこの値を知る必要は全くないからである。
【００５３】
詳細な説明の以下の部分で非常に多く使用されるので、以下のよく知られた結
果のコレクション(collection)に注目されたい。
果のコレクション(collection)に注目されたい。
【００５４】
補助定理1
f(x)∈Zq[x]を次数dの多項式とする。この場合、d以下の値z1,…zd∈Zqがあり
、したがって、f(zi) = 0である。
、したがって、f(zi) = 0である。
【００５５】
系1
f(x), g(x)∈Zq[x]を、f≠gとして、次数d以上の2つの多項式とする。この場
合、d以上の値z1,…zd∈Zqが存在し、したがって、f(zi) = g(zi)である。
合、d以上の値z1,…zd∈Zqが存在し、したがって、f(zi) = g(zi)である。
【００５６】
系2
f(x), g(x)∈Zq[x]を、f≠gとして、次数d以上の2つの多項式とする。c∈RZq
、(cはZqからアトランダムに選択された)とすると、以下の確率が得られる。
、(cはZqからアトランダムに選択された)とすると、以下の確率が得られる。
【００５７】
【数１８】
【００５８】
補助定理2
【００５９】
【数１９】
【００６０】
をZqに亘る標準的なk次元のベクトル空間とし、
【００６１】
【数２０】
【００６２】
をv≠0に固定する。
【００６３】
【数２１】
【００６４】
がアトランダムに選択されると、
【００６５】
【数２２】
【００６６】
となる。
【００６７】
2.反復対数乗法の証明
この節の以下の部分で、すべての対数乗法は、固定された要素gに関して計算
されるので、表記法の下付き添え字は省略される。以下の問題は、後に出て来る
シャッフル証明の基礎となるものである。
されるので、表記法の下付き添え字は省略される。以下の問題は、後に出て来る
シャッフル証明の基礎となるものである。
【００６８】
反復対数乗法問題:2つのシーケンス
【００６９】
【数２３】
【００７０】
と、
【００７１】
【数２４】
【００７２】
は公然と知られている。証明者Pはすべてのiに関するui=loggXiおよびvi=loggYi
も知っているが、これらはベリファイアVには知られていない。Pは、秘密対数ui
とviに関する情報を露出せずに、関係式
【００７３】
【数２５】
【００７４】
をVに確信させることが要求される。
【００７５】
直観的に、注意1を考慮するとこの問題は簡潔である。証明者はk Chaum-Peder
sen証明の2つのシーケンスを構築して、Vに、
sen証明の2つのシーケンスを構築して、Vに、
【００７６】
【数２６】
【００７７】
の値と、
【００７８】
【数２７】
【００７９】
の値の両方を確信させることができ、次いでVはそれらの2つの値が同一であると
チェックすることができる。すべてのXiとYiがランダムかつ独立であることが知
られている場合、このことはuiとviとを秘密に保持する目的で受け入れることが
でき、本発明の一実施形態で実施することができる。しかし、このプロトコルは
、中間対数乗法に加え、V自身では計算することができない一部の情報、すなわ
ち
チェックすることができる。すべてのXiとYiがランダムかつ独立であることが知
られている場合、このことはuiとviとを秘密に保持する目的で受け入れることが
でき、本発明の一実施形態で実施することができる。しかし、このプロトコルは
、中間対数乗法に加え、V自身では計算することができない一部の情報、すなわ
ち
【００８０】
【数２８】
【００８１】
の値を露出することは明らかである。このプロトコルを強化するために、上述の
実施形態と以下で詳述される方法はある程度のランダム性を導入し、基礎となる
Chaum-Pedersenプロトコルよりも多く情報を漏洩しないことを保障する。 反復対数乗法証明: 1.Pは秘密裏に、k+1個の値
実施形態と以下で詳述される方法はある程度のランダム性を導入し、基礎となる
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に関して一部の情報が知ら
れる場合だけ、得ることができる。不正なベリファイアによってこのようなこと
が起こる可能性があるかどうかは知られていないが、ベリファイアが公正な場合
は起こらない。これは、後述する実施形態と応用例でも同様である。
て各々から露出される情報以上に秘密に関する情報を露出する可能性はない。こ
れを理解するキーは注意2である。第1の証明はri/ri-1に関してゼロ知識である
が、ui/ri-1に関しては、公正なベリファイアだけがゼロ知識である。しかし、
第2の証明はri,ri-1とuiに関しゼロ知識である。これは、証明者さえも、証明を
生成するためにそれらの値を知る必要がないからである。しかし、もちろん、露
出されたziからこれらの値に関する情報の一部を、viに関して一部の情報が知ら
れる場合だけ、得ることができる。不正なベリファイアによってこのようなこと
が起こる可能性があるかどうかは知られていないが、ベリファイアが公正な場合
は起こらない。これは、後述する実施形態と応用例でも同様である。
【００９２】
明らかに商ri/ri-1はすべて均一に分配されて独立しているので、値zi自体は
、uiとviに関していかなる情報もそれら自体によっては露出しない。 4.Vは
、uiとviに関していかなる情報もそれら自体によっては露出しない。 4.Vは
【００９３】
【数３３】
【００９４】
であることをチェックし、各Chaum-Pedersen証明をチェックする。
5.Vは最終的に
【００９５】
【数３４】
【００９６】
を評価し、
【００９７】
【数３５】
【００９８】
であることをチェックする。
【００９９】
注意1を参照し、単純にその指数を乗算することによって、このプロトコルが
反復対数乗法問題を解決することは、容易に確認することができる。偽造証明の
確率は、1つまたは2つ以上のChaum-Pedersen証明が偽造された確率だけ上に有界
である。これらの確率のそれぞれは1/qである。したがって、偽造される証明の
全体的な確率は2k/qだけ上に有界である。
反復対数乗法問題を解決することは、容易に確認することができる。偽造証明の
確率は、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には秘密である。さらに、定数c∈ZqはPにだけ知られているが、c
のコミットメントであるC=gcはVに知られることになる。Pは、秘密対数ui,vi,お
よびcに関する情報を露出せずに、関係式
【０１０６】
【数３８】
【０１０７】
をVに確信させることが要求される。
【０１０８】
スケールされる反復対数乗法証明:この証明は、元の値に対するより小さい変
分しか必要としない。4のChaum-Pedersen証明は、類似の証明
分しか必要としない。4のChaum-Pedersen証明は、類似の証明
【０１０９】
CP(Yi,Ci,Wi,Zi) (6)
【０１１０】
で置き換える必要がある。
【０１１１】
3.簡素なKシャッフル
本発明で構築した第1のシャッフル証明は、条件の限定的な集合を必要とする
。これは2つの理由から有用であろう。第1に、これは、後で出てくる、より一般
的なシャッフル証明の基本的なビルディングブロックとなる。偶然にも、これは
第2の重要な目的にも役立つ。この証明の一例を、特定の置換を効果的に「コミ
ットする」ために構築することができる。Zpの要素のタプル上でシャッフルを実
施する必要がある場合に、これは重要となる可能性があるが、これはまさしく投
票応用例で必要とされるものである(「タプル」はシーケンスまたは順序集合の
ことである。例えば、5-タプルまたは5倍は5つの要素をもつ順序集合であり、k-
タプルは不特定数の構成要素による有限の順序集合のことである。)。
。これは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に関して、
は公然と知られている。証明者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によってプロトコルを実施する。
明である。 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に基づいて)保たれることを保障する。
。スケールされる対数乗法証明をUおよびVの上でチェックすることによって、ベ
リファイアは、要素Xの初期入力シーケンスとシーケンスYの間の所望の関係が(
系2に基づいて)保たれることを保障する。
【０１２１】
スケールされる反復対数乗法証明が偽造されるか、またはS=Tcの単一の証明が
偽造されるか、あるいはVが系2の除外集合からcを偶然に選択した場合、偽造さ
れた証明が生成される可能性がある。したがって、偽造された証明の全体的な確
率は(3k+1)/qだけ上に有界である。本発明に記載のシャッフルプロトコルの下で
提供される証明に関するさらなる情報は、上記で参照した米国仮出願明細書に記
載されている。
偽造されるか、あるいはVが系2の除外集合からcを偶然に選択した場合、偽造さ
れた証明が生成される可能性がある。したがって、偽造された証明の全体的な確
率は(3k+1)/qだけ上に有界である。本発明に記載のシャッフルプロトコルの下で
提供される証明に関するさらなる情報は、上記で参照した米国仮出願明細書に記
載されている。
【０１２２】
一般に、ある応用例では簡素なkシャッフルで十分かもしれない。項目をシャ
ッフルするには、結果的に生じたY要素を生成したのは、元のX要素のうちのいず
れであるかを露出せずに、一連の出力要素Y1からYkまたはそれらのシーケンスが
、定数暗号化情報に基づいて、元の要素X1からXkまたはそれらの入力シーケンス
から導出されたことが確実な場合、各々暗号変換(例えば、累乗法)を使用する必
要がある。さらに、十分なレベルの証明のためには多数の反復を必要とする先行
技術で周知の、カットアンドチューズタイプの妥当性証明などの、煩わしい妥当
性の証明を使用することも必要とせずに、個々にこのようなシャッフルを実現す
ることが希望される。その代わりに、秘密累乗法値cに基づく一連のk独立Chaum-
Pedersen証明が本明細書に記載されたように使用される。
ッフルするには、結果的に生じたY要素を生成したのは、元のX要素のうちのいず
れであるかを露出せずに、一連の出力要素Y1からYkまたはそれらのシーケンスが
、定数暗号化情報に基づいて、元の要素X1からXkまたはそれらの入力シーケンス
から導出されたことが確実な場合、各々暗号変換(例えば、累乗法)を使用する必
要がある。さらに、十分なレベルの証明のためには多数の反復を必要とする先行
技術で周知の、カットアンドチューズタイプの妥当性証明などの、煩わしい妥当
性の証明を使用することも必要とせずに、個々にこのようなシャッフルを実現す
ることが希望される。その代わりに、秘密累乗法値cに基づく一連のk独立Chaum-
Pedersen証明が本明細書に記載されたように使用される。
【０１２３】
4.一般的ｋシャッフル
シャッフラPがすべての元の指数s1,…,skを知る必要があるということが、簡
素なkシャッフルプロトコルの明らかな限界である。多くの応用例では、これは
この通りではない。次のステップは、この制約を解消することである。
素なkシャッフルプロトコルの明らかな限界である。多くの応用例では、これは
この通りではない。次のステップは、この制約を解消することである。
【０１２４】
一般的ｋシャッフル問題:Zp,X1,…,XkとY1,…Ykのk要素の2つのシーケンスは
、公然と知られている。さらに、定数c∈ZqはPだけに知られているが、cのコミ
ットメントであるC=gcはVに知らされている。Pは、πまたは秘密cに関する情報
を露出せずに、すべての1≦i≦kに関して、
、公然と知られている。さらに、定数c∈ZqはPだけに知られているが、cのコミ
ットメントであるC=gcはVに知らされている。Pは、πまたは秘密cに関する情報
を露出せずに、すべての1≦i≦kに関して、
【０１２５】
【数４２】
【０１２６】
という特性を有するある種の置換π∈ΣkがあることをVに確信させることが要求
される。
される。
【０１２７】
一般的ｋシャッフル証明:この証明は、ベリファイアによって「適切にランダ
ム化された」簡素なkシャッフルと、補助定理2の適用から構築される。 1.Pはシーケンス
ム化された」簡素なkシャッフルと、補助定理2の適用から構築される。 1.Pはシーケンス
【０１２８】
【数４３】
【０１２９】
をランダムに、かつ独立して生成し、シーケンス
【０１３０】
【数４４】
【０１３１】
を露出する。
2.Vは別のシーケンス
【０１３２】
【数４５】
【０１３３】
をランダムに、かつ独立して生成し、これをチャレンジとしてPに与える。
3.Pは公然と
【０１３４】
【数４６】
【０１３５】
をセットし、秘密裏に
【０１３６】
【数４７】
【０１３７】
をセットする。ベリファイアが生成した値を加えるように証明者に要求すること
によって、証明者が特定の秘密(指数)を選択することを防止し、そうでない場合
は暗号の堅固さを保障するために役立つ。 4.Pはシーケンス
によって、証明者が特定の秘密(指数)を選択することを防止し、そうでない場合
は暗号の堅固さを保障するために役立つ。 4.Pはシーケンス
【０１３８】
【数４８】
【０１３９】
上で、別のコミットメントD=gd(異なる秘密指数)と逆置換π-1によって簡素なk
シャッフルを構築し、簡素なkシャッフルの節にあるように、結果的にシーケン
ス
シャッフルを構築し、簡素なkシャッフルの節にあるように、結果的にシーケン
ス
【０１４０】
【数４９】
【０１４１】
および対応する証明を生じる(Viは公開だが、viはPに対して秘密であることを想
起されたい。)。 5.Pは公然と
起されたい。)。 5.Pは公然と
【０１４２】
【数５０】
【０１４３】
および
【０１４４】
【数５１】
【０１４５】
をセットし、Chaum-Pedersen証明
【０１４６】
CP(g,Vi,Xi,Ai) (9)
CP(g,Ui,Yi,Bi) (10)
【０１４７】
を露出する。
したがって、要素AおよびBのシーケンスは要素XおよびYの入力シーケンスに対応
する。 6.値
する。 6.値
【０１４８】
【数５２】
【０１４９】
【数５３】
【０１５０】
が公然と評価される。
7.PはChaum-Pedersen証明
【０１５１】
CP(D,A,C,B) (13)
【０１５２】
を露出する。
【０１５３】
上記のステップ5-7は、証明者が元のデータを改ざんしていないことを保障す
るために役立つようにデータを留めておくことを証明者に効果的に要求する(こ
れらのステップは、上記の簡素なシャッフルの説明とは異なる)。簡素なkシャッ
フル証明が偽造されるか、Chaum-Pedersen証明の1つが偽造されるか、補助定理2
の除外集合からタプル(ui,…uk)が選択される場合だけ、偽造された証明が生成
される可能性がある。したがって、偽造の全体的な確率は
るために役立つようにデータを留めておくことを証明者に効果的に要求する(こ
れらのステップは、上記の簡素なシャッフルの説明とは異なる)。簡素なkシャッ
フル証明が偽造されるか、Chaum-Pedersen証明の1つが偽造されるか、補助定理2
の除外集合からタプル(ui,…uk)が選択される場合だけ、偽造された証明が生成
される可能性がある。したがって、偽造の全体的な確率は
【０１５４】
【数５４】
【０１５５】
だけ上に有界である。
【０１５６】
5.タプルのKシャッフル
関連技術の精通者ならば、前節で、簡素なシャッフルを選択することによって
、証明される可能性のあった置換を基本的に「凍結した」ことが理解されるであ
ろう。これによって、前節を、<g>の要素のkタプルのシャッフルまでどのように
して拡張すべきかを理解することが容易になる。k個のl-タプルのシーケンスをk
×lの配列と考えると、すべてのシーケンスは同じ置換に従って置換されたが、
各行は変更されずにあることを証明するために、単一の簡素なk-シャッフルを利
用することができる。したがって、上述のkシャッフルは、k要素の配列の各シー
ケンスに1回ずつ、l(エル)回実行される(kシャッフルの各々はこの簡素なシャッ
フルを再利用する)。具体的には、これはエルガマル対のタプルまで拡張される
。
、証明される可能性のあった置換を基本的に「凍結した」ことが理解されるであ
ろう。これによって、前節を、<g>の要素のkタプルのシャッフルまでどのように
して拡張すべきかを理解することが容易になる。k個のl-タプルのシーケンスをk
×lの配列と考えると、すべてのシーケンスは同じ置換に従って置換されたが、
各行は変更されずにあることを証明するために、単一の簡素なk-シャッフルを利
用することができる。したがって、上述のkシャッフルは、k要素の配列の各シー
ケンスに1回ずつ、l(エル)回実行される(kシャッフルの各々はこの簡素なシャッ
フルを再利用する)。具体的には、これはエルガマル対のタプルまで拡張される
。
【０１５７】
6.投票応用例
投票者の登録、票の形成および分配、票の記憶、および暗号化された電子投票
を利用する選挙の実行に関する情報は、2000年3月24日出願の「Multi-Way Elect
ion 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 Correc
tion of Compromised Ballots in Secret, Remote, Electronic Voting Systems
」という名称の米国仮出願第60/270,182号明細書、および2001年3月2日出願、「
Information Theoretically Anonymous Signatures with Discrete Log Securit
y」という名称の米国仮出願第60/272,883号明細書に記載されている。
を利用する選挙の実行に関する情報は、2000年3月24日出願の「Multi-Way Elect
ion 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 Correc
tion of Compromised Ballots in Secret, Remote, Electronic Voting Systems
」という名称の米国仮出願第60/270,182号明細書、および2001年3月2日出願、「
Information Theoretically Anonymous Signatures with Discrete Log Securit
y」という名称の米国仮出願第60/272,883号明細書に記載されている。
【０１５８】
一実施形態では、投票は、
【０１５９】
【数５５】
【０１６０】
という形式のエルガマル対 (または、さらに多くのデータが必要とされる場合は
、それらの対のシーケンス) として提供される。ここで、mは投票者の選択した(
本明細書に記載の)ある種の標準符号化、αiは投票者によって秘密裏に生成され
、hはディーラーのいない秘密共有方式によって構築された公開パラメータであ
る(例えば、T.Pedersen著、「A threshold cryptosystem without a trusted pa
rty, Advances in Cryptology EUROCRYPT '91, Lecture Notes in Computer Sc
ience」522-526頁。Springer-Verlag、1991年を参照のこと)。投票所が閉まると
(投票が終了すると)、オーソリティの独立したコレクションが連続して票をシャ
ッフルする。最後のシャッフルを出力する際、暗号化された票の最後のコレクシ
ョンが、この閾値方式に従って暗号解読され、明確なテキストの票決が通常の選
挙規則によって全景で作表される。
、それらの対のシーケンス) として提供される。ここで、mは投票者の選択した(
本明細書に記載の)ある種の標準符号化、αiは投票者によって秘密裏に生成され
、hはディーラーのいない秘密共有方式によって構築された公開パラメータであ
る(例えば、T.Pedersen著、「A threshold cryptosystem without a trusted pa
rty, Advances in Cryptology EUROCRYPT '91, Lecture Notes in Computer Sc
ience」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を秘密に
保つ。
れる。 3.秘密指数cによるシャッフルが、結果的に暗号化された投票に関して実行され
る。 4.ステップ1-2が反復される。 5.この時点で、暗号化されたメッセージは元のメッセージのc乗である。これは
、各投票の各座標を1/c乗することによって容易に決めることができる。この演
算のChaum-Pedersen証明は等しく容易に提供され、したがって、gとC=gcの役割
を単純に逆転させることによってベリファイアを納得させながらも、cを秘密に
保つ。
【０１６７】
上記のステップ1および2は、入力データをランダム化することを助け、シャッ
フリングする前に票の間の関係を選択するなど、入力データを変更することを回
避する。Chaum-Pedersen証明は、このランダム化のために追加された加算値が正
確であることを保障する。代替実施形態では、ステップ1および2(およびステッ
プ4)は省略される。
フリングする前に票の間の関係を選択するなど、入力データを変更することを回
避する。Chaum-Pedersen証明は、このランダム化のために追加された加算値が正
確であることを保障する。代替実施形態では、ステップ1および2(およびステッ
プ4)は省略される。
【０１６８】
7.セキュリティ保護されたメッセージ符号化
p-1が小さな素因数を有する場合、符号化されたメッセージに関する一部の情
報が漏洩する可能性がある。これはシャッフルプロトコルでは問題ではなく、む
しろ最初にmiを強力に暗号化する場合に問題である。これが心配するほど重大な
問題かどうかは、符号化されるべきメッセージの期待値によって異なる。しかし
、この問題は、符号化に特別な配慮をすることによっても解消することができる
。各メッセージは、位数が大きな素因数だけを含んでいる部分群に投影すること
ができる。本明細書に記載の大半の実施形態は、|<g>|が素数qである場合に限定
されるので、p=2q+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αm)として暗号化するの
ではなく、
【０１７５】
(gα,hαm2)
【０１７６】
として暗号化する。これは、すべてのメッセージは、
【０１７７】
【数５８】
【０１７８】
の順番2の部分群上への同一の自明な投影によって符号化されることを意味して
いる。方程式15は、マップm→m2が定義域上で可逆であることを保障する。逆転
させるには、(p-1)/2よりも小さな一意の平方根を取るだけである。したがって
、実際のメッセージm2が一旦暗号解読されれば、元のメッセージmを回復するの
は簡単なことである。
いる。方程式15は、マップm→m2が定義域上で可逆であることを保障する。逆転
させるには、(p-1)/2よりも小さな一意の平方根を取るだけである。したがって
、実際のメッセージm2が一旦暗号解読されれば、元のメッセージmを回復するの
は簡単なことである。
【０１７９】
8.適切なシステム
図1および以下の議論により、本発明の態様を実施することができる適切なコ
ンピューティング環境の簡潔で一般的な説明が得られる。必須ではないが、本発
明の実施形態は、汎用コンピュータ、例えばパーソナルコンピュータまたはウェ
ブサーバによって実行されるコンピュータ実行可能命令、例えばルーチンの一般
的なコンテクストで記述されるであろう。関連技術の精通者ならば、本発明の態
様(小規模の選挙など)は、インターネット機器、ハンドヘルド装置、ウェアラブ
ルコンピュータ、パーソナルデジタルアシスタンス(「PDA」)、マルチプロセッ
サシステム、マイクロプロセッサベースの、またはプログラム可能な家庭電化製
品、ネットワークPC、ミニコンピュータ、携帯電話または移動電話、セットトッ
プボックス、メインフレームコンピュータなどを含め、他のコンピュータシステ
ム構成で実行することができることが理解されるであろう。本発明の態様は、特
に本発明に記載の1つまたは2つ以上のコンピュータ実行可能命令を実行するよう
にプログラム、構成または構築された専用コンピュータまたはデータプロセッサ
で実施することができる。実際、本発明で一般に使用する「コンピュータ」とい
う用語は、どの上記装置並びにどのデータプロセッサをも示す。
ンピューティング環境の簡潔で一般的な説明が得られる。必須ではないが、本発
明の実施形態は、汎用コンピュータ、例えばパーソナルコンピュータまたはウェ
ブサーバによって実行されるコンピュータ実行可能命令、例えばルーチンの一般
的なコンテクストで記述されるであろう。関連技術の精通者ならば、本発明の態
様(小規模の選挙など)は、インターネット機器、ハンドヘルド装置、ウェアラブ
ルコンピュータ、パーソナルデジタルアシスタンス(「PDA」)、マルチプロセッ
サシステム、マイクロプロセッサベースの、またはプログラム可能な家庭電化製
品、ネットワークPC、ミニコンピュータ、携帯電話または移動電話、セットトッ
プボックス、メインフレームコンピュータなどを含め、他のコンピュータシステ
ム構成で実行することができることが理解されるであろう。本発明の態様は、特
に本発明に記載の1つまたは2つ以上のコンピュータ実行可能命令を実行するよう
にプログラム、構成または構築された専用コンピュータまたはデータプロセッサ
で実施することができる。実際、本発明で一般に使用する「コンピュータ」とい
う用語は、どの上記装置並びにどのデータプロセッサをも示す。
【０１８０】
本発明は、ローカルエリアネットワーク(LAN)、ワイドエリアネットワーク(WA
N)またはインターネットなどの通信ネットワークを介してリンクされている遠隔
処理装置によってタスクまたはモジュールが実行される、分散型コンピューティ
ング環境で実行することもできる。分散型コンピューティング環境では、プログ
ラムモジュールまたはサブルーチンは、ローカルメモリストレージとリモートメ
モリストレージの両方に配置することができる。本発明に記載の本発明は、磁気
/光学読み取り可能/取り外し可能なコンピュータディスクなどのコンピュータ読
み取り可能媒体に記憶または分配することも、チップにファームウェアとして記
憶することも、また、インターネットまたは他のネットワーク(無線ネットワー
クを含めて)を介して電子的に分配することもできる。関連技術の精通者ならば
、本発明に記載のプロトコルの部分は、対応する部分をクライアントコンピュー
タに常駐させながら、サーバコンピュータに常駐することができることが理解さ
れるであろう。このようなプロトコルに特定のデータ構造とデータの伝送も、本
発明の範囲内に含まれる。
N)またはインターネットなどの通信ネットワークを介してリンクされている遠隔
処理装置によってタスクまたはモジュールが実行される、分散型コンピューティ
ング環境で実行することもできる。分散型コンピューティング環境では、プログ
ラムモジュールまたはサブルーチンは、ローカルメモリストレージとリモートメ
モリストレージの両方に配置することができる。本発明に記載の本発明は、磁気
/光学読み取り可能/取り外し可能なコンピュータディスクなどのコンピュータ読
み取り可能媒体に記憶または分配することも、チップにファームウェアとして記
憶することも、また、インターネットまたは他のネットワーク(無線ネットワー
クを含めて)を介して電子的に分配することもできる。関連技術の精通者ならば
、本発明に記載のプロトコルの部分は、対応する部分をクライアントコンピュー
タに常駐させながら、サーバコンピュータに常駐することができることが理解さ
れるであろう。このようなプロトコルに特定のデータ構造とデータの伝送も、本
発明の範囲内に含まれる。
【０１８１】
別途記載のない限り、図1の種々のブロックの構成および動作は従来のデザイ
ンである。したがって、これらのブロックは関連技術の精通者には容易に理解さ
れるので、本発明ではさらに詳述する必要はない。
ンである。したがって、これらのブロックは関連技術の精通者には容易に理解さ
れるので、本発明ではさらに詳述する必要はない。
【０１８２】
図1を参照すると、システム100の適切な環境は、1つまたは2つ以上の投票者コ
ンピュータまたはクライアントコンピュータ102を含むが、そのそれぞれは、コ
ンピュータに、インターネットのワールドワイドウェブ部分106内のウェブサイ
トを含めてインターネットによってデータにアクセスし、データを交換すること
ができるようにするブラウザプログラムモジュール104を含む。投票者コンピュ
ータ102は、いずれも周知ではあるが図1には示さない、1つまたは2つ以上の中央
演算処理装置または他の論理処理回路構成、メモリ、入力装置(例えば、キーボ
ード、マイクロフォン、タッチスクリーン、およびポインティングデバイス)、
出力装置(例えば、表示装置、オーディオスピーカー、およびプリンタ)、記憶装
置(例えば、固定された、フロッピー(登録商標)および光学ディスクドライブ)を
含むことができる。投票者コンピュータ102は、さらに、オペレーティングシス
テム、1つまたは複数のアプリケーションプログラム(例えば、ワードプロセッシ
ングアプリケーションまたはスプレッドシートアプリケーション)などの他のプ
ログラムモジュールを含むこともできる。図1に示すように、投票者1,2,3,…Nを
表すN個の投票者コンピュータ102がある。
ンピュータまたはクライアントコンピュータ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)を含むことができ、それによって複数の投票者が同時に、または
並行して投票することを可能にする。
るサーバコンピュータシステム108または「投票収集センター」は、票の収集、
記憶および他の処理の大半またはすべてを実行する。サーバコンピュータ108に
接続されているデータベース110は、投票者コンピュータ102と、1つまたは複数
の投票所コンピュータ112およびサーバコンピュータ108との間で交換されるウェ
ブページとデータ(票およびシャッフル妥当性証明を含めて)の大半を記憶する。
投票所コンピュータ112は、パーソナルコンピュータ、サーバコンピュータ、ミ
ニコンピュータなどであり、インターネット106に接続されたコンピュータに即
座にアクセスすることのできない市民または投票者が、本発明に記載のシステム
下で電子的に投票できるようにするために、公共の投票所に配置されている。し
たがって、1つまたは複数の投票所コンピュータ112が公的な場所に配置されてい
るか、または公共選挙で投票者にアクセス可能な場合、投票者コンピュータ102
は、個々の投票者の家庭に配置することができる。投票所コンピュータ112は、1
つのサーバコンピュータと、LANを介してそのサーバコンピュータに接続された
複数のクライアントコンピュータまたは投票者端末を有するローカルエリアネッ
トワーク(LAN)を含むことができ、それによって複数の投票者が同時に、または
並行して投票することを可能にする。
【０１８４】
投票所コンピュータはさらに、Dallas Semiconductor社から供給される暗号法
iButtonsなどのiButtonsを読むためのiButtonリーダーを含むこともできる。iBu
ttonは、ステンレススチール缶に覆われた16mmのコンピュータチップであり、登
録している投票者の署名などの情報を暗号化し暗号解読するために必須の高速算
術計算用のマイクロプロセッサを含むことができる。さらなる情報は、http://w
ww.ibutton.comで見ることができる。当然ながら、本発明に記載のコンピュータ
読み取り可能媒体、無線周波数識別票(RFID)、1次元または2次元のバーコードま
たは他のデータ収集装置、およびこれらに関連したリーダーなどの、iButton以
外の他のデータ記憶装置を使用することができる。
iButtonsなどのiButtonsを読むためのiButtonリーダーを含むこともできる。iBu
ttonは、ステンレススチール缶に覆われた16mmのコンピュータチップであり、登
録している投票者の署名などの情報を暗号化し暗号解読するために必須の高速算
術計算用のマイクロプロセッサを含むことができる。さらなる情報は、http://w
ww.ibutton.comで見ることができる。当然ながら、本発明に記載のコンピュータ
読み取り可能媒体、無線周波数識別票(RFID)、1次元または2次元のバーコードま
たは他のデータ収集装置、およびこれらに関連したリーダーなどの、iButton以
外の他のデータ記憶装置を使用することができる。
【０１８５】
代替実施形態下では、会社役員や取締役の選出など、民間の選挙の状況ではシ
ステム100を使用することができる。この実施形態下では、投票者コンピュータ1
02は、株主のラップトップコンピュータまたはデスクトップコンピュータであっ
てよく、投票所コンピュータ112は選挙を実施している会社内(例えば、ロビー)
に設置された1つまたは複数のコンピュータであってよい。したがって、株主は
、会社に行って投票所コンピュータ112にアクセスして票を投じることができる
。
ステム100を使用することができる。この実施形態下では、投票者コンピュータ1
02は、株主のラップトップコンピュータまたはデスクトップコンピュータであっ
てよく、投票所コンピュータ112は選挙を実施している会社内(例えば、ロビー)
に設置された1つまたは複数のコンピュータであってよい。したがって、株主は
、会社に行って投票所コンピュータ112にアクセスして票を投じることができる
。
【０１８６】
1つまたは2つ以上のオーソリティまたは組織コンピュータ114も、インターネ
ット106を介してサーバコンピュータシステム108に接続されている。オーソリテ
ィコンピュータ114のそれぞれは、データベース110に記憶されている電子票を暗
号解読するために必須のキーを保持する。閾値暗号化システムは、オーソリティ
の総数nの部分集合t(すなわち、t<n)が票の暗号解読に賛成することを必要とし
ており、それによって、票の暗号解読にすべてのオーソリティが必要とされる必
須条件が回避される。すなわち、閾値暗号化の目的は、群のn人の構成員間で秘
密鍵sを共有することであり、事実上の部分集合Tが共同するときにメッセージを
暗号解読することができるようにすることである。これが、(t,n)閾値暗号化シ
ステムである。プロトコルは、(1)その群間で共同してキーを生成し、(2)秘密鍵
を再構成せずにメッセージを暗号解読するものと定義される。オーソリティコン
ピュータ114は、投票期間終了後にサーバコンピュータシステム108にオーソリテ
ィコンピュータ114の暗号解読の分担を提供することができ、その結果、サーバ
コンピュータシステムは票を暗号解読してその結果を総計することができる。
ット106を介してサーバコンピュータシステム108に接続されている。オーソリテ
ィコンピュータ114のそれぞれは、データベース110に記憶されている電子票を暗
号解読するために必須のキーを保持する。閾値暗号化システムは、オーソリティ
の総数nの部分集合t(すなわち、t<n)が票の暗号解読に賛成することを必要とし
ており、それによって、票の暗号解読にすべてのオーソリティが必要とされる必
須条件が回避される。すなわち、閾値暗号化の目的は、群のn人の構成員間で秘
密鍵sを共有することであり、事実上の部分集合Tが共同するときにメッセージを
暗号解読することができるようにすることである。これが、(t,n)閾値暗号化シ
ステムである。プロトコルは、(1)その群間で共同してキーを生成し、(2)秘密鍵
を再構成せずにメッセージを暗号解読するものと定義される。オーソリティコン
ピュータ114は、投票期間終了後にサーバコンピュータシステム108にオーソリテ
ィコンピュータ114の暗号解読の分担を提供することができ、その結果、サーバ
コンピュータシステムは票を暗号解読してその結果を総計することができる。
【０１８７】
さらに、記載の実施形態下では、オーソリティコンピュータの各々は、本発明
に記載のように1回の票のシャッフルを実行する。各シャッフルに関して、各オ
ーソリティコンピュータはシャッフル妥当性証明を生成し、そのシャッフル妥当
性証明は、暗号化されてサーバコンピュータ108に転送されるか、オーソリティ
コンピュータによってローカルに記憶することができる。代替実施形態では、オ
ーソリティコンピュータのさらなる集合が提供される。ここで、オーソリティコ
ンピュータの1つの集合は暗号化された票をシャッフルしてシャッフル妥当性証
明を生成し、一方、オーソリティコンピュータの第2の集合はその票を暗号解読
するために鍵の分担を使用する。
に記載のように1回の票のシャッフルを実行する。各シャッフルに関して、各オ
ーソリティコンピュータはシャッフル妥当性証明を生成し、そのシャッフル妥当
性証明は、暗号化されてサーバコンピュータ108に転送されるか、オーソリティ
コンピュータによってローカルに記憶することができる。代替実施形態では、オ
ーソリティコンピュータのさらなる集合が提供される。ここで、オーソリティコ
ンピュータの1つの集合は暗号化された票をシャッフルしてシャッフル妥当性証
明を生成し、一方、オーソリティコンピュータの第2の集合はその票を暗号解読
するために鍵の分担を使用する。
【０１８８】
オーソリティコンピュータ114に類似の、1つまたは2つ以上の任意に選択可能
なベリファイアコンピュータ130を提供することもできる。ベリファイアコンピ
ュータは、当該選挙が損なわれていないことを検証するために、選挙の写しを受
け取ることができる。例えば、ベリファイアコンピュータは、本発明に記載のよ
うに、オーソリティコンピュータのそれぞれからシャッフル妥当性証明を受け取
ることができる。ベリファイアコンピュータは、選挙の後で検証を実行すること
ができ、インターネットに接続されている必要はない。実際、検証は、本発明に
図示または記載の他のコンピュータによって実行することもできる。
なベリファイアコンピュータ130を提供することもできる。ベリファイアコンピ
ュータは、当該選挙が損なわれていないことを検証するために、選挙の写しを受
け取ることができる。例えば、ベリファイアコンピュータは、本発明に記載のよ
うに、オーソリティコンピュータのそれぞれからシャッフル妥当性証明を受け取
ることができる。ベリファイアコンピュータは、選挙の後で検証を実行すること
ができ、インターネットに接続されている必要はない。実際、検証は、本発明に
図示または記載の他のコンピュータによって実行することもできる。
【０１８９】
サーバコンピュータ、ベリファイアコンピュータまたはオーソリティコンピュ
ータが投票者登録プロトコルを実行することも、別個の登録コンピュータ(図示
せず)を提供することもできる。登録コンピュータは、指紋データ、声紋データ
、デジタル画像比較、および関連技術の精通者に周知の他の技術など、登録者の
生物測定データを読み取るための生物測定リーダーを含むことができる。投票者
の登録と、検証可能なシャッフルで使用するための匿名証明書の発行については
後述する。
ータが投票者登録プロトコルを実行することも、別個の登録コンピュータ(図示
せず)を提供することもできる。登録コンピュータは、指紋データ、声紋データ
、デジタル画像比較、および関連技術の精通者に周知の他の技術など、登録者の
生物測定データを読み取るための生物測定リーダーを含むことができる。投票者
の登録と、検証可能なシャッフルで使用するための匿名証明書の発行については
後述する。
【０１９０】
サーバコンピュータ108は、サーバエンジン120、ウェブページ管理構成要素12
2、データベース管理構成要素124、並びに図示しない他の構成要素を含む。サー
バエンジン120は、標準の機能の他に、電子投票プロトコルの部分を実行する。
暗号化プロトコルはサーバコンピュータに記憶することができるが、このような
プロトコルの部分は適切な定数と共にクライアントコンピュータにも記憶される
。実際、上記プロトコルは、磁気/光学読み取り可能/取り外し可能なコンピュー
タディスクなどのコンピュータ読み取り可能媒体、半導体チップ(例えば、EEPRO
M)に記憶されるマイクロコードに記憶し、および分配することも、インターネッ
トまたは他のネットワークを介して電子的に分配することもできる。関連技術の
精通者ならば、プロトコルの部分はサーバコンピュータに常駐するが、対応する
部分はクライアントコンピュータに常駐することが理解されるであろう。上記プ
ロトコルに特有なデータ構造およびデータの伝送も、本発明の範囲に含まれる。
したがって、サーバエンジン120は、権限を付与された投票者に対するすべての
必要な票の伝送、票の収集、票の検証(例えば、デジタル署名をチェックし、票
に含まれる妥当性の証明の検証を通すこと)、投票の集計、票の暗号解読および/
または投票の作表を実行する。代替実施形態下では、サーバエンジン120は、デ
ータ収集センターとしてすべての電子投票を収集するだけである。電子投票は、
次いで記憶されて、票をシャッフルし、投票集計を暗号解読して選挙結果を提供
するためのツールと共に、自治体などの選挙を管理する第三者機関に提供される
。同様に、シャッフル妥当性証明などの選挙検査情報は、ローカルに記憶するこ
とも、自治体または他の機関に提供することができる。
2、データベース管理構成要素124、並びに図示しない他の構成要素を含む。サー
バエンジン120は、標準の機能の他に、電子投票プロトコルの部分を実行する。
暗号化プロトコルはサーバコンピュータに記憶することができるが、このような
プロトコルの部分は適切な定数と共にクライアントコンピュータにも記憶される
。実際、上記プロトコルは、磁気/光学読み取り可能/取り外し可能なコンピュー
タディスクなどのコンピュータ読み取り可能媒体、半導体チップ(例えば、EEPRO
M)に記憶されるマイクロコードに記憶し、および分配することも、インターネッ
トまたは他のネットワークを介して電子的に分配することもできる。関連技術の
精通者ならば、プロトコルの部分はサーバコンピュータに常駐するが、対応する
部分はクライアントコンピュータに常駐することが理解されるであろう。上記プ
ロトコルに特有なデータ構造およびデータの伝送も、本発明の範囲に含まれる。
したがって、サーバエンジン120は、権限を付与された投票者に対するすべての
必要な票の伝送、票の収集、票の検証(例えば、デジタル署名をチェックし、票
に含まれる妥当性の証明の検証を通すこと)、投票の集計、票の暗号解読および/
または投票の作表を実行する。代替実施形態下では、サーバエンジン120は、デ
ータ収集センターとしてすべての電子投票を収集するだけである。電子投票は、
次いで記憶されて、票をシャッフルし、投票集計を暗号解読して選挙結果を提供
するためのツールと共に、自治体などの選挙を管理する第三者機関に提供される
。同様に、シャッフル妥当性証明などの選挙検査情報は、ローカルに記憶するこ
とも、自治体または他の機関に提供することができる。
【０１９１】
ウェブページ構成要素122は、後述するように、電子投票ボックスウェブペー
ジなどのウェブページの作成と表示、またはルーティングを取り扱う。投票者お
よびユーザは、http://www.votehere.netなどのサーバコンピュータ108に関連付
けられたURL、または、自治体のURLなどの選挙に関連付けられたURLによってサ
ーバコンピュータ108にアクセスすることができる。自治体は、サーバコンピュ
ータシステム108を直接的に主催または運営したとしても、そのような受け取っ
た電子投票を、サーバコンピュータシステムを操作することのできる第三者の投
票権限付与者に転送することもできる。URLまたは本発明で示したリンクまたは
アドレスはいかなる資源ロケータであってもよい。
ジなどのウェブページの作成と表示、またはルーティングを取り扱う。投票者お
よびユーザは、http://www.votehere.netなどのサーバコンピュータ108に関連付
けられたURL、または、自治体のURLなどの選挙に関連付けられたURLによってサ
ーバコンピュータ108にアクセスすることができる。自治体は、サーバコンピュ
ータシステム108を直接的に主催または運営したとしても、そのような受け取っ
た電子投票を、サーバコンピュータシステムを操作することのできる第三者の投
票権限付与者に転送することもできる。URLまたは本発明で示したリンクまたは
アドレスはいかなる資源ロケータであってもよい。
【０１９２】
ウェブページ管理プロセス122およびサーバコンピュータ108は、権限を付与さ
れた投票者またはシステム管理者などの権限を付与された人物だけがアクセスす
ることのできるセキュリティ保護されたセクションまたはページを有することが
できる。サーバコンピュータ108は、そのようなユーザを認証するために、セキ
ュアソケットレイヤ(「SSL」)およびトークンまたはクッキーを使用することが
できる。実際、小規模な選挙または不正行為の確率が低い(または、不正行為の
結果が比較的重大でない)選挙の場合、システム100は、上記の特許出願明細書に
記載の複雑な電子暗号化された票を使用するのではなく、後述するような投票を
収集し記憶するための簡素なネットワークセキュリティ対策を使用することがで
きる。ユーザを認証する方法(パスワードの使用によるなど)、セキュリティ保護
された伝送接続を確立する方法、およびセキュリティ保護されたサーバとウェブ
ページを提供する方法は、関連技術の精通者には周知である。
れた投票者またはシステム管理者などの権限を付与された人物だけがアクセスす
ることのできるセキュリティ保護されたセクションまたはページを有することが
できる。サーバコンピュータ108は、そのようなユーザを認証するために、セキ
ュアソケットレイヤ(「SSL」)およびトークンまたはクッキーを使用することが
できる。実際、小規模な選挙または不正行為の確率が低い(または、不正行為の
結果が比較的重大でない)選挙の場合、システム100は、上記の特許出願明細書に
記載の複雑な電子暗号化された票を使用するのではなく、後述するような投票を
収集し記憶するための簡素なネットワークセキュリティ対策を使用することがで
きる。ユーザを認証する方法(パスワードの使用によるなど)、セキュリティ保護
された伝送接続を確立する方法、およびセキュリティ保護されたサーバとウェブ
ページを提供する方法は、関連技術の精通者には周知である。
【０１９３】
この選挙方式およびシステムは、それぞれの掲示物がデジタル署名され、1つ
も消去されることのない「掲示板」を使用する。K.Sako,J.Kilian,R.およびCram
er, R.Gennaro, B.Schoenmakersの論文を参照されたい。この掲示板はウェブサ
ーバとして実施される。「投票箱」はこの掲示板上に常駐し、すべての暗号化さ
れた票を保持する。ウェブサーバのデータを、追記型光ディスク(WORM)永久記憶
媒体または類似の装置に書き込むことによって、消去を防止することができる。
このような掲示板システムに関するさらなる詳細は、「Electronic Voting Sche
me Employing Permanent Ballot Storage」という名称の、米国特許出願第09/53
4,836号明細書に記載されている。
も消去されることのない「掲示板」を使用する。K.Sako,J.Kilian,R.およびCram
er, R.Gennaro, B.Schoenmakersの論文を参照されたい。この掲示板はウェブサ
ーバとして実施される。「投票箱」はこの掲示板上に常駐し、すべての暗号化さ
れた票を保持する。ウェブサーバのデータを、追記型光ディスク(WORM)永久記憶
媒体または類似の装置に書き込むことによって、消去を防止することができる。
このような掲示板システムに関するさらなる詳細は、「Electronic Voting Sche
me Employing Permanent Ballot Storage」という名称の、米国特許出願第09/53
4,836号明細書に記載されている。
【０１９４】
本発明の一実施形態はコンピュータを接続するためにインターネットを使用す
るように本発明には記載されているが、他の代替実施形態も可能であることに留
意されたい。例えば、本発明の態様は、スタンドアロンコンピュータによって使
用することができる。本発明の態様は、どのような相互接続されたデータ処理マ
シンによって使用することもできる。本発明に記載の方法またはプロトコルの態
様を実施するために、このようなマシンでは、ブラウザを使用せず、クライアン
トソフトウェアを使用することができる。
るように本発明には記載されているが、他の代替実施形態も可能であることに留
意されたい。例えば、本発明の態様は、スタンドアロンコンピュータによって使
用することができる。本発明の態様は、どのような相互接続されたデータ処理マ
シンによって使用することもできる。本発明に記載の方法またはプロトコルの態
様を実施するために、このようなマシンでは、ブラウザを使用せず、クライアン
トソフトウェアを使用することができる。
【０１９５】
9.選挙の実施例
一般的k-シャッフルプロトコルの一応用例は、電子投票の分野にある。選挙を
「普遍的に検証可能」にするために、提出された票は最初に有効な(すなわち、
登録された)投票者に絶対的に接続可能である必要がある。票は、「開票」が可
能となる前に、検証可能プロセス、すなわち分離プロセスにおいて偽票が提出さ
れることを許可しないことによって何とかして「署名と分離される」必要がある
。
「普遍的に検証可能」にするために、提出された票は最初に有効な(すなわち、
登録された)投票者に絶対的に接続可能である必要がある。票は、「開票」が可
能となる前に、検証可能プロセス、すなわち分離プロセスにおいて偽票が提出さ
れることを許可しないことによって何とかして「署名と分離される」必要がある
。
【０１９６】
本発明で提示されるプロトコルは、選挙結果に種々の関心を抱くN人の「作表
オーソリティ」の集合に依存している。 1.このプロトコルは、完了されるべき作表のために、少なくともt人のオーソリ
ティが正当に振舞わなければならない閾値スキーム(scheme)である。(パラメー
タtは、任意の値1≦t≦Nになるように選挙前に選択することができる)。したが
って、具体的には、オーソリティが自分のシャッフルをいかなる特定の順序で完
了することも必須ではなく、また、すべてのオーソリティが参加することさえも
必須ではない(特殊なt=Nの場合を除いて)。 2.すべてのオーソリティが共謀したとしても、選挙結果を検証することを希望す
る外部の監査役によって見つからずに、偽の選挙結果を生成することはできない
。 3.個々の投票のプライバシーは、少なくともt人のオーソリティが共謀すること
によってのみ侵害される可能性がある。
オーソリティ」の集合に依存している。 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の論文を参照のこと。
答、投票スタイル、投票所が開かれ、閉じられる時刻が含まれる。 (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は、特定の有権者に試行することによってその応答を認証するため、「暗号
化された応答のシーケンス」
以上の自分の応答を、選挙標準「ビット符号化」(選挙開始期間中にオーソリテ
ィによって合意され署名されたもの。上記参照のこと。)によって、メッセージ
のシーケンスm1,…,md∈Gに符号化する。(これに関しては以下でさらに記載する
。)「メッセージの重複」dは別の選挙パラメータである(上記参照のこと。)。 2.Vは、暗号化のために、指数α1,…,αdを、0≦αj<|g|からアトランダムに個
別に選択する。 3.Vは、特定の有権者に試行することによってその応答を認証するため、「暗号
化された応答のシーケンス」
【０２００】
【数５９】
【０２０１】
を、Vによって生成された「添付の」デジタル署名と共に「投票収集センター」
に戻す。 4.Vによって提出されたデジタル署名により検証され、かつVが以前に票を投じて
いなかった場合、中央収集機関によって署名された受領書がVに対して発行され
る。この受領書は、特定の選挙において当該投票者からの投票が受領されたこと
を承認するが、(暗号化またはハッシュされた情報さえも)その票の内容に関する
情報は含まない。この受領書は、当該投票者に対しても送信することができる。
この受領書は、また、当該投票者の票が消失せず、また、悪意をもって削除され
なかったことを確認するためにも役立つ。
に戻す。 4.Vによって提出されたデジタル署名により検証され、かつVが以前に票を投じて
いなかった場合、中央収集機関によって署名された受領書がVに対して発行され
る。この受領書は、特定の選挙において当該投票者からの投票が受領されたこと
を承認するが、(暗号化またはハッシュされた情報さえも)その票の内容に関する
情報は含まない。この受領書は、当該投票者に対しても送信することができる。
この受領書は、また、当該投票者の票が消失せず、また、悪意をもって削除され
なかったことを確認するためにも役立つ。
【０２０２】
第3:結果を作表する
1.最初に、投票者の応答の集合は、それぞれが受領された票の応答の総数である
各長さがNcastの2d個のシーケンスに配列される。各シーケンスは、標準の票応
答形式の1つの座標に対応する(方程式16)。各シーケンスの項目は投票者によっ
て順序付けられる。各投票者に割り当てられる指標は、一貫性のある限り重要で
はない。このようにして、外部オブザーバーは、署名された票が、非常に簡素な
方法で変換され、データレイアウトに正しい解釈を適用することによって、依然
として署名され受領された応答の同じ集合を表していることを確認することがで
きる。 2.任意の便宜的な順序で、sオーソリティのシーケンスはそれぞれに以下のステ
ップを実行する。 (a)Sをシーケンスに現在入っているオーソリティとする。 (b)Sは、dNcast指数
各長さがNcastの2d個のシーケンスに配列される。各シーケンスは、標準の票応
答形式の1つの座標に対応する(方程式16)。各シーケンスの項目は投票者によっ
て順序付けられる。各投票者に割り当てられる指標は、一貫性のある限り重要で
はない。このようにして、外部オブザーバーは、署名された票が、非常に簡素な
方法で変換され、データレイアウトに正しい解釈を適用することによって、依然
として署名され受領された応答の同じ集合を表していることを確認することがで
きる。 2.任意の便宜的な順序で、sオーソリティのシーケンスはそれぞれに以下のステ
ップを実行する。 (a)Sをシーケンスに現在入っているオーソリティとする。 (b)Sは、dNcast指数
【０２０３】
1≦βjl≦|g| １≦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人のオーソリティが、各シャッフルされた票で閾値暗号解読プロト
コルを実行する。
成される。 (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」)と中間C
haum-Pedersen証明のチェックの両方をパスする場合だけ、シャッフルを実行す
る。) 第2に、シャッフルが完全に1回実行され、検証されると、t人の作表オー
ソリティの集合は、エルガマル対の最終集合の各mの暗号解読を共同で (かつ検
証可能に) 計算するために、秘密鍵の分担を使用する。
のT≦tの集合は、それぞれに順次、検証可能なk×dシャッフルを実行する(ここ
で、kは投じられた票の総数である)。各シャッフルからの出力シーケンスと証明
は署名され、次の作表オーソリティに渡される。(各作表オーソリティは、その
入力が署名のチェックおよび(前回の)シャッフルゼロ知識証明(「ZKP」)と中間C
haum-Pedersen証明のチェックの両方をパスする場合だけ、シャッフルを実行す
る。) 第2に、シャッフルが完全に1回実行され、検証されると、t人の作表オー
ソリティの集合は、エルガマル対の最終集合の各mの暗号解読を共同で (かつ検
証可能に) 計算するために、秘密鍵の分担を使用する。
【０２１０】
一般に、シャッフルする各オーソリティは、最初に置換の生成を担当するので
、入力と出力の対応関係を知ることになる。しかし、シャッフルは行われ、1回
のシャッフルの出力は、シャッフルする別のオーソリティによって実行される別
のシャッフルへの入力として使用される。したがって、すべてのオーソリティが
共謀しない限り、シャッフルするオーソリティの1人として、最初の入力と最後
の出力との間の対応関係を知ることは全くない。しかし後述するように、さらな
る強化によりこの可能性も排除される。
、入力と出力の対応関係を知ることになる。しかし、シャッフルは行われ、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証明 を発行する。
l)) (c)自分のk-シャッフル証明 (d)上記ステップ(g)下のChaum-Pedersen証明 を発行する。
【０２１２】
一般に、「選挙の写し」を公開することができ、これには以下のものが含まれ
る。 1.投票者のID情報と投票者の公開鍵を含む投票者名簿 2.k投票者の署名済みの票の元の集合 3. tk×dシャッフル(上記の証明を含めて) 4.最後の共有暗号解読の妥当性証明 5.最終的な投票集計
る。 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に示すようなシャッフル妥
当性証明が生成される。このシャッフル妥当性証明によって、第三者機関は、す
べての入力されたデータ(投票)に同じ演算が適用されたこと、および、票の変更
がまったく行われなかったことを保障することができる。
ロトコルの基本的な応用例を示している。ブロック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に示すような投票集計を生成する。第三者機関は、各シャッフラが選挙の
公平性を維持したことを保障するために、特に各シャッフル妥当性証明を分析す
ることによって選挙を検証することができる。
に示すような2回目のシャッフルを受けた票の集合を生成する。ここでもまた、
ブロック214に示すようなシャッフル妥当性証明が生成される。ブロック212のシ
ャッフルを受けた票が3回目のシャッフルを受け、ブロック216下で最後のシャッ
フルを受けた票の集合を生成する。3回目のシャッフルに基づいて、第3のシャッ
フル妥当性証明218が同様に生成される。すなわち、この実施例では、3×3の配
列が提供される。このシャッフリングに引き続き、票が暗号解読されて、ブロッ
ク220に示すような投票集計を生成する。第三者機関は、各シャッフラが選挙の
公平性を維持したことを保障するために、特に各シャッフル妥当性証明を分析す
ることによって選挙を検証することができる。
【０２１７】
シャッフルプロトコルをサブルーチンに効果的に分離し、電子投票方式などの
種々の応用例に使用することができることが上記で示されている。第1のサブル
ーチンは、証明者とベリファイアとの間の、スケールされる反復対数乗法証明の
機能を提供する。第2のサブルーチンは、簡素なシャッフルプロトコルの機能を
提供し、スケールされる反復対数乗法証明を使用する。その後、第3のサブルー
ルチンは、一般的シャッフル機能を実施するが、そこでは、シャッフラは簡素な
シャッフルの第2のサブルーチン上に構築された指数を知らない。第4のサブルー
チンは、kタプルの要素のシャッフリングまで第3のサブルーチンを拡張する。
種々の応用例に使用することができることが上記で示されている。第1のサブル
ーチンは、証明者とベリファイアとの間の、スケールされる反復対数乗法証明の
機能を提供する。第2のサブルーチンは、簡素なシャッフルプロトコルの機能を
提供し、スケールされる反復対数乗法証明を使用する。その後、第3のサブルー
ルチンは、一般的シャッフル機能を実施するが、そこでは、シャッフラは簡素な
シャッフルの第2のサブルーチン上に構築された指数を知らない。第4のサブルー
チンは、kタプルの要素のシャッフリングまで第3のサブルーチンを拡張する。
【０２１８】
図3を参照すると、スケールされる反復対数乗法証明を実施するためのルーチ
ン300が示されている。ブロック302では、初期暗号パラメータの合意が、例えば
投票機構などによって行われる。これらの初期パラメータは、群(例えば、Zp)、
部分群オペレータg、群のサイズG、および生成された部分群pおよびqを含む。こ
の情報は、n人のシャッフラまたはオーソリティコンピュータ114およびベリファ
イアコンピュータ130に提供される。
ン300が示されている。ブロック302では、初期暗号パラメータの合意が、例えば
投票機構などによって行われる。これらの初期パラメータは、群(例えば、Zp)、
部分群オペレータg、群のサイズG、および生成された部分群pおよびqを含む。こ
の情報は、n人のシャッフラまたはオーソリティコンピュータ114およびベリファ
イアコンピュータ130に提供される。
【０２１９】
ブロック304では、シャッフラ(または証明者P)は秘密指数cを選択し、部分群
ジェネレータgに基づいてCを生成する。さらに、シャッフラは、受け取ったXお
よび1からkまでのインデックスiに対するY値を受け取るか、または生成し、X、Y
、およびCをベリファイアに提供する。
ジェネレータgに基づいてCを生成する。さらに、シャッフラは、受け取ったXお
よび1からkまでのインデックスiに対するY値を受け取るか、または生成し、X、Y
、およびCをベリファイアに提供する。
【０２２０】
ブロック304では、シャッフラはさらに、ランダム指数をriとして秘密裏に生
成するが、これは、部分群gジェネレータに基づいて、0からkまでのiの各値に対
して値Riを生成するために使用される。同様に、ブロック304下では、シャッフ
ラは、生成されたランダム指数riを使用してWiとZiを生成する。
成するが、これは、部分群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に等しいことを確認する。
よび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でベリファイアに提供される。
チン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をチェックする
。
すなわち、ベリファイアは、UおよびVのシーケンスに対して上記の、スケールさ
れる反復対数乗法証明プロトコルを実行し、コミットメント値Cをチェックする
。
【０２２４】
図5を参照すると、シャッフラが指数を知らない場合の、一般的シャッフルプ
ロトコル500が示されている。プロトコル500の初期ステップは、ベリファイアが
シャッフラの秘密指数にランダム化要素を加えることを除き、400の初期ステッ
プと類似する。ブロック502に示すように、シャッフラは初期値のランダムシー
ケンスを秘密裏に生成するが、これは、初期シーケンス
ロトコル500が示されている。プロトコル500の初期ステップは、ベリファイアが
シャッフラの秘密指数にランダム化要素を加えることを除き、400の初期ステッ
プと類似する。ブロック502に示すように、シャッフラは初期値のランダムシー
ケンスを秘密裏に生成するが、これは、初期シーケンス
【０２２５】
【数６２】
【０２２６】
を生成するために、部分群ジェネレータgによって指数として使用される。同様
に、ブロック504では、ベリファイアは、1からkまでの値iに対する要素eの別の
シーケンスを生成し、そのシーケンスをチャレンジとしてシャッフラに提供する
。ブロック506では、シャッフラは前のシーケンスにそのシーケンスのチャレン
ジeを秘密裏に加え、その時までに一連の値
に、ブロック504では、ベリファイアは、1からkまでの値iに対する要素eの別の
シーケンスを生成し、そのシーケンスをチャレンジとしてシャッフラに提供する
。ブロック506では、シャッフラは前のシーケンスにそのシーケンスのチャレン
ジeを秘密裏に加え、その時までに一連の値
【０２２７】
【数６３】
【０２２８】
を公然と生成する。
【０２２９】
ブロック508では、シャッフラは、別の秘密裏に(シャッフラが選択した異なる
秘密指数dを使用する)生成されたコミットメントDによってシーケンスU上に簡素
なkシャッフルを構築し、値Vのシーケンスを生成する。次いで、公然と、シャッ
フラは1からkまでのインデックスに対する値AおよびBのシーケンスに対するChau
m-Pedersen証明を露出し、そのシーケンスの積を値AおよびBとして公然と生成し
て、図示するようにD、A、CおよびBの間の関係にChaum-Pedersen証明を提供する
。ブロック510の下では、この証明データはベリファイアに提供され、ベリファ
イアはこの証明データをブロック512の下で検証する。
秘密指数dを使用する)生成されたコミットメントDによってシーケンスU上に簡素
なkシャッフルを構築し、値Vのシーケンスを生成する。次いで、公然と、シャッ
フラは1からkまでのインデックスに対する値AおよびBのシーケンスに対するChau
m-Pedersen証明を露出し、そのシーケンスの積を値AおよびBとして公然と生成し
て、図示するようにD、A、CおよびBの間の関係にChaum-Pedersen証明を提供する
。ブロック510の下では、この証明データはベリファイアに提供され、ベリファ
イアはこの証明データをブロック512の下で検証する。
【０２３０】
10.検証可能なシャッフルによって匿名証明書を発行する
上記で提示されたのは、暗号化データを検証可能にシャッフリングする新しく
て効率的な構築と、この構築を「普遍的に検証可能」な電子選挙システムを実行
するために使用することのできる特別な方法である。このシステムでは、投票時
に収集された票データを「シャッフル」または「匿名化」することは、選挙オー
ソリティの集合に依存する。このプロセスは、すべての票が投じられた後、票が
暗号解読されて作表される前に行われる。この妥当性の構築は、1人または2人以
上の選挙オーソリティが、最終的な選挙の写しを検査しているいずれからも見つ
からずに、元の選挙データに変更を加えることを防止する。
て効率的な構築と、この構築を「普遍的に検証可能」な電子選挙システムを実行
するために使用することのできる特別な方法である。このシステムでは、投票時
に収集された票データを「シャッフル」または「匿名化」することは、選挙オー
ソリティの集合に依存する。このプロセスは、すべての票が投じられた後、票が
暗号解読されて作表される前に行われる。この妥当性の構築は、1人または2人以
上の選挙オーソリティが、最終的な選挙の写しを検査しているいずれからも見つ
からずに、元の選挙データに変更を加えることを防止する。
【０２３１】
この手法の欠点は、選挙の公平性と同様の強固な機構によっては、投票者の匿
名性が保護されないということである。選挙の公平性は、単に計算上の処理のし
にくさによって保護される。すなわち、選挙オーソリティが、検出されずに偽の
選挙結果を生成することは、たとえ全員が共謀したとしても基本的には不可能で
ある。しかし、共謀することによって、彼らは、比較的容易にいかなる個々の投
票者の票の内容をも判断することができる。
名性が保護されないということである。選挙の公平性は、単に計算上の処理のし
にくさによって保護される。すなわち、選挙オーソリティが、検出されずに偽の
選挙結果を生成することは、たとえ全員が共謀したとしても基本的には不可能で
ある。しかし、共謀することによって、彼らは、比較的容易にいかなる個々の投
票者の票の内容をも判断することができる。
【０２３２】
この弱点を解消する新しい選挙プロトコルを構築するために、同じ基本的なシ
ャッフル構築を使用することができる。このアイディアは、シャッフリングを、
選挙の登録または票の要求のフェーズに移動し、それによって、厳重な管理と選
挙の資格規定の検査、すなわち登録した投票者による票だけを数え、同一投票者
からの複数の票は受理しないといった管理と検査を損なうことなく、投票者の識
別を匿名化するということである。これが達成されると、もはや票を暗号化する
必要さえなく、「普通文で」作表を実行することができる。これは、明らかに検
査するのに容易なプロセスである。
ャッフル構築を使用することができる。このアイディアは、シャッフリングを、
選挙の登録または票の要求のフェーズに移動し、それによって、厳重な管理と選
挙の資格規定の検査、すなわち登録した投票者による票だけを数え、同一投票者
からの複数の票は受理しないといった管理と検査を損なうことなく、投票者の識
別を匿名化するということである。これが達成されると、もはや票を暗号化する
必要さえなく、「普通文で」作表を実行することができる。これは、明らかに検
査するのに容易なプロセスである。
【０２３３】
この構成を「匿名登録プロセス」の一部として使用するというアイディアは、
投票以外にも応用例がある。サーバまたはファイルなどの資源へのアクセスは権
限を付与された人員に限定される必要があるが、権限を付与された人員が個人の
識別を保護することを希望する場合はいかなる状況でも、この構成を使用して両
方の要件を同時に満たすことができる。例えば、グループ署名の応用例は、本発
明に記載のプロトコルにおしなべて適用することができる。本発明では、一般に
「投票者」という用語は、本発明に記載の一部またはすべてのプロトコルを利用
するいかなる個人または組織を意味する。
投票以外にも応用例がある。サーバまたはファイルなどの資源へのアクセスは権
限を付与された人員に限定される必要があるが、権限を付与された人員が個人の
識別を保護することを希望する場合はいかなる状況でも、この構成を使用して両
方の要件を同時に満たすことができる。例えば、グループ署名の応用例は、本発
明に記載のプロトコルにおしなべて適用することができる。本発明では、一般に
「投票者」という用語は、本発明に記載の一部またはすべてのプロトコルを利用
するいかなる個人または組織を意味する。
【０２３４】
「プロトコルの概要」
2つの異なるプロトコルの形体が提供され、どちらも同じ高レベルの情報の流
れに従う。各プロトコルは、公開鍵の集合がいくつかの中央認証データベースま
たは証明書サーバに記憶されていることを推定するところから始まる。各対応す
る秘密鍵は、1人の、しかもたった1人の有権者にのみ知られている。さらに、公
開鍵と個々の投票者の対応関係は、証明書サーバを管理する1つまたは2つ以上の
エンティティによって知られる(これらの公開鍵/秘密鍵対の厳密な形式は、プロ
トコルの異なる形体ごとに若干相異する。)。実際には、公開鍵は、すべての識
別情報を公開鍵と共に単一のフォーマットされたデータとして結合する「デジタ
ル証明書」の形式で包まれるる可能性がある(これは、広く受け入れられている
公開鍵基盤すなわちPKIが準拠している規則である。) 通常、このような鍵と証明書の分配は、厳重に管理された登録プロセスによっ
て達成される。このプロセスの最も安全なものは、証明書生成時に投票者が物理
的に識別される「本人による」登録プロセスであろう(このような登録プロセス
は、米国特許出願第09/534,836号明細書で詳述されている。)。プロトコルに存
在する2つの異なるタイプの証明書を区別することが重要である。第1のタイプは
、上記の証明書(「標準証明書」)であり、この場合、公開鍵と個々の人物との間
の関係が公然と、または少なくとも広く知られている。第2のタイプは、上記の
初期登録のフェーズに続くプロトコルの段階で分配される証明書(「匿名証明書
」)である。これらの匿名証明書は、少なくとも異なる公開鍵を含んでいるが、
所与の匿名証明書の所有者を知っている個人だけが所有者自身であるという事実
によって相互に区別することができる。このプロトコルの目的は、 標準証明書の1つを所有する個人だけに、匿名証明書を発行する ことを保障することである。
れに従う。各プロトコルは、公開鍵の集合がいくつかの中央認証データベースま
たは証明書サーバに記憶されていることを推定するところから始まる。各対応す
る秘密鍵は、1人の、しかもたった1人の有権者にのみ知られている。さらに、公
開鍵と個々の投票者の対応関係は、証明書サーバを管理する1つまたは2つ以上の
エンティティによって知られる(これらの公開鍵/秘密鍵対の厳密な形式は、プロ
トコルの異なる形体ごとに若干相異する。)。実際には、公開鍵は、すべての識
別情報を公開鍵と共に単一のフォーマットされたデータとして結合する「デジタ
ル証明書」の形式で包まれるる可能性がある(これは、広く受け入れられている
公開鍵基盤すなわちPKIが準拠している規則である。) 通常、このような鍵と証明書の分配は、厳重に管理された登録プロセスによっ
て達成される。このプロセスの最も安全なものは、証明書生成時に投票者が物理
的に識別される「本人による」登録プロセスであろう(このような登録プロセス
は、米国特許出願第09/534,836号明細書で詳述されている。)。プロトコルに存
在する2つの異なるタイプの証明書を区別することが重要である。第1のタイプは
、上記の証明書(「標準証明書」)であり、この場合、公開鍵と個々の人物との間
の関係が公然と、または少なくとも広く知られている。第2のタイプは、上記の
初期登録のフェーズに続くプロトコルの段階で分配される証明書(「匿名証明書
」)である。これらの匿名証明書は、少なくとも異なる公開鍵を含んでいるが、
所与の匿名証明書の所有者を知っている個人だけが所有者自身であるという事実
によって相互に区別することができる。このプロトコルの目的は、 標準証明書の1つを所有する個人だけに、匿名証明書を発行する ことを保障することである。
【０２３５】
投票応用例などの大半の応用例では、このプロトコルの目的は、さらに、
各個人に、その個人が有する標準証明書と同数だけ匿名証明書を発行する(通
常、標準証明書の各所有者は標準証明書を1つだけ有する。) ことを保障することである。
常、標準証明書の各所有者は標準証明書を1つだけ有する。) ことを保障することである。
【０２３６】
標準証明書の登録が完了すると、プロトコルの各形体はそれぞれに以下のよう
に進められる。
に進められる。
【０２３７】
初期化:未処理の公開鍵の集合Kが証明書サーバ(例えば、サーバ108)で構成され
、標準証明書の集合に関連付けられた公開鍵の集合になるように初期設定される
。各個人が登録して、例えば標準デジタル証明書を受け取るという、各個人の初
期登録プロセス中に公開鍵の集合が生成される。この初期登録プロセスの下で生
成された公開鍵は一緒にプールされて、集合Kを生成する。各個人は、集合Kの公
開鍵の1つに関連付けられた秘密鍵を保持する。
、標準証明書の集合に関連付けられた公開鍵の集合になるように初期設定される
。各個人が登録して、例えば標準デジタル証明書を受け取るという、各個人の初
期登録プロセス中に公開鍵の集合が生成される。この初期登録プロセスの下で生
成された公開鍵は一緒にプールされて、集合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を選択し、
バ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は、
)。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は、
複数回発行することが望まれる場合、Sは、
【０２４３】
K=J∪M'∪H' (19)
【０２４４】
をセットする。および
ii.Sは、フォーマットされた証明書要求にデジタル署名し、それによって匿名証
明書を作成し、(署名した)証明書をPに戻し、後の匿名認証のためにその証明書
をデータベースに記憶する。 7.プロセスは、次に、新たなPの始めから続行し、Kは適切に変更される。
明書を作成し、(署名した)証明書をPに戻し、後の匿名認証のためにその証明書
をデータベースに記憶する。 7.プロセスは、次に、新たなPの始めから続行し、Kは適切に変更される。
【０２４５】
すなわち、個人Pは、証明書サーバSに対して、その個人の選択した部分集合M
の公開鍵の1つに関連付けられた秘密鍵をその個人が保持していることを、公開
鍵の部分集合Mをシャッフリングすることによって、それが公開鍵のいずれであ
るかを露出することなく証明することができる。匿名証明書の発行後、証明書サ
ーバは、次の匿名証明書を要求する個人が使用するために、公開鍵のシャッフル
された集合から1つのシャッフルされた公開鍵を除去する。
の公開鍵の1つに関連付けられた秘密鍵をその個人が保持していることを、公開
鍵の部分集合Mをシャッフリングすることによって、それが公開鍵のいずれであ
るかを露出することなく証明することができる。匿名証明書の発行後、証明書サ
ーバは、次の匿名証明書を要求する個人が使用するために、公開鍵のシャッフル
された集合から1つのシャッフルされた公開鍵を除去する。
【０２４６】
「匿名認証および署名」
上記シャッフルプロトコルを基本的に構築することにより、次の問題が解決さ
れれる。
れれる。
【０２４７】
一般的ｋシャッフル問題:Zp,S={X1,….Xk}およびT={Y1,…,Yk}のk要素の2つのシ
ーケンスは公然と知られている。さらに、定数c∈ZqはPにだけ知られているが、
cのコミットメントC=gcはVに知らされている。Pは、πまたは秘密cに関する情報
を露出せずに、すべての1≦i≦kに関して、
ーケンスは公然と知られている。さらに、定数c∈ZqはPにだけ知られているが、
cのコミットメントC=gcはVに知らされている。Pは、πまたは秘密cに関する情報
を露出せずに、すべての1≦i≦kに関して、
【０２４８】
【数６４】
【０２４９】
という特性を有するある種の置換π∈Σkが存在することを、Vに確信させること
が要求される。
が要求される。
【０２５０】
上記シャッフルプロトコルでは、この問題に対する解決法は、まずPおよびVに
よって実行される対話式証明プロトコルとして提示されるが、これはFiat-Shami
rヒューリスティックの標準的な応用例では非対話式である。本発明では、T(S,T
,g,C)によって、結果的に生じる検証の、シャッフラPによって生成される写しを
示す。
よって実行される対話式証明プロトコルとして提示されるが、これはFiat-Shami
rヒューリスティックの標準的な応用例では非対話式である。本発明では、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に等しくなるようセットされる。
ある。 集合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は変換
∈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=Kのすべての公開鍵に同
じ変換(塁乗法)が適用される。すべての検査要件が満たされるまで、写しT(H,H'
,G,C)のそれぞれは記憶しておかなければならないということによって、標準証
明書の元の集合が大きい場合、多量のデータが作成される可能性がある。この問
題は、次の第2の匿名認証プロトコルによって扱われる。
【０２６０】
このプロトコルの形体では、
公開鍵は要素(k,h)∈<g>×<g>の対であり、対応する秘密鍵は単純に秘密指数s
=logkhである。 集合HはPの公開鍵を含まなければならない。これは種々の方法で達成すること
ができる。 1.SおよびPは、Hのこの特性が達成されるまで一連の再試行に関与することがで
きる。 2.または、初期登録において、標準証明書を「ブロック」に割り当てることがで
きる。Pが最初にSに接触したとき、Pは自分のブロック番号がある限り、自己を
特定する。
=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の証明の妥当性をチェックする。
合(その部分集合は、投票者の公開鍵対を含む)の部分集合だけをシャッフルする
。このプロトコルは、前節に記載の要領で、次の変更に進められる。 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の下で各個人により選択することができる。
集合H)は、いずれか一個人が匿名証明書を要求する前に、ある個人またはオーソ
リティによってシャッフルすることができる。すなわち、公開鍵のプールは、上
記匿名認証プロトコルのどちらかが、要求している特定の個人に利用される前に
、十分にランダム化することができる。したがって、公開鍵の小さな部分集合は
、プロトコル2の下で各個人により選択することができる。
【０２６３】
図6を参照すると、匿名証明書分配の第1の変形体を実施するためのルーチン60
0の一例が示されている。ブロック302で暗号パラメータを初期化した後、公開鍵
Hの標準集合がブロック604で提供されるが、これは、登録者または投票者の集合
がそれぞれに(ブロック606に示すように、個々に保持した秘密鍵sに対応する)公
開鍵hを登録して提出した後、登録サーバによって収集することができる。ブロ
ック608では、部分群ジェネレータgがGにセットされる。
0の一例が示されている。ブロック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の下
の選択的ランダム化は、前の初期化の一部として、あるいは後述する匿名証明書
の生成のいかなる中間段階でも実行することができる。
的ランダム化を実行することができる。ブロック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とは異なる)。
明書の単一の要求を示す。これらのステップは、要求している各登録者によって
反復される。ブロック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にデジタル署名する。このル
ーチンは次の登録者の要求の準備ができる。
であることを確認する。これら双方のチェックが通ると、登録サーバは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に類
似している。
体を示す。ルーチン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証明書要
求を生成し、秘密鍵を記憶する。
。代替の実施形態下で、登録サーバは、登録者の公開鍵を含む部分集合だけを取
り出す。ブロック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の残りの部分とほぼ同一である。
。どちらのチェックも通った場合、登録者サーバは、Kをセットし(方程式(18)ま
たは(19)の下で公開鍵対(g'j,h'j)を除去し)、k=k-1をセットする。ルーチン700
の残りの部分は、ルーチン600の残りの部分とほぼ同一である。
【０２７０】
11.結論
当業者ならば、本発明の概念は、インターネット以外の種々の環境で使用する
ことができることが理解されるであろう。例えば、この概念は、電子メール投票
、トランザクション、フォームが処理され記憶される電子メール環境で使用する
ことができる。一般に、ウェブページまたは表示内容(例えば、掲示板)は、HTML
、XMLまたはWAP形式、電子メール形式、または情報を表示するのに適した(文字/
コードベース形式、ビットマップ形式、およびベクトルベース形式を含めて)い
かなる他の形式であってもよい。同様に、インターネットの代わりに、ローカル
エリアネットワーク、ワイドエリアネットワーク、またはポイントツーポイント
のダイヤルアップ接続などの種々の通信チャネルを使用することができる。種々
のトランザクションもまた、クライアント/サーバ環境ではなく、単一コンピュ
ータ環境内で実施することができる。各投票者コンピュータまたはクライアント
コンピュータは、サーバコンピュータまたはシステムと対話するハードウェアま
たはソフトウェアのいかなる組み合わせを含むこともできる。これらのクライア
ントシステムは、テレビジョンベースのシステム、インターネット機器、および
トランザクションを実行することができる種々の他の消費者製品を含むことがで
きる。
ことができることが理解されるであろう。例えば、この概念は、電子メール投票
、トランザクション、フォームが処理され記憶される電子メール環境で使用する
ことができる。一般に、ウェブページまたは表示内容(例えば、掲示板)は、HTML
、XMLまたはWAP形式、電子メール形式、または情報を表示するのに適した(文字/
コードベース形式、ビットマップ形式、およびベクトルベース形式を含めて)い
かなる他の形式であってもよい。同様に、インターネットの代わりに、ローカル
エリアネットワーク、ワイドエリアネットワーク、またはポイントツーポイント
のダイヤルアップ接続などの種々の通信チャネルを使用することができる。種々
のトランザクションもまた、クライアント/サーバ環境ではなく、単一コンピュ
ータ環境内で実施することができる。各投票者コンピュータまたはクライアント
コンピュータは、サーバコンピュータまたはシステムと対話するハードウェアま
たはソフトウェアのいかなる組み合わせを含むこともできる。これらのクライア
ントシステムは、テレビジョンベースのシステム、インターネット機器、および
トランザクションを実行することができる種々の他の消費者製品を含むことがで
きる。
【０２７１】
本発明で一般に使用される「リンク」という用語は、ネットワーク上にサイト
またはノードを有する投票オーソリティの表示内容などの、ネットワーク上の資
源を識別する任意の資源ロケータを示す。一般に、投票者コンピュータ、端末お
よびサーバなどのハードウェアプラットフォームを本明細書では記載しているが
、本発明の態様は、ノードを識別するための対応する資源ロケータを有するネッ
トワーク上のノードにおしなべて適用可能である。
またはノードを有する投票オーソリティの表示内容などの、ネットワーク上の資
源を識別する任意の資源ロケータを示す。一般に、投票者コンピュータ、端末お
よびサーバなどのハードウェアプラットフォームを本明細書では記載しているが
、本発明の態様は、ノードを識別するための対応する資源ロケータを有するネッ
トワーク上のノードにおしなべて適用可能である。
【０２７２】
文脈上明らかに要求されない限り、詳細な説明並びに特許請求の範囲を通して
、「備える」「備えている」などの語句は、排他的意味または網羅的意味とは反
対の、包含的な意味、すなわち「含むが、これに限定されない」という意味に解
釈されるべきである。単数または複数を使用する単語も、それぞれに複数または
単数を含む。さらに、「本発明において」「本発明では」という語句、および類
似の意味の単語も、本願で使用される場合、本願を全体として意味しており、本
願のいかなる特定の部分をも意味しない。
、「備える」「備えている」などの語句は、排他的意味または網羅的意味とは反
対の、包含的な意味、すなわち「含むが、これに限定されない」という意味に解
釈されるべきである。単数または複数を使用する単語も、それぞれに複数または
単数を含む。さらに、「本発明において」「本発明では」という語句、および類
似の意味の単語も、本願で使用される場合、本願を全体として意味しており、本
願のいかなる特定の部分をも意味しない。
【０２７３】
本発明の例示の実施形態についての上記の説明は、本発明を、開示された正確
な形式を網羅し、限定することを目的としていない。本発明の特定の実施形態お
よび実施例を説明する目的で本明細書に記載したが、種々の異なる形態も本発明
の範囲内で可能であることを関連技術の精通者ならば理解するであろう。本発明
の教示するところは、上記の電子投票システムだけでなく他の暗号化の応用例に
も適用することができる。例えば、このプロトコルの応用例には、匿名性と検査
可能性の双方を必要とする電子商取引も含まれる。この実施例は、電子マネーに
よる支払い方式(「電子キャッシュ」)である。
な形式を網羅し、限定することを目的としていない。本発明の特定の実施形態お
よび実施例を説明する目的で本明細書に記載したが、種々の異なる形態も本発明
の範囲内で可能であることを関連技術の精通者ならば理解するであろう。本発明
の教示するところは、上記の電子投票システムだけでなく他の暗号化の応用例に
も適用することができる。例えば、このプロトコルの応用例には、匿名性と検査
可能性の双方を必要とする電子商取引も含まれる。この実施例は、電子マネーに
よる支払い方式(「電子キャッシュ」)である。
【０２７４】
上記の種々の実施形態は、さらなる実施形態を提供するように組み合わせるこ
とができる。上記の参照および米国特許および出願のすべては、参照により本発
明に組み込まれている。本発明の態様は、本発明のさらに別の実施形態を提供す
るために種々の特許および出願のシステム、機能、および概念を利用するように
、必要に応じて変更することができる。
とができる。上記の参照および米国特許および出願のすべては、参照により本発
明に組み込まれている。本発明の態様は、本発明のさらに別の実施形態を提供す
るために種々の特許および出願のシステム、機能、および概念を利用するように
、必要に応じて変更することができる。
【０２７５】
上記の詳細な説明に鑑みて、本発明にはこれらおよび他の変更を加えることが
できる。一般に、特許請求の範囲で使用される用語は、本発明および特許請求の
範囲で開示された特定の実施形態に本発明を限定するものと解釈されるべきでな
く、データの安全性を実現するために特許請求の範囲で動作するすべての暗号化
システムおよび方法を含むものと解釈されるべきである。したがって、本発明は
開示によって限定されるのではなく、本発明の範囲は特許請求の範囲によって完
全に確定されるべきである。
できる。一般に、特許請求の範囲で使用される用語は、本発明および特許請求の
範囲で開示された特定の実施形態に本発明を限定するものと解釈されるべきでな
く、データの安全性を実現するために特許請求の範囲で動作するすべての暗号化
システムおよび方法を含むものと解釈されるべきである。したがって、本発明は
開示によって限定されるのではなく、本発明の範囲は特許請求の範囲によって完
全に確定されるべきである。
【０２７６】
本発明の特定の態様は特許請求の範囲の形式で表現されるが、いかなる数の特
許請求の範囲形式においても本発明の種々の態様が検討される。例えば、本発明
の1つの態様だけがコンピュータ読み取り可能媒体として実施されるように記載
されているが、他の態様も同様にコンピュータ読み取り可能媒体として実施する
ことができる。したがって、本発明の他の態様のためにそのような追加の請求項
の形式を追求するため、本願出願後に追加の請求項を加える権利が留保されてい
る。
許請求の範囲形式においても本発明の種々の態様が検討される。例えば、本発明
の1つの態様だけがコンピュータ読み取り可能媒体として実施されるように記載
されているが、他の態様も同様にコンピュータ読み取り可能媒体として実施する
ことができる。したがって、本発明の他の態様のためにそのような追加の請求項
の形式を追求するため、本願出願後に追加の請求項を加える権利が留保されてい
る。
【図１】
本発明の実施形態を実施するために適切な環境を示すブロック図である。
【図２】
3人の投票者と3回のシャッフルによる1つの簡素な投票に適用された本明細書
に記載のシャッフルプロトコルの簡素な実施を示す概略図である。
に記載のシャッフルプロトコルの簡素な実施を示す概略図である。
【図３】
スケールされる反復対数乗法証明プロトコルを示すフロー図である。
【図４】
シャッフラが暗号指数を知っている簡素なシャッフルプロトコルを示すフロー
図である。
図である。
【図５】
シャッフラが暗号指数を知らない一般的なシャッフルプロトコルを示すフロー
図である。
図である。
【図６】
匿名証明書分配ルーチンを示すフロー図である。
【図７】
図6の匿名証明書分配ルーチンの代替実施形態を示すフロー図である。
─────────────────────────────────────────────────────
フロントページの続き
(31)優先権主張番号 ６０／２６８，５５１
(32)優先日 平成13年２月14日(2001．2．14)
(33)優先権主張国 米国（ＵＳ）
(81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＣＹ，
ＤＥ，ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，Ｉ
Ｔ，ＬＵ，ＭＣ，ＮＬ，ＰＴ，ＳＥ，ＴＲ)，ＯＡ(ＢＦ
，ＢＪ，ＣＦ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＧＷ，
ＭＬ，ＭＲ，ＮＥ，ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＧＨ，Ｇ
Ｍ，ＫＥ，ＬＳ，ＭＷ，ＭＺ，ＳＤ，ＳＬ，ＳＺ，ＴＺ
，ＵＧ，ＺＷ)，ＥＡ(ＡＭ，ＡＺ，ＢＹ，ＫＧ，ＫＺ，
ＭＤ，ＲＵ，ＴＪ，ＴＭ)，ＡＥ，ＡＧ，ＡＬ，ＡＭ，
ＡＴ，ＡＵ，ＡＺ，ＢＡ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，Ｂ
Ｚ，ＣＡ，ＣＨ，ＣＮ，ＣＯ，ＣＲ，ＣＵ，ＣＺ，ＤＥ
，ＤＫ，ＤＭ，ＤＺ，ＥＥ，ＥＳ，ＦＩ，ＧＢ，ＧＤ，
ＧＥ，ＧＨ，ＧＭ，ＨＲ，ＨＵ，ＩＤ，ＩＬ，ＩＮ，Ｉ
Ｓ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ，ＫＺ，ＬＣ，ＬＫ
，ＬＲ，ＬＳ，ＬＴ，ＬＵ，ＬＶ，ＭＡ，ＭＤ，ＭＧ，
ＭＫ，ＭＮ，ＭＷ，ＭＸ，ＭＺ，ＮＯ，ＮＺ，ＰＬ，Ｐ
Ｔ，ＲＯ，ＲＵ，ＳＤ，ＳＥ，ＳＧ，ＳＩ，ＳＫ，ＳＬ
，ＴＪ，ＴＭ，ＴＲ，ＴＴ，ＴＺ，ＵＡ，ＵＧ，ＵＳ，
ＵＺ，ＶＮ，ＹＵ，ＺＡ，ＺＷ
Claims (35)
- 【請求項１】 コンピュータ化されたネットワークで使用するための電子投
票システムにおいて、 前記コンピュータ化されたネットワークに結合された複数の投票用コンピュー
タであって、 各投票用コンピュータは、電子暗号化された投票を実現し、 各電子投票は、基礎となる群Zpまたは楕円曲線を用いて離散対数非対称暗号化
プロセスの下に暗号化される複数の投票用コンピュータと、 前記コンピュータ化されたネットワークに結合された少なくとも前記第1、第2
および第3のオーソリティコンピュータであって、 第1のオーソリティコンピュータは、複数の投票用コンピュータから受け取っ
た電子投票のそれぞれの集合に対応する一連の電子投票を受け取り、かつ、該一
連の電子投票を匿名でシャッフルし、第1のシャッフルされた一連の投票を生成
するために、少なくとも第1の秘密鍵を使用して、秘密のワンウェイ暗号変換を
適用するように構成されており、 前記第1のオーソリティコンピュータだけが、前記第1の一連のシャッフルされ
た投票と前記一連の電子投票の間の対応関係を知っており、および 前記第1のオーソリティコンピュータは、スケールされる反復対数乗法証明に
基づき、前記第1の一連のシャッフルされた投票の正確さの第1のリニアサイズの
、非対話式証明を提供するようにさらに構成され、 第2のオーソリティコンピュータは、前記第1の一連のシャッフルされた投票を
受け取り、かつ、前記第1の一連のシャッフルされた投票を匿名でシャッフルし
て第2の一連のシャッフルされた投票を生成するために少なくとも第2の秘密鍵を
使用して暗号変換を適用するように構成されており、 前記第2のオーソリティコンピュータだけが、前記第1の一連のシャッフルされ
た投票と前記第2の一連のシャッフルされた投票との間の対応関係を知っており
、および 前記第2のオーソリティコンピュータは、スケールされる反復対数乗法証明に
基づいて、前記第2の一連のシャッフルされた投票の正確さの、第2のリニアサイ
ズの非対話式証明を提供するようにさらに構成されており、 第3のオーソリティコンピュータは、前記第2の一連のシャッフルされた投票を
受け取り、前記第2の一連のシャッフルされた投票を匿名でシャッフルして第3の
一連のシャッフルされた投票を生成するために少なくとも第3の秘密鍵を使用し
て暗号変換を適用するように構成されており、 前記第3のオーソリティコンピュータだけが、前記第3の一連のシャッフルされ
た投票と前記第2の一連のシャッフルされた投票との間の対応関係を知っており
、および 前記第3のオーソリティコンピュータは、スケールされる反復対数乗法証明に
基づいて、前記第3の一連のシャッフルされた投票の正確さの第3のリニアサイズ
の非対話式証明を提供するようにさらに構成された少なくとも前記第1、第2およ
び第3のオーソリティコンピュータと、および 前記第1、第2および第3のオーソリティコンピュータと対話することなく、前
記第1、第2および第3のオーソリティコンピュータから前記正確さの証明を受け
取り、前記シャッフルされた投票の正確さを検証するように構成されたコンピュ
ータ化されたネットワークに結合された検証コンピュータと を備えたことを特徴とするシステム。 - 【請求項２】 前記複数の投票用コンピュータから複数の電子投票を受け取
り、前記複数の電子投票のそれぞれの妥当性証明を検証し、前記複数の電子投票
から前記投票の暗号化された投票集計を形成し、前記暗号化された投票集計を前
記第1、第2および第3のオーソリティコンピュータに送信して、前記第1、第2お
よび第3のオーソリティコンピュータのうち少なくとも2つから生成された投票解
読の分担を受け取り、かつ暗号解読された投票集計を計算するように構成された
コンピュータ化されたネットワークに結合されたサーバコンピュータシステムと
、 コンピュータ化されたネットワークに結合され、前記サーバコンピュータシス
テムに前記複数の電子暗号化された投票の一部を提供する少なくとも1つの投票
所コンピュータと をさらに備えたことを特徴とする請求項１に記載のシステム。 - 【請求項３】 前記第1、第2および第3のオーソリティコンピュータは、前
記投票の前記第1、第2および第3のシャッフルにそれぞれChaum-Pedersen証明を
提供するように構成されており、前記第1、第2および第3のオーソリティコンピ
ュータの各々は、初期チャレンジの一続きを生成し、少なくとも1つの検証コン
ピュータから1つのチャレンジを受け取り、初期チャレンジと受け取ったチャレ
ンジの累乗とに基づいて暗号変換を生成することを特徴とする請求項１に記載の
システム。 - 【請求項４】 前記コンピュータ化されたネットワークは、ワールドワイド
ウェブを含み、 前記複数の投票用コンピュータの各々と、前記第1、第2および第3のオーソリ
ティコンピュータとは、ウェブブラウザプログラムを含むこと を特徴とする請求項１に記載のシステム。 - 【請求項５】 前記複数の投票用コンピュータは、パームサイズコンピュー
タ、携帯電話、ウェアラブルコンピュータ、対話式テレビジョン端末またはイン
ターネット機器のうち少なくとも1つを含むことを特徴とする請求項１に記載の
システム。 - 【請求項６】 要素のシーケンスを受け取るためのコンピュータシステムに
おいて、 コンピュータネットワークに結合され、 個々のデータファイルを表す電子データ要素のシーケンスを受け取り、 少なくとも第1の秘密鍵を用いて暗号変換を適用し、前記電子データ要素のシ
ーケンスを匿名で置換し、および第1の電子データ要素のシャッフルされたシー
ケンスを生成するように構成されたサーバコンピュータを備え、 該サーバコンピュータは、前記第1の電子データ要素のシャッフルされたシー
ケンスと前記電子データ要素のシーケンスとの間の対応関係を知り、および スケールされる反復対数乗法証明に基づいて、前記第1の電子データ要素のシ
ャッフルされたシーケンスの正確さの第1のリニアサイズ証明を生成することを
特徴とするシステム。 - 【請求項７】 前記受け取った電子データ要素のシーケンスは、前記サーバ
コンピュータに知られていない鍵を使用し、Zpまたは楕円曲線の群を用いて暗号
化され、および 前記サーバコンピュータは、ベリファイアコンピュータから一連のランダムに
生成された値eiを受け取り、 受け取った一連の値eiと秘密裏に生成された値 【数１】 を使用する、秘密のワンウェイ暗号変換に基づいて一連の値Uiを秘密裏に生成し
、 前記一連の値Uiと秘密の値dに基づいて前記第1のシャッフルされた要素のシー
ケンスを生成する前記電子データ要素のシーケンスを置換し、 暗号変換を前記ベリファイアコンピュータに対し露出することなく、前記第1
のシャッフルされた要素のシーケンスを生成するため、前記サーバコンピュータ
が、前記電子データ要素のシーケンスを前記暗号変換がどのようにして置換した
かにアクセスするノリッジの証明として、前暗号変換に基づく前記値Uiと一連の
証明値とを提供するように、さらに構成されていることを特徴とする請求項６に
記載のシステム。 - 【請求項８】 前記サーバコンピュータは、 複数の公開鍵を、各々が前記複数の公開鍵の1つに対応する秘密鍵を有する対
応する複数の個人から受け取り、 1つの秘密鍵を有する前記複数の個人の1人から証明書の要求を受け取り、 前記複数の公開鍵のうち少なくとも1つの部分集合を前記要求している個人に
提供し、 前記複数の公開鍵のシャッフル、および、スケールされる反復対数乗法証明と
前記1つの秘密鍵とに対応し、前記1つの秘密鍵を露出することなく1人の個人が
前記1つの秘密鍵のノリッジを有するという証明を提供する値に基づいて前記シ
ャッフルされた公開鍵の正確さのリニアサイズ証明を受け取り、 前記正確さの証明をチェックし、 前記値が、前記1つの秘密鍵に対応する前記公開鍵の1つに数学的に関係するこ
とをチェックし、 前記1人の個人に証明書を発行し、および 前記複数の公開鍵を前記1つの公開鍵だけ減らすようにさらに構成されたこと
を特徴とする請求項６に記載のシステム。 - 【請求項９】 前記電子要素のシーケンスは、公開鍵であり、および 前記サーバは、もし、個人からの要求に応じて、前記公開鍵の1つに一意かつ
数学的に関係する値を前記個人が有するかどうかをチェックするようにさらに構
成されるなら、および 有する場合は前記1人の個人に証明書を発行することを特徴とする請求項６に
記載のシステム。 - 【請求項１０】 コンピュータで実施される方法であって、 複数の公開鍵を、それぞれが前記複数の公開鍵の1つに対応する秘密鍵を有す
る、対応する複数の個人から受け取ることと、 1つの秘密鍵を有する前記複数の個人の1人から証明書の要求を受け取ることと
、 前記複数の公開鍵のうち少なくとも1つの部分集合を前記要求している個人に
提供することと、 前記複数の公開鍵のシャッフルおよびスケールされる反復対数乗法証明と前記
1つの秘密鍵とに対応する値に基づいて前記シャッフルされた公開鍵の正確さの
リニアサイズの証明を受け取り、前記値が、前記1つの秘密鍵を露出することな
く前記1人の個人が前記1つの秘密鍵のノリッジを有する証明を提供することと、 前記正確さの証明をチェックすることと、 前記値が、前記1つの秘密鍵に対応する前記公開鍵の1つに数学的に関係するこ
とをチェックすることと、 前記1人の個人に証明書を発行することと、 前記複数の公開鍵を前記1つの公開鍵だけ減らすことと を備えたことを特徴とする方法。 - 【請求項１１】 前記方法は、値Gを、Zpまたは楕円曲線群からの部分群オ
ペレータgにセットすることをさらに含み、 前記複数の公開鍵のうち少なくとも1つの部分集合を提供することは、その時
点の現行公開鍵Hのすべてを提供することを含むことを特徴とする請求項１０に
記載の方法。 - 【請求項１２】 前記複数の公開鍵のうち少なくとも1つの部分集合を提供
することは、複数の公開鍵対のうち少なくとも1つの部分集合を提供することを
含み、 前記複数の公開鍵のシャッフルを受け取ることは、前記1人の個人によって選
択された前記複数の公開鍵対の真部分集合のシャッフルを受け取ることを含むこ
とを特徴とする請求項１０に記載の方法。 - 【請求項１３】 前記複数の公開鍵H'のシャッフルされた集合を生成するた
め、複数のオーソリティの各々から、前記複数の公開鍵のうち少なくとも1つの
部分集合上で実行された秘密暗号化シャッフル操作に基づいて前記複数の公開鍵
のシャッフルされた集合H'を順次受け取ることと、 複数のオーソリティの各々から、前記暗号化シャッフル操作の検証の写しを順
次受け取ることと、 該検証の写しに基づいて前記暗号化シャッフル操作の正確さを検証し、検証さ
れると、Hに対する前記複数の公開鍵のうち少なくとも1つの部分集合をH'にセッ
トすることと をさらに備えたことを特徴とする請求項１０に記載の方法。 - 【請求項１４】 前記複数の公開鍵のうち少なくとも一部を受け取った後の
ある時点において、その時点で受け取った前記複数の公開鍵のうち少なくとも1
つの部分集合を、前記複数の公開鍵の受け取られたシャッフルされた集合にセッ
トすることをさらに備え、 前記複数の公開鍵の前記シャッフルされた集合が第三者から受け取られていた
ことを特徴とする請求項１０に記載の方法。 - 【請求項１５】 前記複数の個人の前記1人から発行された証明書を受け取
ることと、および 前記1人の個人に電子投票を提供することと をさらに備えたことを特徴とする請求項１０に記載の方法。 - 【請求項１６】 前記証明書を発行することは、公開鍵基盤(「PKI」)証明
書を生成するために、前記受け取った要求にデジタル署名することを含むことを
特徴とする請求項１０に記載の方法。 - 【請求項１７】 前記複数の個人のうち少なくとも一部から発行された証明
書を受け取り、それに応答して初期電子投票を提供することと、および 前記複数の個人のうち少なくとも一部から暗号化されていない投票された票を
受け取ることと をさらに備えたことを特徴とする請求項１０に記載の方法。 - 【請求項１８】 証明者コンピュータとベリファイアコンピュータとの間に
おけるコンピュータで実施される暗号化方法であって、 群Gから選択される部分群ジェネレータgを選択することと、 該部分群ジェネレータgに基づいて証明者鍵cとコミットメント値Cとを秘密裏
に生成することと、 第1および第2の要素のシーケンスの間に暗号化関係を秘密裏に確立することと
、 前記ベリファイアコンピュータに前記コミットメントCと、前記第1と第2の要
素のシーケンスとを提供するが、前記暗号化関係は提供しないことと、 前記暗号化関係に基づいて一連の証明値を計算することと、 前記ベリファイアコンピュータに前記暗号化関係を露出することなく、前記証
明者コンピュータが前記暗号化関係にアクセスするノリッジの非対話式証明とし
て、前記一連の計算された証明値を前記ベリファイアコンピュータに提供するこ
とと を備えたことを特徴とする方法。 - 【請求項１９】 少なくとも前記第2の要素のシーケンスは、各々がZpまた
は楕円曲線群を使用して暗号化された票のシーケンスであり、 前記第1と第2の要素のシーケンスは、それぞれ (X1,…,Xk)と(Y1,…,Yk) であり、 前記第1と第2の要素のシーケンスは、 【数２】 として、暗号化関係 【数３】 を有し、および 前記一連の証明値を計算して提供することは、各0≦i≦kに対してランダムri
を生成し、 【数４】 各1≦i≦kに対する、 【数５】 に基づいて、前記ベリファイアコンピュータに対し (Ri-1,Xi,Ri,Wi)と(Yi,C,Wi,Zi) の形式で与えられたチョム−ペダーセン証明を提供することを含むことを特徴と
する請求項１８に記載の方法。 - 【請求項２０】 暗号変換に基づいて前記第2の要素のシーケンスを生成す
るために前記第1の要素のシーケンスを置換することと、 前記ベリファイアコンピュータからランダムに生成された値tを受け取ること
と、 前記受け取った値tと前記部分群ジェネレータに基づいて値Tを秘密裏に生成し
、かつ、前記受け取った値tと前記証明者鍵cに基づいて値Sを秘密裏に生成する
こととをさらに備え、 前記一連の証明値を計算して前記ベリファイアコンピュータに提供することは
、前記ベリファイアコンピュータに前記暗号変換を露出することなく、前記第2
の要素のシーケンスを生成するため、前記暗号変換が前記第1の要素のシーケン
スをどのように置換したかという、前記証明者コンピュータがアクセスしたノリ
ッジの証明として、前記暗号変換に基づく一連の値を提供することを含むことを
特徴とする請求項１８に記載の方法。 - 【請求項２１】 【数６】 の形式で、暗号変換に基づき前記第2の要素のシーケンスを生成するために前記
第1の要素のシーケンスを置換することと、 前記ベリファイアコンピュータからランダムに生成された値tを受け取ること
と、 前記部分群ジェネレータgを前記受け取った値t乗することに基づいて値Tを秘
密裏に生成し、かつ、前記値Tを前記証明者鍵c乗することに基づいて値Sを秘密
裏に生成することとをさらに備え、 前記一連の証明値を計算して前記ベリファイアコンピュータに提供することは
、前記ベリファイアコンピュータに前記暗号変換を露出することなく、前記第2
の要素のシーケンスを提供するために、前記暗号変換が前記第1の要素のシーケ
ンスをどのように置換したかという、前記証明者コンピュータがアクセスしたノ
リッジの証明として、前記暗号変換に基づく一連の値を、 Ui=Xi/T Vi=Yi/S の形式で提供することを含むことを特徴とする請求項１８に記載の方法。 - 【請求項２２】 前記証明者コンピュータに知られていない方法で以前に置
換された要素の集合として前記第1の要素のシーケンスを受け取ることと、 前記ベリファイアコンピュータから一連のランダムに生成された値eiを受け取
ることと、 前記受け取った一連の値eiと秘密裏に生成された値 【数７】 を利用する秘密暗号変換に基づいて一連の値Uiを秘密裏に生成することと、 前記一連の値Uiと秘密値dに基づいて前記第１の要素のシーケンスに関して前
記第2の要素のシーケンスを置換することとをさらに備え、 前記一連の証明値を計算して前記ベリファイアコンピュータに提供することは
、結果的に生じる値Uiを提供することと、前記ベリファイアコンピュータに前記
暗号変換を露出することなく、前記第2の要素のシーケンスを提供するために、
前記暗号変換が前記第1の要素のシーケンスをどのように置換したかという、前
記証明者コンピュータがアクセスしたノリッジの証明として、前記暗号変換に基
づく一連の証明値を提供することを含むことを特徴とする請求項１８に記載の方
法。 - 【請求項２３】 前記証明者コンピュータに知られていない方法で以前に置
換された要素の集合として前記第１の要素のシーケンスを受け取ることと、 前記ベリファイアコンピュータから一連のランダムに生成された値eiを受け取
ることと、 【数８】 の形式で秘密暗号変換に基づいて一連の値Uiを秘密裏に生成することと、 次の演算 【数９】 に基づいて、前記一連の値Uiと秘密値dとに基づいて前記第１の要素のシーケン
スに関して、前記第2の要素のシーケンスを置換することをさらに備え、 前記一連の証明値を計算して前記ベリファイアに提供することは、前記結果的
に生じた値Ui 【数１０】 を提供することと、1≦i>kに対して (g,Vi,Xi,Ai)と(g,Ui,Yi,Bi) の形式の一連の証明チョム−ペダーセンと、(D,A,C,B)に対するチョム−ペダー
セン証明とを、前記暗号変換を前記ベリファイアコンピュータに露出することな
く、前記第2の要素のシーケンスを生成するために、前記暗号変換がどのように
して前記第１の要素のシーケンスを置換したかという、前記証明者コンピュータ
がアクセスしたノリッジの証明として提供することとを含むことを特徴とする請
求項１８に記載の方法。 - 【請求項２４】 前記第１の要素のシーケンスを受け取ること、一連のラン
ダムに生成された値を受け取ること、一連の値を秘密裏に生成すること、および
前記第１の要素のシーケンスのl(エル)タプルの要素に対して前記第2の要素のシ
ーケンスを置換することを反復することをさらに備えたことを特徴とする請求項
２３に記載の方法。 - 【請求項２５】 前記第１の要素のシーケンスを受け取ることは、各々の識
別する要素が個人に対応している、識別する要素の集合の部分集合を受け取るこ
とを含み、および前記方法は、 前記ベリファイアコンピュータが前記一連の証明を検証した場合に匿名証明書
を受け取ることをさらに備えたことを特徴とする請求項２２に記載の方法。 - 【請求項２６】 前記群GがZpであることを特徴とする請求項１８に記載の
方法。 - 【請求項２７】 前記群Gが楕円曲線群であることを特徴とする請求項１８
に記載の方法。 - 【請求項２８】 コンピュータによって実施されたときに電子データ要素の
シーケンスのシャッフリングを実行する命令を提供するコンテンツであって、 前記電子データ要素のシーケンスを受け取る命令と、 前記電子データ要素のシーケンスを匿名で置換するために、少なくとも第1の
秘密鍵を使用して秘密のワンウェイ暗号変換を適用して、電子データ要素の第1
のシャッフルされたシーケンスを生成する命令と、および スケールされる反復対数乗法証明に基づいて、前記電子データ要素の前記第1
のシャッフルされたシーケンスに対する正確さの、第1のリニアサイズの非対話
式証明を生成する命令と を備えたコンテンツを有することを特徴とするコンピュータ読み取り可能媒体
。 - 【請求項２９】 前記受け取った電子データ要素のシーケンスは、モジュラ
ス整数値p(Zp)を有する整数の環である基礎となる数学的群によって暗号化され
ることを特徴とする請求項２８に記載のコンピュータ読み取り可能媒体。 - 【請求項３０】 前記コンピュータ読み取り可能媒体は、前記電子データ要
素のシーケンスと前記内容を受け取るコンピュータネットワーク内の論理ノード
であることを特徴とする請求項２８に記載のコンピュータ読み取り可能媒体。 - 【請求項３１】 前記コンピュータ読み取り可能媒体は、コンピュータ読み
取り可能ディスクであることを特徴とする請求項２８に記載のコンピュータ読み
取り可能媒体。 - 【請求項３２】 前記コンピュータ読み取り可能媒体は、前記コンテンツを
含む生成されたデータ信号を伝送するデータ伝送媒体であることを特徴とする請
求項２８に記載のコンピュータ読み取り可能媒体。 - 【請求項３３】 前記コンピュータ読み取り可能媒体は、コンピュータシス
テムのメモリであることを特徴とする請求項２８に記載のコンピュータ読み取り
可能媒体。 - 【請求項３４】 前記コンピュータ読み取り可能媒体は、投票オーソリティ
サーバコンピュータへのインターネット接続リンクであることを特徴とする請求
項２８に記載のコンピュータ読み取り可能媒体。 - 【請求項３５】 暗号化方法において、コンピュータによって使用されるた
めに送信された信号であって、 ワンウェイ暗号変換は、前記電子データ要素のシャッフルされたシーケンスを
生成するために、電子データ要素の入力シーケンスを匿名で、少なくとも1つの
第1の秘密鍵を用いて置換した、個々のデータファイルを表している電子データ
要素のシャッフルされたシーケンスと、および スケールされる反復対数乗数証明に基づいて前記電子データ要素のシャッフル
されたシーケンスの正確さのリニアサイズ証明と を備えたことを特徴とする信号。
Applications Claiming Priority (7)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US19178500P | 2000-03-24 | 2000-03-24 | |
| US60/191,785 | 2000-03-24 | ||
| US25237600P | 2000-11-21 | 2000-11-21 | |
| US60/252,376 | 2000-11-21 | ||
| US26855101P | 2001-02-14 | 2001-02-14 | |
| US60/268,551 | 2001-02-14 | ||
| PCT/US2001/009550 WO2001073694A2 (en) | 2000-03-24 | 2001-03-24 | Verifiable, secret shuffles of encrypted data, such as elgamal encrypted data for secure multi-authority elections |
Related Child Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2006011456A Division JP2006115550A (ja) | 2000-03-24 | 2006-01-19 | 安全な複数オーソリティ選挙のためのエルガマル暗号化データのように暗号化されたデータの検証可能な秘密シャッフル |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP2003529256A true JP2003529256A (ja) | 2003-09-30 |
Family
ID=27392950
Family Applications (2)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2001571337A Pending JP2003529256A (ja) | 2000-03-24 | 2001-03-24 | 安全な複数オーソリティ選挙のためのエルガマル暗号化データのように暗号化されたデータの検証可能な秘密シャッフル |
| JP2006011456A Pending JP2006115550A (ja) | 2000-03-24 | 2006-01-19 | 安全な複数オーソリティ選挙のためのエルガマル暗号化データのように暗号化されたデータの検証可能な秘密シャッフル |
Family Applications After (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2006011456A Pending JP2006115550A (ja) | 2000-03-24 | 2006-01-19 | 安全な複数オーソリティ選挙のためのエルガマル暗号化データのように暗号化されたデータの検証可能な秘密シャッフル |
Country Status (10)
| Country | Link |
|---|---|
| US (1) | US6950948B2 (ja) |
| EP (1) | EP1302020B1 (ja) |
| JP (2) | JP2003529256A (ja) |
| AT (1) | ATE309655T1 (ja) |
| AU (1) | AU2001250976A1 (ja) |
| CA (1) | CA2404161C (ja) |
| DE (1) | DE60114833T2 (ja) |
| DK (1) | DK1302020T3 (ja) |
| ES (1) | ES2251475T3 (ja) |
| WO (1) | WO2001073694A2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2007318745A (ja) * | 2006-04-27 | 2007-12-06 | Matsushita Electric Ind Co Ltd | コンテンツ配信システム |
Families Citing this family (103)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6676127B2 (en) | 1997-03-13 | 2004-01-13 | Shuffle Master, Inc. | Collating and sorting apparatus |
| US6254096B1 (en) | 1998-04-15 | 2001-07-03 | Shuffle Master, Inc. | Device and method for continuously shuffling cards |
| US6655684B2 (en) | 1998-04-15 | 2003-12-02 | Shuffle Master, Inc. | Device and method for forming and delivering hands from randomly arranged decks of playing cards |
| JP4181724B2 (ja) * | 2000-03-03 | 2008-11-19 | 日本電気株式会社 | 証明付再暗号シャッフル方法と装置、再暗号シャッフル検証方法と装置、入力文列生成方法と装置及び記録媒体 |
| US8590896B2 (en) | 2000-04-12 | 2013-11-26 | Shuffle Master Gmbh & Co Kg | Card-handling devices and systems |
| EP1348187A4 (en) * | 2000-11-27 | 2007-03-14 | Bruce Hasbrouck Dickson Reeves | METHOD FOR COLLECTING AND COLLAGING DATA |
| JP3788246B2 (ja) | 2001-02-13 | 2006-06-21 | 日本電気株式会社 | 匿名復号システム及び匿名復号方法 |
| US20020147904A1 (en) * | 2001-04-10 | 2002-10-10 | Moritaka Nakamura | Electronic notarization on net system |
| KR20030094331A (ko) * | 2001-04-23 | 2003-12-11 | 인터내셔널 비지네스 머신즈 코포레이션 | 양도할 수 없는 익명의 디지털 수령 증명 |
| JP3901471B2 (ja) * | 2001-05-18 | 2007-04-04 | 日本電気株式会社 | 証明付シャッフル復号システムと証明付シャッフル復号方法、シャッフル復号検証方法 |
| US20030023478A1 (en) * | 2001-07-26 | 2003-01-30 | Piccionelli Gregory A. | Electronic initiative petition |
| US7234059B1 (en) * | 2001-08-09 | 2007-06-19 | Sandia Corporation | Anonymous authenticated communications |
| US20030046144A1 (en) * | 2001-08-28 | 2003-03-06 | International Business Machines Corporation | System and method for anonymous message forwarding and anonymous voting |
| US20030055719A1 (en) * | 2001-09-20 | 2003-03-20 | Faigle Christopher T. | Remote participation and voting in a meeting |
| US7753373B2 (en) | 2001-09-28 | 2010-07-13 | Shuffle Master, Inc. | Multiple mode card shuffler and card reading device |
| US8616552B2 (en) | 2001-09-28 | 2013-12-31 | Shfl Entertainment, Inc. | Methods and apparatuses for an automatic card handling device and communication networks including same |
| US8337296B2 (en) | 2001-09-28 | 2012-12-25 | SHFL entertaiment, Inc. | Method and apparatus for using upstream communication in a card shuffler |
| US8011661B2 (en) | 2001-09-28 | 2011-09-06 | Shuffle Master, Inc. | Shuffler with shuffling completion indicator |
| US7677565B2 (en) | 2001-09-28 | 2010-03-16 | Shuffle Master, Inc | Card shuffler with card rank and value reading capability |
| AU2002337945A1 (en) * | 2001-12-31 | 2003-07-30 | Voting Technologies International, Llc | Computerized electronic voting system |
| US6886829B2 (en) | 2002-02-08 | 2005-05-03 | Vendingdata Corporation | Image capturing card shuffler |
| US20030221131A1 (en) * | 2002-03-08 | 2003-11-27 | Toshifumi Mori | Data processing device |
| US6951303B2 (en) | 2002-04-01 | 2005-10-04 | Petersen Steven D | Combination electronic and paper ballot voting system |
| KR20040099429A (ko) * | 2002-04-12 | 2004-11-26 | 톰슨 라이센싱 에스.에이. | 데이터 송신기의 익명 인증을 위한 방법 |
| US7840806B2 (en) * | 2002-10-16 | 2010-11-23 | Enterprise Information Management, Inc. | System and method of non-centralized zero knowledge authentication for a computer network |
| US8239917B2 (en) * | 2002-10-16 | 2012-08-07 | Enterprise Information Management, Inc. | Systems and methods for enterprise security with collaborative peer to peer architecture |
| AU2003220132A1 (en) * | 2002-10-22 | 2004-05-13 | Voting Technologies International, Llc | Computerized electronic voting system |
| FR2847401A1 (fr) * | 2002-11-14 | 2004-05-21 | France Telecom | Procede d'acces a un service avec authentification rapide et anonymat revocable et systeme d'ouverture et de maintien de session |
| US7305711B2 (en) * | 2002-12-10 | 2007-12-04 | Intel Corporation | Public key media key block |
| WO2004109553A2 (en) * | 2003-06-04 | 2004-12-16 | Matsushita Electric Industrial Co., Ltd. | Media inventory information presentation system, management device, and terminal device |
| WO2005071881A1 (ja) * | 2004-01-22 | 2005-08-04 | Nec Corporation | ミックスネットシステム |
| JP4835831B2 (ja) * | 2004-01-26 | 2011-12-14 | 日本電気株式会社 | 多数の入力から関数を計算する方法および装置 |
| US7647498B2 (en) * | 2004-04-30 | 2010-01-12 | Research In Motion Limited | Device authentication |
| EP1756767A2 (en) * | 2004-06-07 | 2007-02-28 | Dategrity Corporation | Cryptographic systems and methods, including practical high certainty intent verification, such as for encrypted votes in an electronic election |
| ATE429747T1 (de) * | 2004-06-30 | 2009-05-15 | France Telecom | Elektronisches wahlverfahren und -system in einem hochsicherheitskommunikationsnetz |
| US20060066048A1 (en) | 2004-09-14 | 2006-03-30 | Shuffle Master, Inc. | Magnetic jam detection in a card shuffler |
| GB2419000A (en) * | 2004-10-06 | 2006-04-12 | Hewlett Packard Development Co | Proving relationships between data |
| EP1858194A4 (en) * | 2005-02-28 | 2013-10-30 | Nec Corp | SHUFFLE DECLARATION VALIDITY VERIFICATION DEVICE AND METHODS, SHUFFLE DECISION VALIDATION DEVICE AND METHOD, PROGRAM AND RECORDING MEDIUM |
| JP4771053B2 (ja) * | 2005-05-27 | 2011-09-14 | 日本電気株式会社 | 統合シャッフル正当性証明装置、証明統合装置、統合シャッフル正当性検証装置及びミックスネットシステム |
| US7764836B2 (en) | 2005-06-13 | 2010-07-27 | Shuffle Master, Inc. | Card shuffler with card rank and value reading capability using CMOS sensor |
| US7818570B2 (en) * | 2005-10-31 | 2010-10-19 | Ntt Docomo, Inc. | Exclusive set system constructions including, but not limited to, applications to broadcast encryption and certificate revocation |
| US7499552B2 (en) | 2006-01-11 | 2009-03-03 | International Business Machines Corporation | Cipher method and system for verifying a decryption of an encrypted user data key |
| US7556266B2 (en) | 2006-03-24 | 2009-07-07 | Shuffle Master Gmbh & Co Kg | Card shuffler with gravity feed system for playing cards |
| US7597258B2 (en) * | 2006-04-21 | 2009-10-06 | Cccomplete, Inc. | Confidential electronic election system |
| US8353513B2 (en) | 2006-05-31 | 2013-01-15 | Shfl Entertainment, Inc. | Card weight for gravity feed input for playing card shuffler |
| US8579289B2 (en) | 2006-05-31 | 2013-11-12 | Shfl Entertainment, Inc. | Automatic system and methods for accurate card handling |
| US8342525B2 (en) | 2006-07-05 | 2013-01-01 | Shfl Entertainment, Inc. | Card shuffler with adjacent card infeed and card output compartments |
| US8070574B2 (en) | 2007-06-06 | 2011-12-06 | Shuffle Master, Inc. | Apparatus, system, method, and computer-readable medium for casino card handling with multiple hand recall feature |
| US8919775B2 (en) | 2006-11-10 | 2014-12-30 | Bally Gaming, Inc. | System for billing usage of an automatic card handling device |
| US7779041B2 (en) * | 2007-05-02 | 2010-08-17 | Sap Ag | Anonymizing infocube data |
| DE102008006840A1 (de) * | 2008-01-30 | 2009-08-13 | Continental Automotive Gmbh | Datenübertragungsverfahren und Tachographensystem |
| US8967621B2 (en) | 2009-04-07 | 2015-03-03 | Bally Gaming, Inc. | Card shuffling apparatuses and related methods |
| US7988152B2 (en) | 2009-04-07 | 2011-08-02 | Shuffle Master, Inc. | Playing card shuffler |
| US8230231B2 (en) * | 2009-04-14 | 2012-07-24 | Microsoft Corporation | One time password key ring for mobile computing device |
| US8583932B2 (en) * | 2009-05-29 | 2013-11-12 | Nec Corporation | Signature device, signature verification device, anonymous authetication system, signing method, signature authentication method, and programs therefor |
| US20120022919A1 (en) * | 2009-09-18 | 2012-01-26 | Hewlett-Packard Development Company, L.P. | Privacy Ensured Polling |
| US8862879B2 (en) * | 2009-10-13 | 2014-10-14 | Sergio Demian LERNER | Method and apparatus for efficient and secure creating, transferring, and revealing of messages over a network |
| WO2011047085A2 (en) * | 2009-10-13 | 2011-04-21 | Certimix, Inc. | Method and apparatus for efficient and secure creating transferring, and revealing of messages over a network |
| US8800993B2 (en) | 2010-10-14 | 2014-08-12 | Shuffle Master Gmbh & Co Kg | Card handling systems, devices for use in card handling systems and related methods |
| US8484195B2 (en) * | 2011-05-11 | 2013-07-09 | Yottavote, Inc. | Anonymous referendum system and method |
| US20120290369A1 (en) * | 2011-05-11 | 2012-11-15 | Jesus Acosta-Cazaubon | Referendum enhanced subscription based application system |
| US9731190B2 (en) | 2011-07-29 | 2017-08-15 | Bally Gaming, Inc. | Method and apparatus for shuffling and handling cards |
| US8485527B2 (en) | 2011-07-29 | 2013-07-16 | Savant Shuffler LLC | Card shuffler |
| US8960674B2 (en) | 2012-07-27 | 2015-02-24 | Bally Gaming, Inc. | Batch card shuffling apparatuses including multi-card storage compartments, and related methods |
| US9511274B2 (en) | 2012-09-28 | 2016-12-06 | Bally Gaming Inc. | Methods for automatically generating a card deck library and master images for a deck of cards, and a related card processing apparatus |
| US9378766B2 (en) | 2012-09-28 | 2016-06-28 | Bally Gaming, Inc. | Card recognition system, card handling device, and method for tuning a card handling device |
| SG10201706403RA (en) | 2014-04-11 | 2017-09-28 | Bally Gaming Inc | Method and apparatus for shuffling and handling cards |
| US9474957B2 (en) | 2014-05-15 | 2016-10-25 | Bally Gaming, Inc. | Playing card handling devices, systems, and methods for verifying sets of cards |
| US20190213820A1 (en) * | 2014-07-02 | 2019-07-11 | OSET Foundation | Secure balloting and election system |
| KR101599144B1 (ko) * | 2014-07-23 | 2016-03-02 | 삼성에스디에스 주식회사 | 키 생성 장치 및 방법 |
| USD764599S1 (en) | 2014-08-01 | 2016-08-23 | Bally Gaming, Inc. | Card shuffler device |
| US9566501B2 (en) | 2014-08-01 | 2017-02-14 | Bally Gaming, Inc. | Hand-forming card shuffling apparatuses including multi-card storage compartments, and related methods |
| US9504905B2 (en) | 2014-09-19 | 2016-11-29 | Bally Gaming, Inc. | Card shuffling device and calibration method |
| US10333696B2 (en) | 2015-01-12 | 2019-06-25 | X-Prime, Inc. | Systems and methods for implementing an efficient, scalable homomorphic transformation of encrypted data with minimal data expansion and improved processing efficiency |
| JP5951094B1 (ja) * | 2015-09-07 | 2016-07-13 | ヤフー株式会社 | 生成装置、端末装置、生成方法、生成プログラム及び認証処理システム |
| US9993719B2 (en) | 2015-12-04 | 2018-06-12 | Shuffle Master Gmbh & Co Kg | Card handling devices and related assemblies and components |
| US9929860B1 (en) * | 2015-12-30 | 2018-03-27 | Emc Corporation | Methods and apparatus for generalized password-based secret sharing |
| DE102016205121A1 (de) * | 2016-03-29 | 2017-10-05 | Siemens Aktiengesellschaft | Verfahren zum Voting mit verketteten Signaturen |
| US11088855B2 (en) | 2016-07-29 | 2021-08-10 | Workday, Inc. | System and method for verifying an identity of a user using a cryptographic challenge based on a cryptographic operation |
| US10637665B1 (en) | 2016-07-29 | 2020-04-28 | Workday, Inc. | Blockchain-based digital identity management (DIM) system |
| US11336432B2 (en) | 2016-07-29 | 2022-05-17 | Workday, Inc. | System and method for blockchain-based device authentication based on a cryptographic challenge |
| US10933300B2 (en) | 2016-09-26 | 2021-03-02 | Shuffle Master Gmbh & Co Kg | Card handling devices and related assemblies and components |
| US10339765B2 (en) | 2016-09-26 | 2019-07-02 | Shuffle Master Gmbh & Co Kg | Devices, systems, and related methods for real-time monitoring and display of related data for casino gaming devices |
| US10547592B2 (en) | 2017-01-19 | 2020-01-28 | Hewlett Packard Enterprise Development Lp | Computing a global sum that preserves privacy of parties in a multi-party environment |
| AU2017395785B2 (en) * | 2017-01-30 | 2023-12-21 | EXO One Pty Ltd | Voting system and method |
| US10798086B2 (en) | 2017-05-08 | 2020-10-06 | Amazon Technologies, Inc. | Implicit certificates using ring learning with errors |
| US10511591B2 (en) * | 2017-05-08 | 2019-12-17 | Amazon Technologies, Inc. | Generation of shared secrets using pairwise implicit certificates |
| US10516543B2 (en) | 2017-05-08 | 2019-12-24 | Amazon Technologies, Inc. | Communication protocol using implicit certificates |
| US11896891B2 (en) | 2018-09-14 | 2024-02-13 | Sg Gaming, Inc. | Card-handling devices and related methods, assemblies, and components |
| US11376489B2 (en) | 2018-09-14 | 2022-07-05 | Sg Gaming, Inc. | Card-handling devices and related methods, assemblies, and components |
| US11338194B2 (en) | 2018-09-28 | 2022-05-24 | Sg Gaming, Inc. | Automatic card shufflers and related methods of automatic jam recovery |
| US11087578B2 (en) | 2018-11-15 | 2021-08-10 | Daniel Bernard Ruskin | Voting booth, system, and methods of making and using same |
| CN112307488A (zh) * | 2019-07-31 | 2021-02-02 | 华为技术有限公司 | 一种认证凭据保护方法和系统 |
| US11038699B2 (en) | 2019-08-29 | 2021-06-15 | Advanced New Technologies Co., Ltd. | Method and apparatus for performing multi-party secure computing based-on issuing certificate |
| US11898837B2 (en) | 2019-09-10 | 2024-02-13 | Shuffle Master Gmbh & Co Kg | Card-handling devices with defect detection and related methods |
| US11173383B2 (en) | 2019-10-07 | 2021-11-16 | Sg Gaming, Inc. | Card-handling devices and related methods, assemblies, and components |
| US12099997B1 (en) | 2020-01-31 | 2024-09-24 | Steven Mark Hoffberg | Tokenized fungible liabilities |
| US20210336789A1 (en) * | 2020-03-30 | 2021-10-28 | Facebook, Inc. | Deterministic sparse-tree based cryptographic proof of liabilities |
| US12034800B2 (en) | 2021-02-24 | 2024-07-09 | Ip Technology Labs, Llc | Systems and methods for automated, controllerless and stateless network connection selection based on distributed server information |
| US12034799B2 (en) | 2021-02-24 | 2024-07-09 | Ip Technology Labs, Llc | Systems and methods for automated, controllerless and stateless network connection selection based on distributed server information |
| US12051282B2 (en) * | 2021-05-22 | 2024-07-30 | Carey Robert Briggs | System and method for conducting a publicly auditable election with secret ballots |
| US20230290208A1 (en) * | 2022-01-27 | 2023-09-14 | James McNulty | Secure electronic voting method and apparatus |
| GB202209495D0 (en) * | 2022-06-29 | 2022-08-10 | Nchain Licensing Ag | Proof of ownership |
Family Cites Families (22)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4774665A (en) | 1986-04-24 | 1988-09-27 | Data Information Management Systems, Inc. | Electronic computerized vote-counting apparatus |
| FI86486C (fi) | 1990-08-27 | 1992-08-25 | Tecnomen Oy | Foerfarande foer att arrangera teleroestningen pao ett saekert saett. |
| US5278753A (en) * | 1991-08-16 | 1994-01-11 | Graft Iii Charles V | Electronic voting system |
| NL9301348A (nl) * | 1993-08-02 | 1995-03-01 | Stefanus Alfonsus Brands | Elektronisch betalingssysteem. |
| US5400248A (en) * | 1993-09-15 | 1995-03-21 | John D. Chisholm | Computer network based conditional voting system |
| US5708714A (en) * | 1994-07-29 | 1998-01-13 | Canon Kabushiki Kaisha | Method for sharing secret information and performing certification in a communication system that has a plurality of information processing apparatuses |
| US5875432A (en) | 1994-08-05 | 1999-02-23 | Sehr; Richard Peter | Computerized voting information system having predefined content and voting templates |
| US5495532A (en) | 1994-08-19 | 1996-02-27 | Nec Research Institute, Inc. | Secure electronic voting using partially compatible homomorphisms |
| US5682430A (en) * | 1995-01-23 | 1997-10-28 | Nec Research Institute, Inc. | Secure anonymous message transfer and voting scheme |
| IL113259A (en) * | 1995-04-05 | 2001-03-19 | Diversinet Corp | A device and method for a secure interface for secure communication and data transfer |
| US6092051A (en) * | 1995-05-19 | 2000-07-18 | Nec Research Institute, Inc. | Secure receipt-free electronic voting |
| FR2738934B1 (fr) | 1995-09-15 | 1997-11-28 | Thomson Multimedia Sa | Systeme de comptabilisation anonyme d'informations a des fins statistiques, notamment pour des operations de vote electronique ou de releves periodiques de consommation |
| US5604804A (en) * | 1996-04-23 | 1997-02-18 | Micali; Silvio | Method for certifying public keys in a digital signature scheme |
| US5610383A (en) | 1996-04-26 | 1997-03-11 | Chumbley; Gregory R. | Device for collecting voting data |
| US5878399A (en) * | 1996-08-12 | 1999-03-02 | Peralto; Ryan G. | Computerized voting system |
| US6029150A (en) | 1996-10-04 | 2000-02-22 | Certco, Llc | Payment and transactions in electronic commerce system |
| US6250548B1 (en) | 1997-10-16 | 2001-06-26 | Mcclure Neil | Electronic voting system |
| US6081793A (en) * | 1997-12-30 | 2000-06-27 | International Business Machines Corporation | Method and system for secure computer moderated voting |
| WO2000013082A1 (en) * | 1998-09-02 | 2000-03-09 | Diversified Dynamics, Inc. | Direct vote recording system |
| US6317833B1 (en) | 1998-11-23 | 2001-11-13 | Lucent Technologies, Inc. | Practical mix-based election scheme |
| AU3770200A (en) | 1999-03-25 | 2001-04-17 | Votehere. Net | Multiway election method and apparatus |
| US6769613B2 (en) * | 2000-12-07 | 2004-08-03 | Anthony I. Provitola | Auto-verifying voting system and voting method |
-
2001
- 2001-03-24 JP JP2001571337A patent/JP2003529256A/ja active Pending
- 2001-03-24 CA CA002404161A patent/CA2404161C/en not_active Expired - Fee Related
- 2001-03-24 EP EP01924313A patent/EP1302020B1/en not_active Expired - Lifetime
- 2001-03-24 ES ES01924313T patent/ES2251475T3/es not_active Expired - Lifetime
- 2001-03-24 AU AU2001250976A patent/AU2001250976A1/en not_active Abandoned
- 2001-03-24 AT AT01924313T patent/ATE309655T1/de not_active IP Right Cessation
- 2001-03-24 DK DK01924313T patent/DK1302020T3/da active
- 2001-03-24 US US09/816,869 patent/US6950948B2/en not_active Expired - Fee Related
- 2001-03-24 DE DE60114833T patent/DE60114833T2/de not_active Expired - Fee Related
- 2001-03-24 WO PCT/US2001/009550 patent/WO2001073694A2/en active IP Right Grant
-
2006
- 2006-01-19 JP JP2006011456A patent/JP2006115550A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2007318745A (ja) * | 2006-04-27 | 2007-12-06 | Matsushita Electric Ind Co Ltd | コンテンツ配信システム |
Also Published As
| Publication number | Publication date |
|---|---|
| DK1302020T3 (da) | 2006-03-20 |
| ATE309655T1 (de) | 2005-11-15 |
| US6950948B2 (en) | 2005-09-27 |
| US20020007457A1 (en) | 2002-01-17 |
| AU2001250976A1 (en) | 2001-10-08 |
| WO2001073694A2 (en) | 2001-10-04 |
| WO2001073694A3 (en) | 2003-02-06 |
| DE60114833T2 (de) | 2006-04-13 |
| JP2006115550A (ja) | 2006-04-27 |
| ES2251475T3 (es) | 2006-05-01 |
| EP1302020B1 (en) | 2005-11-09 |
| EP1302020A2 (en) | 2003-04-16 |
| CA2404161A1 (en) | 2001-10-04 |
| CA2404161C (en) | 2006-05-23 |
| DE60114833D1 (de) | 2005-12-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6950948B2 (en) | Verifiable, secret shuffles of encrypted data, such as elgamal encrypted data for secure multi-authority elections | |
| KR100727281B1 (ko) | 검증가능한 비밀 셔플들 및 전자 투표에 대한 그 응용 | |
| Lee et al. | Receipt-free electronic voting scheme with a tamper-resistant randomizer | |
| Neff | A verifiable secret shuffle and its application to e-voting | |
| US20190019366A1 (en) | System and method of determining ballots of voters collected with the aid of electronic balloting | |
| Nair et al. | An improved e-voting scheme using secret sharing based secure multi-party computation | |
| Rjašková | Electronic voting schemes | |
| Radwin et al. | An untraceable, universally verifiable voting scheme | |
| WO2001020562A2 (en) | Multiway election method and apparatus | |
| Heinl et al. | Remote electronic voting in uncontrolled environments: A classifying survey | |
| EP1633077A2 (en) | Verifiable, secret shuffles of encrypted data, such as elgamal encrypted data for secure multi-authority elections | |
| Fan et al. | An efficient multi-receipt mechanism for uncoercible anonymous electronic voting | |
| EP3474241A1 (en) | Electronic balloting | |
| Doan et al. | Encryption Mechanisms for Receipt-Free and Perfectly Private Verifiable Elections | |
| Binu et al. | Secret sharing homomorphism and secure E-voting | |
| JP2004192029A (ja) | 電子投票システム、投票データ生成サーバ、端末装置、及び、集計サーバ、ならびに、コンピュータプログラム | |
| RU2271574C2 (ru) | Проверяемые секретные перетасовывания и их применение при проведении электронного голосования | |
| CA2550259A1 (en) | Verifiable, secret shuffles of encrypted data, such as elgamal encrypted data for secure multi-authority elections | |
| KR100611038B1 (ko) | 검증가능한 비밀 셔플들 및 전자 투표에 대한 그 응용 | |
| Yang et al. | RVBT: a remote voting scheme based on three-ballot | |
| Røsland | Remote Electronic Voting | |
| Dall'Olio et al. | Voting with Designated Verifier Signature-Like Protocol. | |
| Hassler | Aspects of group communications security | |
| Allayear et al. | Secure E-Voting System with Secure Storage Media | |
| Yıldırım | Internet voting based on homomorphic encryption |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20050906 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20051206 |
|
| RD04 | Notification of resignation of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7424 Effective date: 20051206 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20051213 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20060119 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20060620 |
|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20021125 |