JPH0863533A - 部分的に互換性のある準同形を使用する保安電子投票の方法および装置 - Google Patents

部分的に互換性のある準同形を使用する保安電子投票の方法および装置

Info

Publication number
JPH0863533A
JPH0863533A JP20493895A JP20493895A JPH0863533A JP H0863533 A JPH0863533 A JP H0863533A JP 20493895 A JP20493895 A JP 20493895A JP 20493895 A JP20493895 A JP 20493895A JP H0863533 A JPH0863533 A JP H0863533A
Authority
JP
Japan
Prior art keywords
equation
vote
electronic voting
posting
sub
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
Application number
JP20493895A
Other languages
English (en)
Inventor
Jiei Kirian Jiyozefu
ジェイ．キリアン ジョゼフ
Kazue Sako
和恵 佐古
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NEC Corp
Original Assignee
NEC Corp
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by NEC Corp filed Critical NEC Corp
Publication of JPH0863533A publication Critical patent/JPH0863533A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G07—CHECKING-DEVICES
    • G07C—TIME OR ATTENDANCE REGISTERS; REGISTERING OR INDICATING THE WORKING OF MACHINES; GENERATING RANDOM NUMBERS; VOTING OR LOTTERY APPARATUS; ARRANGEMENTS, SYSTEMS OR APPARATUS FOR CHECKING NOT PROVIDED FOR ELSEWHERE
    • G07C13/00—Voting apparatus
    • 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/008—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols involving homomorphic encryption
    • 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
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/724—Finite field arithmetic
    • G06F7/725—Finite field arithmetic over elliptic curves
    • 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

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Time Recorders, Dirve Recorders, Access Control (AREA)

Abstract

(57)【要約】 【課題】 電子投票の方法および装置を有効で経済的に
する。 【解決手段】 数理に基づくアルゴリズムにより投票を
保安する。投票者Ｖはｎ個のセンタＣに投票する。通信
および計算のほとんどすべてを前処理することができ
る。センタＣのおのおのは投票が正当にカウントされた
ことを確める。使われているアルゴリズムは部分的に互
換性のある準同形を使っている。投票者ＶもカウンタＣ
もパソコンまたはワークステーションで差支えない。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、保安電子投票に有
益な方法および装置および、特に、数理に基づいた保安
電子投票用のアルゴリズムに関する。詳しく述べると、
このアルゴリズムは、部分的に互換性特性を持つ準同形
のエンクリプションのファミリーに基づいている。
【０００２】
【従来の技術】保安電子投票は、多勢による保安評価に
係る最も重要な単一の応用の一つである。この件につい
ては広範囲な努力にもかかわらず、完全解は理論または
実用の領域のいずれにおいてもまだ見い出されていな
い。多数決保安プロトコルの一般解でさえ選挙の所望の
特性の全てを示していない。例えば、ＳＴＯＣ、５４４
−５５３頁（１９９４年）において「受取り自由の秘密
投票選挙」という題のＪ．Ｃ．ベナロー他の論文は、受
取り自由の特性を述べる。これら一般解は、広い範囲の
保安特性を持ち、厳密な分析には有利であるが計算およ
び通信費用の双方において非実用的である。
【０００３】広く異なる保安特性を持っている多くの更
に実用投票プロトコルが提案されている。匿名のチャネ
ル／ミキサに基づいた計画は、それらの優れた効率と許
容される投票の随意性とのため非常に人気が出て来てい
る。この計画は、Ｄ．ＣｈａｕｍのＡＣＭ、１９８１
年、「ＡＣＭの通信」８４−８８頁における「トレース
できない電子メールおよびデジタル雅号」という題の論
文、Ａ．フジオカ他の「クリプトロジーにおける進歩」
（Ａｕｓｃｒｙｐｔ ´９２）１９９２年、２４４−２
５１頁における「大規模選挙用実用秘密投票計画」とい
う題の論文、およびＣ．パーク他の「クリプトロジーに
おける進歩」（Ｅｕｒｏｃｒｙｐｔ ´９３）１９９３
年、２４８−２５９頁における「オール／ナッシング選
挙計画および匿名チャネル」という題の論文に述べられ
ている。
【０００４】
【発明が解決しようとする課題】しかしながら、ある犠
牲がこの効率に対しては支払われている。これら計画の
うち最も単純なものは、投票者が投票の無視に確実に異
議申し立てするのを許していないし悪意のある投票者が
選挙阻止をするのを許さない。本発明者に知られた計画
においては、高いラウンドでの複雑性、すなわち、匿名
のチャネルを実行するのに使用された各ミキサに対する
一つのラウンドがある。しかも、選挙後投票が正しくカ
ウントされたことをチェックする典型的責任が各投票者
にはある。選挙が適性に行われたことを外部の観察者が
後で検証する方法は通常はない。
【０００５】他のアプローチとしては、匿名のチャネル
またはミキサ無しでの数理技術の使用である。プロトコ
ルは望ましい保安特性を持っているが、詳細に後で述べ
るように、それらの通信の複雑性は現実的なシナリオに
対して大きすぎる。この技術は、Ｊ．Ｂｅｎａｌｏｈお
よびＭ．Ｙｕｎｇによる「ＡＣＭシンポジウムの配分計
算原理」（１９８６年、５２−６２頁）の「投票者のプ
ライバシーを誇張するために政府の権限配分」という題
の論文、Ｊ．Ｂｅｎａｌｏｈによる「Ｙａｌｅｕ／ＤＣ
Ｓ／ＴＲ−５６１」、Ｙａｌｅ大学（１９８７年）の
「検証可能な秘密投票選挙」という題の学位請求論文、
およびＪ．Ｃｏｈｅｎ他の「ＦＯＣＳ８５」（１９８
４，３７２−３８２頁）の「結果および検証可能な暗号
保安選挙計画」という題の論文に述べられている。
【０００６】ＢｅｎａｌｏｈおよびＹｕｎｇのプロトコ
ルは、本発明において得られた望ましい保安特性のほと
んどを享受しており、数５９の形の部分的に互換性があ
る準同形に基づいている。本発明の包含する技術進歩
は、
【０００７】
【数５９】 より大きな一般性： ＢｅｎａｌｏｈおよびＹｕｎｇに
よって使用されたエンクリプションは、因数化問題に同
調されていた。各センターｉはその秘密情報の一部とし
てｎｉの素因数を持っていた。この秘密情報は、投票者
がセンターの公共情報の正確さと相互作用形プロトコル
を通るそれらのサブ荷札の正確さとを検証する必要があ
るのでプロトコルを複雑にした。本発明は、「ディスク
リート・ログ型」の問題に応用可能である。
【０００８】償却技術： 投票における最前の努力とは
異なり、本発明は更に効率良く複数選挙を行う方法を考
慮に入れている。通常多くの投票者がおり各投票者をチ
ェックすることが多くのサブチェックを含んでいるた
め、償却技術は単一の選挙を十分にスピードアップして
効率良く使用するのにも有用である。
【０００９】改善されたゼロ知識証明： 直接および効
率の良いプロトコルは、例えば、ｘ＋ｙが１または−１
のいずれかであることを、いずれの場合かを伝えなくて
も示す。これら証明は従来技術に使用されて来た暗号カ
プセル方法より更に効率が良い。
【００１０】しかも、本発明は、例えば、Ｂｅｎａｌｏ
ｈおよびＹｕｎｇの時代には利用可能でなかった相互作
用を取り除くためのファイアト−シャミールヒューリス
ティックのような技術を包含する。これら技術のいくつ
かは、（困難性および有益性のいろいろな程度におい
て）オリジナルのプロトコルに応用も可能である。更に
現代の技術を使用して本発明ではＢｅｎａｌｏｈおよび
Ｙｕｎｇによってレイアウトされた基本アプローチを大
変に効率良く実現する。
【００１１】本発明の開示による保安電子投票のための
数理方法は、適度の通信費用、低いラウンドの複雑性、
前処理のポテンシャル、保安、普遍的検証性および融通
性等の以下述べる全てを含む多くの特徴を提供する。
【００１２】
【課題を解決するための手段】本発明によれば、請求項
１に記載のとおり（ａ）投票者Ｖ１、Ｖ２、…、Ｖｎお
よび投票カウンタＣ１、Ｃ２、…、Ｃｎが、部分的に互
換性のあり掲示されている複数のエンクリプション関数
Ｅａ、Ｅｂ｛Ｅｉ｝のうち任意に選択されたファミリー
に一致する工程と、（ｂ）各投票者Ｖｋはマスク投票数
１を任意に選択し数２用の２つの代表を任意に選択し数
３を掲示する工程と、（ｃ）前記（ｂ）工程における数
２の後半を数４に変形する工程と、（ｄ）証明合計アル
ゴリズムを使用することにより前記（ｃ）工程における
式の有効性を証明する工程と、（ｅ）アルゴリズムプル
ーブ±１を実行する工程と、および（ｆ）全てのｊおよ
びｉ用の数５の公共のエンクリプションアルゴリズムを
使用してＣｉを暗号化しそのエンクリプションを掲示す
る工程とを備える部分的に互換性のある準同形を使用す
る保安電子投票の方法が得られる。
【００１３】
【作用】保安電子投票のアイデアは、各投票者の投票を
秘密に保ち、選挙結果が多くのカウントセンターの干渉
が無く防不正の秘密投票を電子的に行えるようにするこ
とである。本発明は新規性な数理方法に依存しており、
異なるカウントセンタに供給されたシェアに投票を分け
ることにより投票を検証用にコード化するものである。
その上、投票は検証のため前処理可能であるが、最終の
投票決定は実際の投票の時までに遅延される。ここに使
用される方法では、複数投票検証を効率良く認めてい
る。ついでながら、この方法では現状利用可能なパソコ
ンまたはワークステーションおよび従来の電子掲示板を
使用することによりすぐに実施される。
【００１４】本発明では以前の数理プロトコルにくらべ
て通信費用はあまり必要でない。パラメータの一つの現
実的セッティングとして、本発明はＢｅｎａｌｏｈ−Ｙ
ｕｎｇ計画の通信にくらべて内輪に見積もって１／２０
しか必要でない。しかも、複数の選挙が行われる時に、
前投票の利益を１５０倍ないし２５０倍にあげる償却技
術を使用可能となる。しかしながら、各投票の通信複雑
性は、匿名のチャネル／ミキサを基にしたプロトコルに
より要求されたものより遥かに大きいがこれは実施可能
な範囲であることに注目すべきである。
【００１５】本発明の方法は、極端に低いラウンドの複
雑性を享受する。一旦、システムがセットされたら、投
票者は単一のメッセージを掲示することだけにより選挙
における投票を行える。カウント工程は各カウントセン
タが単一の非常に短いメッセージを掲示することを備え
ている。
【００１６】理想的には、人は実際の投票の前に通信お
よび計算の大半を行いたいだろう。本方法では、人々の
投票を単一のメッセージにより予め処理することが可能
である。予め処理する工程は最終的な投票に依存しない
し、投票のための投票者が「登録」をするときに行って
も良い。実際に投票を行う時が来た時には、投票者は単
一のビットを掲示するだけでよりことがしばしばであ
る。こうして本人確認に署名が必要なときも通信費用は
無視して良い。同様に、予め処理後に、投票センタとし
てのパソコンは、１秒ごとに１００の入力投票を容易に
計数可能である。
【００１７】妥当な発見的仮定のもとで、投票者または
センタの連合は、選挙に不正な影響を与えたり、または
意味ありげにその出力を遅延することはない。投票者
は、２つのセンタが正直であるかぎり自分の投票の秘密
を維持する。２つの正直なセンタの要求は、単純な二重
のメカニズムによって単一の正直なセンターの要求に下
げられ得る：各センターは基礎的な計画における２つの
センターと同等になる。
【００１８】発見的仮定が（例えば、ファイアット−シ
ャミールの非相互作用証明のための方法）使用されてい
る間、唯一の公知の攻略法によれば、動作中のグループ
についてディスクリート−ロガリズムを計算することだ
れである。こうして、ディスクリートログ問題が因数分
解より遥かに困難であると現在考えられている楕円曲線
を使用することが可能になる。以前の数理アプローチ
は、数６０についての第ｒの剰余問題に基づいており、
もしｎを因数分解できるならば、解が保証される。
【００１９】
【数６０】 投票者のあらゆる行為は、投票の前処理または実際の投
票かどうかにかかわらず、投票が正しく行われた証明を
伴う。計算センターの出力が正しいかどうかは容易に確
かめられる。関係者は、だれか他の人の投票が荷札に含
まれたことを立証できる。一旦、当事者がメッセージを
掲示すると、その仕事のチェックする際に共同する必要
がない。選挙をチェックするのは、多くの当事者に分配
され得る。そして、もしだれかがまだ満足されていない
ならば、その人は結果を自分でチェックすることもでき
る。こうして、投票者は、投票を送るだけで他の関与を
せずに、選挙には最小限の参加をするという選択権を持
っている。
【００２０】本発明は、異なる状況に容易に適用され
る。例えば、センターの数は、はなはだ大きくすること
もできる。投票者は、自分自身の保安／効率トレードオ
フを選択し、多くのセンターを使うこともどのセンター
を使用するかを選択することもできる。こうして、２つ
が正直であるかぎりセンターが１００箇所の選挙におい
て典型的投票者が１０箇所を選択して選挙を行うことが
可能である。大きな選挙に対して、階層のカウント計画
が実行可能となる。
【００２１】本発明は、新しいツールすなわち部分的に
互換性のある準同形のエンクリプション関数のファミリ
ーを提供する。加算（Ｅ（ｘ＋ｙ）＝Ｅ（ｘ）Ｅ
（ｙ））または乗算Ｅ（ｘｙ）＝Ｅ（ｘ）Ｅ（ｙ）の準
同形を持つエンクリプション関数が公知である。これら
の特性は、非常に効率の良いゼロ知識証明を作るように
利用されるが、保安に対する仕事もすることができる。
例えば、Ｅ（ｘ）およびＥ（ｙ）があって、ｘ＋ｙが１
または−１かどうかを知るのを望むと仮定しよう。もし
Ｅが加算準同形を持つ（確率エンクリプションに対し
て）関数であるならば、Ｅ（ｘ＋ｙ）すなわちＥ（１）
またはＥ（−１）に等しいかどうかを計算できる。
【００２２】ＢｅｎａｌｏｈおよびＹｕｎｇの「ＡＣＭ
シンポジウム・オン・プリンシプルズ・オブ・ディスト
リビューテッド・コンピュータ」１９８６年５２−６２
頁における「投票箱のプライバシーを高めるように政府
の権力を分散する」という第の論文において、確率エン
クリプション関数｛Ｅ１、…、Ｅｎ｝のファミリーを使
ってこの困難を乗り越えている。ここに各自のＥｉは、
ｒをｉとは独立のかなり大きい素数とするときエレメン
ト数６１を確率的にエンクリプトする。このＥｉは、Ｅ
ｉ（ｘ＋ｙ）＝Ｅｉ（ｘ）Ｅｉ（ｙ）を満足するが、Ｅ
ｉ（ｘ）とＥｉ（ｙ）との結合によりｘとｙとの簡単な
関数をエンクリプトする自明の方法はない。この技術の
重要な要求は、下記の形式により条件を容易にしたよう
にエンクリプションＥｉが確率的だということである。
【００２３】
【数６１】 本発明においては、決定論的なエンクリプション関数
｛Ｅ１、…、Ｅｎ｝のような加算的準同形のファミリー
を考慮する。このファミリには、Ｅｉ（ｘ＋ｙ）＝Ｅｉ
（ｘ）Ｅｉ（ｙ）のように、数６２とするとき（ｑは大
きいとする）ひとつのグループＺｑが存在する。したが
って、これらは基本的には両立する。しかし、すべての
（ｉ、ｊ）について下記の二つの寄与が計算上は区別で
きないことが必要である。
【００２４】
【数６２】 １．Ｚq からｘとｙとを一様に選んだとき（Ｅ
i （ｘ）、Ｅj （ｙ））、 ２．Ｚq からｘを一様に選んだとき（Ｅi （ｘ）、Ｅj
（ｘ））。
【００２５】これらのことは、任意のｖについて（Ｅi
（ｘ）、Ｅi （ｖ−ｘ′））と（Ｅi （ｘ）、Ｅ
j （ｙ））とが区別できないということを意味する。
【００２６】上のように、ｘ＋ｙ＝ｖであるようにｘと
ｙとを一様に選んだとき、（Ｅi （ｘ）、Ｅj （ｇ））
が分かっていないということからだけでは、ｖについて
は何も分からない。同様に、ｘ1 ，…，ｘn の和がｖで
あり、｛ｘ1 ，…，ｘn ｝の値についてｎ−２であるこ
とが分かっているとしても、ｖについては何も分からな
い。
【００２７】このようなエンクリプレション関数のファ
ミリは以上の性質を持つ部分的に互換性がある準同形の
エンクリプレション関数である。このようなファミリを
既知の代数的な仮定に変換することは知れていない。し
かし、このようなエンクリプション関数のファミリとし
ての候補はたくさんある。たとえば、ｑを素数とすると
き素数ｐi はｐi ＝ｋiq＋１であるとし、ｇi を数６３
のために任意（または準任意）に選んだジェネレータで
あるとし、数６４であるとする。もし数６５であれば、
離散した対数を計算しないかぎりＥ1 （ｘ1 ）とＥ
2 （ｘ2 ）のｘ1 ＋ｘ2 について何かの情報を得る手段
はない。この方法のただ一つの弱点は、もしｐ1 ＝ｐ2
であってα2 ＝α1 l とするようなｌが知られていれば
ｘ1 ＋ｙ2 を与えられた数に等しくするような数６６が
計算できてしまうことである。ただし、ｐ1 がｐ2 に等
しくなければ、このような解決はできない。
【００２８】
【数６３】
【００２９】
【数６４】
【００３０】
【数６５】
【００３１】
【数６６】 だ円曲線または他のグループに基づくエンクリプト関数
を使うこともできる。さらに、どの形式のグループでも
任意に結合することができる。記述を簡単にするため、
αi によってジェネレートされた巡回グループの掛け算
記法を、このグループが掛け算的に使われるか足し算的
に使われるかには拘わらずに、使うこととする。
【００３２】これら部分的に交換可能な準同形のエンク
リプト関数を使えば、甚だ有効な相互作用証明は次のと
おり確めることができる。
【００３３】すなわち：値のエンクリプトが与えられて
いれば、ｘ1 ＋ｘ2 ＋…＋ｘn ＝ａ＋ｂであること、エ
ンクリプトがｘとｙとについて与えられていれば前記数
６６であること。
【００３４】これらの証明は有効であるから何回も使え
るし、Ｆｉａｔ−Ｓｈａｍｉｒが「アドバンシズ・イン
・クリプトロジ」（１９８６年にＳｐｒｉｎｇｅｒ−Ｖ
ｅｒｌａｇ出版の「クリプト '８６」）の１８６ないし
１９９ページに出した「あなた自身をどのようにして証
明するか、特定および署名の問題への実際的な解決」と
いう題の論文の啓発により相互作用を防ぐこともでき
る。
【００３５】この改良された証明法によれば、数理技術
の複雑さが、パソコンにより伝言を投票掲示板に掲示す
ることができる程度までにすることができる。ただし、
秘密用パラメータを強め（Ｆｉａｔ−Ｓｈａｍｉｒ法の
ときは誤り率とした２-40 ないし２-60 が好ましい）投
票者が複数個（たとえば１０か所）のセンタを使って投
票の秘密を保ちたいときは、費用はかなりかさむ。した
がって、本発明はこれらの負担を軽くする方法を提供す
る。
【００３６】選挙に先立ってほとんどの仕事を片づける
ことにより、計算および通信の負担を時間的に平均化し
選挙を速めることができる。証明のための計算の負担を
軽くするには、表を参照する技術によりグループ操作の
数を減らす。さらに、一人の投票者が多数の投票を処理
して、それら投票を個別に処理する場合にくらべると通
信や計算の手段を大いに減らすことができる。
【００３７】暗号法に償却を使うことは新規ではない。
たとえば、「アドバンシス・イン・クリプトロジ」
（「クリプト '９０（１９９１発行）の３３９ないし３
５２ページにおけるクロサワおよびツジの「多言語・ゼ
ロ言語相互作用の証明システム」という題の論文には二
つの主張について、ひとつづつの主張についてのゼロ知
識証明を接続するだけの場合よりも有効なゼロ知識証明
が述べてある。また、「ＦＯＣＳ９０」（１９９１年発
行）の６９ないし７８ページのＢｏｙａｒ、Ｂｒａｓｓ
ａｒｄ、およびＰｅｔａｌｔａの「サブ二次ゼロ知識」
と題する論文と「ＳＴＯＣ９２」（１９９２年発行）の
７２２ないし７３２ページのＫｉｌｉａｎの「ゼロ知識
の有効な証明および議論についてのノート」と題する論
文は、単に順次的な繰り返しの場合よりも僅かの計算に
よりＮＰ用のゼロ知識証明を高度な確実さで達成する問
題を考えている。「ＳＴＯＣ９２」（１９９２年発行）
の６９９ないし７１０ページのＦｒａｎｋｌｉｎおよび
Ｙｕｎｇの「保全計算の通信の複雑性」と題する論文に
おいては、ｋ種類の多数保全計算を単一保全計算の費用
のｋ倍よりも経済的に達成する方法を明らかにしてい
る。
【００３８】したがって本発明は、部分的に互換特性を
持つ準同形を用いた保安電子投票のため、従来にくらべ
て、有効な方法および装置を提供する。
【００３９】
【発明の実施の形態】以下、本発明を包含する基本的な
投票手段を述べる。記述を簡単にするため投票を計数す
るセンタは２か所だけとし、投票はイエスかノーかだけ
だとする。ただし、投票を計数するセンタがたくさん
（たとえば１０か所）ある場合にも本発明が適用される
ことは当業者には明らかであろう。基本的な方法におい
ては、センタが一か所だけのときは投票の秘密が保護さ
れない。しかし、この問題は、センタが二か時炉以上の
ときは以下に述べるように解決される。
【００４０】二か所のセンタをｃ1 およびｃ2 で表わ
す。各投票ｖをシェアｘ1 およびｘ2に分ける。ただ
し、ｑを素数とするとき、ｘi はＺq の構成要素（メン
バー）である。掲示に先立って各シェアｘi をエンクリ
プト関数Ｅi により暗号化する。ただし、｛Ｅ1 ，
Ｅ2 ｝は、部分的に互換性のある準同形エンクリプト関
数のファミリを作るものとする。
【００４１】常に１回だけ行なえば済む形成過程の一部
分として、関係者は｛Ｅ1 ，Ｅ2 ｝に同意する。離散対
数関数による実施形態のときは秘密に保たなければなら
ない情報は全くないことを注意しておく。したがって、
一般的な源泉からの数ビットを準ランダム・ビット発生
器に入力し、希望の関数を定義するに使うモジュロとジ
ェネレータとを得られたランダム・ビットによって選ぶ
のに使うことができる。発明を記述する観点から言え
ば、準ランダム・ジェネレータの種子は誰が与えてもい
いし、種子に依存して関数の組が微力になるということ
もない。
【００４２】エンクリプト関数のファミリを作ることの
ほか、公衆キー暗号化や保安ビット列委託などの基本的
な根源は既に確立されていると仮定する。また、Ｈ
（ｘ）は確率的混合関数を表わし、送信者をｘに委託
し、しかもこのｘについては何らの有用な情報も与えな
いものとする。
【００４３】選挙の基本的手続きは３段階に進む。すな
わち、投票の準備、投票、および投票の計数である。
【００４４】各投票者は投票ｖi を、イエスへの投票の
ときは１でノーへの投票のときは−１というように選
ぶ。投票者はｘi (1) およびｘi (2) を一様に選び数６
７であるとする。
【００４５】
【数６７】 次いで投票者は数６８および数６９を掲示し、数７０を
証明する。ただし、ｘi (1) もｘi (2) もｖi も公には
しないものとする。
【００４６】
【数６８】
【００４７】
【数６９】
【００４８】
【数７０】 各投票者は、公衆キーｃ1 およびｃ2 を使ってｘi (1)
およびｘ1 (2) をそれぞれ暗号化する。各センタは数７
１を計算して、これが既に掲示されている値と一致する
ことを確める。
【００４９】
【数７１】 各センタｊは数７２をすべての投票者ｉについて合計
し、サブ荷札ｔj を掲示する。各投票者は数７３を確
め、Ｔ＝ｔ1 ＋ｔ2 を計算する。この計算は投票イエス
の数から投票ノートの数を減じた差に等しい。
【００５０】
【数７２】
【００５１】
【数７３】 図１を参照すると、簡単なアルゴリズムが示してあり、
「プルーブ±１」と書いてある。これは、シェアの有効
性すなわちＥ1 （ｘ1 ）とＥ2 （ｘ2 ）とが与えられた
とき数７４を証明するものである。このアルゴリズム
は、投票の半分づつを結合したとき結果が有効投票であ
ることを証明者が証明する方法である。ただし、この方
法は実際の投票について何らかの情報を開示するもので
はない。
【００５２】
【数７４】 図１のアルゴリズムを実行するごとに、ずるい証明者は
１／２の確率で捕促できる。ここに、（Ｙ1 ，Ｙ2 ）の
分布は、与えられた（Ｅ1 （ｘ1 ），Ｅ2 （ｘ2 ））を
容易にシミュレートするものであることを注意してお
く。実際のところ、Ｒを完全なゼロ知識ビット委託であ
るとすると、このアルゴリズムは完全なゼロ知識であ
る。観念的にならび、もっと簡単なアルゴリズムによっ
ても証明者に２ｂの項に図示したようにｓ（ｘ2 −ｒ）
を公にさせるであろうことを注意しておく。このアルゴ
リズムを選んだのは、通信の複雑さが減るからである。
証明者が両方の可能性をチェックすれば、ｓとｔとを省
くこともできるが、２ビットだけしか節約できない。
【００５３】このアルゴリズムは証明者について述べて
あるが、もっと完全で有用な解決方法としてはＦｉａｔ
−Ｓｈａｍｉｒ法により相互作用を除く方法がある。第
１に、プロトコルを多数回（４０回ないし６０回）実行
してあらゆる無効申立を支える可能性を無視できるほど
下げることである。次には、証明者の代わりに乱数的に
見える混合関数を使って、上述のプロトコルの１の項に
おける証明者による掲示に対する無効申立を形成するこ
とである。証明者が誤りの主張を証明しようとしたと仮
定しても、証明者の唯一の戦略としては混合関数により
異る掲示を行ない誰が無効申立をしているのかを証明者
は見つけることができる。しかし、この攻略法は、誤り
の確率がはなはだ小さい（２-40 ないし２-60 ）のとき
は、費用が多大になる。
【００５４】上の説明においてはセンタは２か所であ
り、イエスかノーかの単一投票であると仮定した。実際
には、投票者はできるだけ多くのセンタに投票を分けて
投票の秘密性を高めたいであろう。さらに投票者として
は、たくさんの選挙に加入したいだろうし、一つの選挙
においても多くのイエス・ノーの投票があるだろう。た
とえば上記のＢｅｎａｌｏｈは、承認投票（候補者が複
数のときに１票を投ずる場合も含む）は、イエス・ノー
の独立した投票が複数種類ある場合と同様であることを
指摘している。次に、多くの投票を多くのセンタに分
け、しかも各投票を別々に用意する場合にくらべて節約
ができる方法を述べる。
【００５５】記述を簡単にするため、センタはｎか所、
各投票者は票をすべてのセンタに入れるとしよう。セン
タｉごとに上述のファミリから選んだエンクリプト関数
Ｅiがあるとする。基本的な手段として述べたとおり、
投票者は投票数７５をシェア数７６により分けて数７７
とし、次いでこれらシェアは正しく使われていることを
証明する。図１に示したプルーブ±１というアルゴリズ
ムを適用するのが、二つ以上のシェアを扱うには最も直
接的な解となる。この証明を次の２段階に分けてもよ
い。第１に、証明者はａとｂとをｖ＝ａ＋ｂであるよう
に任意に選んで数７８を証明する。第２に、図１のプル
ーブ±１のアルゴリズムによりｖ＝ａ＋ｂであることを
証明する。こうすることにより、複数投票を効率よく扱
う機会が得られることは下に述べるとおりである。
【００５６】
【数７５】
【００５７】
【数７６】
【００５８】
【数７７】
【００５９】
【数７８】 図２は、プルーブ和として参照するアルゴリズムを示
す。このアルゴリズムにより、ｎ個の暗号化されたシェ
アを二つのシェアの和で済ませる。投票者は投票を多く
の暗号化されたシェアに分けしかも投票のおのおのを二
つの暗号化された半分に既に分けたとする。このプルー
ブ和アルゴリズムは、多くのシェアを結合すると二つの
半分に等しくなることを証明する方法である。この方法
によっては、実際の投票についての情報は何も得られな
い。プルーブ和のアルゴリズムを、プルーブ±１のアル
ゴリズムと共用すると、多くのシェアに分けた投票を巧
妙な投票に結合することができる。
【００６０】仮に投票者は数７９が成り立つことを証明
するものとし、数８０の値は数８１の範囲で知れている
としよう。次に、係数数８２を任意に選び、次の線形方
程式数８３を考える。確率についての簡単な議論による
と次の事が成り立つ。
【００６１】
【数７９】
【００６２】
【数８０】
【００６３】
【数８１】
【００６４】
【数８２】
【００６５】
【数８３】 １．原線形方程式すべてが正しければ、新しい線形方程
式も成り立つこと、 ２．原線形方程式に正しくないものが一つでもあれば、
新しい線形方程式が正しくない確率は１−１／ｑである
こと。
【００６６】したがって、新しい、線形方程式について
証明すれば、原線形方程式の証明ができる。
【００６７】ただし、新しい変数の暗号をどのように作
るかや、係数をどう選ぶかという問題が残る。この暗号
としては数８４を使うことができる。
【００６８】
【数８４】 これら係数ｃi を無効申立とみなすことができる。上述
のとおり、原暗号化の混合関数により値ｃi をＥｉａｔ
−Ｓｈｍｉｒの方法で作ることができる。この際、複数
回の操作をする必要はない。何故かというと、係数を任
意に決めるとき、原方程式の組における誤差は最終的な
方程式においては、極めて小さくなるからである。実際
の計算の効率上、ｃi を｛１，…，２60｝から選べば十
分で、これにより累乗を早く計算することができる。
【００６９】図３は上述の本発明の選挙方法のアルゴリ
ズムを、ｍ個の投票をｎか所のセンタに分布させた場合
を示す。前計算の段階において、それら任意に出力され
た投票を暗号化されたシェアに従って分ける。投票の段
階において、投票者は投票をそのままカウントすべきか
逆転（イエス（１）をノー（−１）として或いはノー
（−１）をイエス（１）として）してカウントすべきか
指定する。投票スウントの段階において、投票センタは
それぞれにおける投票のシェアをカウントしサブ荷札を
掲示する。このサブ荷札は、投票者のサブ組についての
何らかの情報を提供するものではない。次いでこれらサ
ブ荷札を合計して投票の最終合計を算出する。このアル
ゴリズムの各段階において、投票者および関係外の人々
（おそらくは後の時期のもの）はそれら段階のおのおの
が正しいかどうかを確める情報が得られる。
【００７０】次に本発明の通信費用を推定しよう。本発
明についてはいろいろな変形が可能なことは当業者にと
って明らかであるが、そういう複雑さについての十分な
理解を、投票を暗号化されたシェアに分ける費用を分析
し、それらシェアが優れて形成されていることを証明す
ることにより明らかにしよう。
【００７１】この分析には多数の保安パラメータが含ま
れる。第１に、エンクリプト関数は数８５に渡ってのモ
ジュロ表現に基づき、ｋは長さｐi の上限を表わす（異
るモジュロを使うときは値が等しくはなくてもよい）と
しよう。また、委託に使う混合関数Ｈの出力をｈとし、
証明を何回くり返したかを記述する保安パラメータをｌ
とする。
【００７２】
【数８５】 最も一般的にｍ個の投票をｍか所のセンタに分ける場合
を考えよう。ここに使う方法によれば、ｍが大きいほど
償却の効率は高まる。証明の費用を計算に入れなけれ
ば、変形に使う二つの追加のシェアとともにこれらを表
わすには（ｎ＋２）ｋｍビットが必要である。正確さを
証明するには［２（ｎ＋２）ｋ＋（ｎ＋１）ｈ］ｌビッ
トが必要である。ここに、投票者は、投票を表わすｎ個
のシェアのおのおのは２個の補助シェアに等しいことを
既に証明したとしよう。こり証明により、２個の補助の
１または−１への和には［３ｋ＋ｈ］ｌｍビットが必要
になる。これらシェアを然るべき権力者に開示するには
凡そｎｋｍが必要である。合計すると数８６ビットが必
要である。ここに得られる結果を表１に示す。二つのセ
ンタの代りに一つの良いセンタを使うために「センタ２
重化」をすると、費用は２倍になる。
【００７３】
【数８６】
【００７４】
【表１】 投票者たちについての凡その推定費用は次のとおりであ
る本発明によると、費用の必要な計算は主にモジュロ掛
け算とモジュロ表現とである。共通の基礎によっていろ
いろなモジュロ表現が可能である。このことは、それら
表現に必要な掛け算の数を減らすようなルック・アップ
・テーブルを計算することにより達成される。たとえ
ば、２の累乗であるすべてのｉについて数８７を予め計
算しておく。こうすることにより、数８８の計算に必要
な掛け算の平均の回数を、（ｎ＋２）ｋ2 ビットのテー
ブルの使用により、３ｋ／２ないしｋ／２に減らす。も
っと巧妙なテーブルを使えば典型的な例においては掛け
算の平均の回数を１／３にすることができる。
【００７５】
【数８７】
【００７６】
【数８８】 もう一度、ｍ個の投票のおのおのをｎ個ののシェアに分
けることを考えよう。投票ｍ個を数がｍｎの部片に分け
るには（ｎ＋２）ｋｍ／２回の掛け算が必要である。投
票を２シェア表現に変換することを証明するには合計で
（ｎ＋２）ｋｌ／２回の掛け算が必要である。すべての
投票が有効であることを証明するにはｋｌｍ回の掛け算
が必要である。おのおののセンタのサブ荷札を確めるに
は数８９回のモジュロ掛け算が必要である。
【００７７】
【数８９】 結局のところ凡そ数９０回のモジュロ掛け算が必要であ
る。パソコンを３３ＭＨｚで働かせると、７６８回の掛
け算は１秒間で済む。このことに基づいての結果も前記
表１に示した。ただし以上の数字は近似にすぎない。し
かし、他のモジュロ足し算や混合関数を計算する操作の
費用は、どちらかというと、無視できる。
【００７８】
【数９０】 次に確めに必要な計算費用の凡その推定をしよう。以前
と同じく、ｋの長さはｐで、ごまかしの最大確率を決め
る保安パラメータはｌであるとする。さらに、ｃの値は
係数の長さであり、本方法においては小さく決めること
ができる。もう一つ、モジュロ表現を実行するにはルッ
ク・アップ・テーブルの参照する技術を使うことができ
る。
【００７９】投票ｍ個おのおのをｎ個のシェアに分ける
場合を考える。合計では数９１回の掛け算が、これらシ
ェアを暗号化に表現するのに必要である。結合した式の
正しいことを確めるには数９２回の掛け算が必要であ
る。シェアが良好であることを確めるには合計（ｋ＋
１）ｌｍ回の掛け算が必要である。結局、投票者１人に
ついては数９３回のモジュロ掛け算が必要である。
【００８０】
【数９１】
【００８１】
【数９２】
【００８２】
【数９３】 この回数を減らすには、多数のモジュロ表現を確める技
術を使うことができ、これにより実際にこれら表現を計
算する場合にくらべて１／４にまで減らすことができ
る。
【００８３】ＢｅｎａｌｏｈおよびＹｕｎｇの労作によ
り、投票を部片に分け、確めが可能な荷札により投票の
合計の結果を生ずる第１の手段が得られた。しかし彼ら
の手段は、通信がはなはだ複雑であるから在来の回路網
に実施するには非現実的であると思われる。通信が複雑
になる理由の一つは、センタｉが共通のキーＮi の秘密
の素因数を作らなければならないことに依る。したがっ
て彼らの手段は、起き得るごまかしを検出するための相
互作用のプロトコルを共通のキーの決定の際に含み、こ
の相互作用のプロトコルは、検出されたごまかしが不正
の投票者によるものではないことを示す必要がある。さ
らに、サブ荷札についての余分の情報から秘密の素因数
が公けになってしまうかもしれないから、相互作用のプ
ロトコルによってサブ荷札が正しいことを証明しなけれ
ばならない。これらの理由により、彼らのプロトコルに
は、ｋをｎ個のセンタに共通なキーの大きさとし、ｌを
保安パラメータとするとき、数９４個のビットが必要に
なる。
【００８４】
【数９４】 彼らの手段は繰り返すごとに計算の複雑さは減る。それ
は、計算が数９５に依存し、ここにｃとｒとはｎにくら
べるとはなはだ小さいからである。しかしながら、相互
作用の証明は何回もしなければならないから、合計の費
用は小さいままではない。数９６についてのテーブル
（ｎｒｋビットが必要）を作るステップと同じものを使
うと仮定すると、ｎビットのモジュロ掛け算が合計で数
９７回も必要になる。ここに、ｋはｎ個のセンタに共通
なキーの大きさであり、ｒは投票者の数を決め、ｌは保
安パラメータである。凡その数値的な比較が前記表１に
挙げてある。
【００８５】
【数９５】
【００８６】
【数９６】
【００８７】
【数９７】 本発明を実施する方法を述べたから、次には本発明を実
行する好ましい実施例を述べよう。
【００８８】図４は本発明を実施する好ましい構成を図
式的に示す。投票者も投票カウンタもパソコンまたはワ
ーク・ステーション１０であり、在来の電子的掲示板１
２に接続してある。投票に関与するすべての、関係者
（すなわち投票者、証明者、カウンタなど）はメッセー
ジを掲示し、掲示板からのメッセージを送る。投票者は
投票カウンタにもなる。パソコンには、上述の方法を実
行するソフトウェアまたは下に図５ないし図９について
述べる構成要素のハードウェアあるいはソフトウェアを
含む。
【００８９】図５は投票形成する形成素子１４を図式的
に示す。上述の部分的に準同形のエンクリプト関数を使
うイエス・ノー投票の選択１６により形成素子１４は投
票ごとにシェア１８を作り、暗号化したシェア２０を作
る。形成素子１４は、暗号化されたシェアを結合すると
良好に形成された投票になることを誰でもが証明できる
ように、投票認証証明２２をも形成する。暗号化したシ
ェア２０と証明２２とは電子掲示板１２に掲示される。
センタｃi の矢印は、一般的に掲示された情報をデクリ
プトすることが許されるのは誰であるかを示すに過ぎな
い。
【００９０】図６はイエスの投票をノーの投票に変換
し、ノーの投票をイエスの投票に変換するインバータ２
４を図式的に示す。暗号化されたシェア２０を入力され
ると、インバータ２４は変換された投票２６（番号にダ
ッシュをつけて示す）を出力する。同様に、暗号化して
ないシェア２８が入力されると、インバータ２４は、変
換され暗号なしのシェア３０を出力する。実際の投票の
間においては、以前に形成した投票をカウント前に変換
するかしないかを投票者は指定はする。カウンタが、投
票者の指定に一致してカウントするか、指定に反して投
票をチェックする人により検出するかしなければならな
い。インバータ２４は、登録のときなどに前以て投票を
前処理することができ、そのときは後の投票をそのまま
或いは反転する。これにより、投票は一そう有用にな
る。
【００９１】図７は投票チェッカ３２を図式的に示す。
暗号化されたシェア２０と投票確認証明２２とが入力さ
れると、チェッカ３２は、暗号化されたシェアを結合し
て有用な投票とするか、それともそのようなことをしな
いかを決める。
【００９２】図８は多数投票形成素子４２を図式的に示
す。この図の場合は、多数投票形成素子４０は多数イエ
ス・ノーの投票を多数投票形成素子４２に送る。多数投
票形成素子４２は、投票のおのおのについてシェアを形
成し、それらシェアを暗号化する。暗号化された投票は
投票札４４の形となる。これら多数投票を形成するには
１個の多数投票確認証明４６を使う。
【００９３】図９は、多数投票チェッカ４８を図式的に
示す。図８の多数投票形成素子４２が形成した投票の組
を多数投票チェッカ４８はチェックし、また、これら投
票の組を１個の多数投票形成素子４２が形成するに当っ
ては暗号化されたシェア４４と多数投票確認証明４６と
を使って出力したことをチェックする。図７の投票チェ
ッカ３２について述べたように、多数投票チェッカ４８
も、シェアを結合して良好な投票を形成できるかどう
か、すなわち投票が有効か無効かをチェックできる。
【００９４】図１０は、図３に示した投票動作を図式的
に示す。投票者Ｖは図示のようにイエス・ノーの投票を
行なう。投票はシェアに分割され、暗号化され、多くの
センタＣに分けられる。証明により投票をチェックする
ことにより、それら投票が適切に暗号化されたことの証
明になる。投票とセンタとにより選挙を確認する。セン
タは配分されたシェアを結合してサブ荷札を作る。これ
らサブ荷札を更に結合することにより選挙の最終結果が
得られる。
【００９５】
【発明の効果】本発明による保安電子投票の方法および
装置によれば、投票の費用が節約され、有効な投票を行
なうことができるという効果がある。
【図面の簡単な説明】
【図１】シェアの有効性を証明するのに有用なアルゴリ
ズムである。
【図２】合計の主張を証明するのに有用なアルゴリズム
である。
【図３】本発明による電子的手段のアルゴリズムであ
る。
【図４】本発明を実施するための好ましい例の概略図で
ある。
【図５】投票形成素子の概略図である。
【図６】投票インバータの概略図である。
【図７】投票チェッカの概略図である。
【図８】複合投票形成素子の概略図である。
【図９】複合投票チェッカの概略図である。
【図１０】図３における投票過程の図である。
【符号の説明】
１０ 投票者および投票カウンタ １２ 電子掲示板 １４ 投票構成者（形成素子） ２４ インバータ ３２ 投票チェッカ ４２ 複数投票構成者 ４８ 複数投票チェッカ Ｖ 投票者 Ｃ カウンタ

Claims (28)

    【特許請求の範囲】
  1. 【請求項１】 （ａ） 投票者Ｖ１、Ｖ２、…、Ｖｎお
    よび投票カウンタＣ１、Ｃ２、…、Ｃｎが、部分的に互
    換性のあり掲示されている複数のエンクリプション関数
    Ｅａ、Ｅｂ｛Ｅｉ｝のうち任意に選択されたファミリー
    に一致する工程と、（ｂ）各投票者Ｖｋはマスク投票数
    １を任意に選択し数２用の２つの代表を任意に選択し数
    ３を掲示する工程と、（ｃ）前記（ｂ）工程における数
    ２の後半を数４に変形する工程と、（ｄ）証明合計アル
    ゴリズムを使用することにより前記（ｃ）工程における
    式の有効性を証明する工程と、（ｅ）アルゴリズムプル
    ーブ±１を実行する工程と、および（ｆ）全てのｊおよ
    びｉ用の数５の公共のエンクリプションアルゴリズムを
    使用してＣｉを暗号化しそのエンクリプションを掲示す
    る工程とを備える部分的に互換性のある準同形を使用す
    る保安電子投票の方法。 【数１】 【数２】 【数３】 【数４】 【数５】
  2. 【請求項２】 （ｇ）投票者ｋが投票ｊを使用するため
    に、数６を計算し実際の投票が数７に等しくなり数８を
    掲示する工程を更に備える請求項１に記載の保安電子投
    票の方法。 【数６】 【数７】 【数８】
  3. 【請求項３】 （ｈ）各センタＣｉが全てのｋおよびｊ
    に対して数９をデクリプトし数１０に一致するかどうか
    を検証する工程と、（ｉ）各センタＣｉが数１１により
    サブ荷札を計算しこのサブ荷札を掲示する工程と、
    （ｊ）前記投票をチェックするおのおのは数１３が数１
    ２に等しいことを検証する工程とを更に備える請求項２
    に記載の保安電子投票の方法。 【数９】 【数１０】 【数１１】 【数１２】 【数１３】
  4. 【請求項４】 ｊを掲示する工程を更に備える請求項２
    に記載の保安電子投票の方法。
  5. 【請求項５】 前記（ｃ）、（ｄ）、および（ｄ）の工
    程では認証証書を発行する結果と成る請求項１に記載の
    保安電子投票の方法。
  6. 【請求項６】 前記発行ではファイアット−シャミール
    法を適用することを備える請求項５に記載の保安電子投
    票の方法。
  7. 【請求項７】 （ｇ）投票者ｋは、投票ｊを使用するた
    めに、数１４を計算し実際の投票が数１５に等しくな
    り、数１６を掲示する工程を更に備える請求項５に記載
    の保安電子投票の方法。 【数１４】 【数１５】 【数１６】
  8. 【請求項８】 （ｈ）各センタＣｉが全てのｋおよびｊ
    に対して数１７をデクリプトし数１８に一致するかどう
    かを検証する工程と、（ｉ）各センタＣｉが数１９によ
    りサブ荷札を計算しこのサブ荷札を掲示する工程と、
    （ｊ）前記投票をチェックするおのおのは数２０が数２
    １に等しいことを検証する工程とを更に備える請求項７
    に記載の保安電子投票の方法。 【数１７】 【数１８】 【数１９】 【数２０】 【数２１】
  9. 【請求項９】 ｊを掲示する工程を更に備える請求項７
    に記載の保安電子投票の方法。
  10. 【請求項１０】 （ａ）投票者Ｖ１、Ｖ２、…、Ｖｎお
    よび投票カウンタＣ１、Ｃ２、…、Ｃｎが、部分的に互
    換性のあり掲示されている複数のエンクリプション関数
    Ｅａ、Ｅｂ｛Ｅｉ｝のうち任意に選択されたファミリー
    に一致する工程と、（ｂ）各投票者Ｖｋはマスク投票数
    ２２を任意に選択し数２３用の２つの代表を任意に選択
    する工程と、（ｃ）投票者ｋが投票ｊを使用するため、
    数２４を計算し実際の投票が数２５に等しくなり数２６
    を掲示する工程と、（ｄ）各センタＣｉが数２７により
    サブ荷札を計算しこのサブ荷札を掲示する工程とを備え
    る部分的に互換性のある準同形を使用する保安電子投票
    の方法。 【数２２】 【数２３】 【数２４】 【数２５】 【数２６】 【数２７】
  11. 【請求項１１】 複数の投票者Ｖ１、Ｖ２、…、Ｖｎお
    よび複数の投票カウンタＣ１、Ｃ２、…、Ｃｎのおのお
    のが、部分的に互換性のあり公共的にアクセス可能なメ
    ディア上に掲示されている複数のエンクリプション関数
    Ｅａ、Ｅｂ｛Ｅｉ｝のうち任意に選択されたファミリー
    を持ち、各投票者はマスク投票数２８を任意に選択し数
    ２９用の２つの代表を任意に選択し、前記公共的にアク
    セス可能なメディア上に数３０および数３１を掲示する
    とともに、前記数２９の後半を数３２の形に変形する手
    段と、証明合計アルゴリズムを使用することにより数３
    ３の有効性を証明する手段と、アルゴリズム±１を実行
    する手段と、全てのｊおよびｉ用の前記部分的のエンク
    リプション関数を使用する数３４を暗号化しそのエンク
    リプションを前記公共的にアクセス可能なメディア上に
    掲示する手段とを備える部分的に互換性のある準同形を
    使用する保安電子投票の装置。 【数２８】 【数２９】 【数３０】 【数３１】 【数３２】 【数３３】 【数３４】
  12. 【請求項１２】 数３５を計算し実際の投票が数３６に
    等しくなり、ｋを前記複数の投票者の一人としｊを投票
    であるとするとき前記公共的にアクセス可能なメディア
    上に数３７を掲示する手段を更に備える請求項１１に記
    載の保安電子投票の装置。 【数３５】 【数３６】 【数３７】
  13. 【請求項１３】 各センタＣｉが全てのｋおよびｊに対
    して数３８をデクリプトし数３９に一致するかどうかを
    検証するように前記カウンタのおのおのと組み合わせた
    手段と、数４０によりサブ荷札を計算し前記公共的にア
    クセス可能なメディア上にこのサブ荷札を掲示するよう
    に前記カウンタのおのおのと組み合わせた手段と、数４
    １が数４２に等しいことを検証する手段とを更に備える
    請求項１２に記載の保安電子投票の装置。 【数３８】 【数３９】 【数４０】 【数４１】 【数４２】
  14. 【請求項１４】 前記公共的にアクセス可能なメディア
    上にｊを掲示する手段を更に備える請求項１２に記載の
    保安電子投票の装置。
  15. 【請求項１５】 前記投票カウンタおよび前記投票者
    は、パーソナルコンピュータを備え、前記公共的にアク
    セス可能なメディアは電子掲示板を更に備える請求項１
    １に記載の保安電子投票の装置。
  16. 【請求項１６】 認証証書を発行する手段を更に備える
    請求項１１に記載の保安電子投票の装置。
  17. 【請求項１７】 前記発行手段はファイアット−シャミ
    ール法を適用する手段を含む請求項１６に記載の保安電
    子投票の装置。
  18. 【請求項１８】 数４３を計算し実際の投票が数４４に
    等しくなり、ｋが前記複数の投票者の一人でありｊが投
    票であるとき、前記公共的にアクセス可能なメディア上
    に数４５を掲示する手段を更に備える請求項１６に記載
    の保安電子投票の装置。 【数４３】 【数４４】 【数４５】
  19. 【請求項１９】 全てのｋおよびｊに対して数４６をデ
    クリプトし数４７に一致するかどうかを検証するように
    前記カウンタのおのおのに組み合わせた手段と、数４８
    によりサブ荷札を計算し前記公共的にアクセス可能なメ
    ディア上にこのサブ荷札を掲示するように前記カウンタ
    のおのおのに組み合わせた手段と、数４９が数５０に等
    しいことを検証する手段とを更に備える請求項１８に記
    載の保安電子投票の装置。 【数４６】 【数４７】 【数４８】 【数４９】 【数５０】
  20. 【請求項２０】 前記公共的にアクセス可能なメディア
    上にｊを掲示する手段を更に備える請求項１８に記載の
    保安電子投票の装置。
  21. 【請求項２１】 前記投票カウンタおよび前記投票者
    は、パーソナルコンピュータを備え、前記公共的にアク
    セス可能なメディアは電子掲示板を備える請求項１６に
    記載の保安電子投票の装置。
  22. 【請求項２２】 複数の投票者および複数の投票カウン
    タのおのおのが、部分的に互換性があり公共的にアクセ
    ス可能なメディア上に掲示されている複数のエンクリプ
    ション関数Ｅａ、Ｅｂ｛Ｅｉ｝のうち任意に選択された
    ファミリーを持ち、各投票者Ｖｋはマスク投票数５１を
    任意に選択し数５２用の２つの代表を任意に選択し公共
    的にアクセス可能なメディア上に前記数３０および前記
    数３１を掲示するものであって、ｋが前記複数の投票者
    の一人でありｊが投票であるとき数５３を計算し実際の
    投票が数５４に等しくなり数５５を前記公共的にアクセ
    ス可能なメディア上に掲示する手段と、全てのｋおよび
    ｊに対する数５６をディクリプトし数５７と一致するか
    どうかを検証するために前記カウンターのおのおのと組
    み合わされた手段と、数５８によりサブ荷札を計算しこ
    のサブ荷札を前記公共的にアクセス可能なメディア上に
    掲示する手段と、前記投票の結果を決定するために前記
    サブ荷札を結合する手段とを備える部分的に互換性のあ
    る準同形を使用する保安電子投票の装置。 【数５１】 【数５２】 【数５３】 【数５４】 【数５５】 【数５６】 【数５７】 【数５８】
  23. 【請求項２３】 前記投票カウンタおよび前記投票者
    は、パーソナルコンピュータを備え、前記公共的にアク
    セス可能なメディアは電子掲示板を備える請求項２２に
    記載の保安電子投票の装置。
  24. 【請求項２４】 認証証書を発行する手段を更に備える
    請求項２２に記載の保安電子投票の装置。
  25. 【請求項２５】 前記発行手段はファイアット−シャミ
    ール法を適用する手段を含む請求項２４に記載の保安電
    子投票の装置。
  26. 【請求項２６】 前記投票カウンタおよび前記投票者
    は、パーソナルコンピュータを備え、前記公共的にアク
    セス可能なメディアは電子掲示板を備える請求項２４に
    記載の保安電子投票の装置。
  27. 【請求項２７】 前記サブ荷札を結合する工程を更に備
    える請求項３に記載の保安電子投票の方法。
  28. 【請求項２８】 前記サブ荷札を結合する工程を更に備
    える請求項８に記載の保安電子投票の方法。
JP20493895A 1994-08-19 1995-08-10 部分的に互換性のある準同形を使用する保安電子投票の方法および装置 Pending JPH0863533A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/293363 1994-08-19
US08/293,363 US5495532A (en) 1994-08-19 1994-08-19 Secure electronic voting using partially compatible homomorphisms

Publications (1)

Publication Number Publication Date
JPH0863533A true JPH0863533A (ja) 1996-03-08

Family

ID=23128777

Family Applications (1)

Application Number Title Priority Date Filing Date
JP20493895A Pending JPH0863533A (ja) 1994-08-19 1995-08-10 部分的に互換性のある準同形を使用する保安電子投票の方法および装置

Country Status (5)

Country Link
US (1) US5495532A (ja)
EP (1) EP0697776B1 (ja)
JP (1) JPH0863533A (ja)
DE (1) DE69520714T2 (ja)
ES (1) ES2156594T3 (ja)

Families Citing this family (63)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5682430A (en) * 1995-01-23 1997-10-28 Nec Research Institute, Inc. Secure anonymous message transfer and voting scheme
US6092051A (en) * 1995-05-19 2000-07-18 Nec Research Institute, Inc. Secure receipt-free electronic voting
US5758325A (en) * 1995-06-21 1998-05-26 Mark Voting Systems, Inc. Electronic voting system that automatically returns to proper operating state after power outage
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
US6330608B1 (en) 1997-03-31 2001-12-11 Stiles Inventions L.L.C. Method and system of a computer system for establishing communications between a service provider and a central service factory and registry in a computer system
US6035041A (en) * 1997-04-28 2000-03-07 Certco, Inc. Optimal-resilience, proactive, public-key cryptographic system and method
US20050049082A1 (en) * 1998-03-18 2005-03-03 Callaway Golf Company Golf ball
JP2001202013A (ja) * 2000-01-21 2001-07-27 Nec Corp 匿名参加権限管理システム
WO2000013082A1 (en) 1998-09-02 2000-03-09 Diversified Dynamics, Inc. Direct vote recording system
WO2000021041A1 (en) 1998-10-06 2000-04-13 Chavez Robert M Digital elections network system with online voting and polling
JP3233119B2 (ja) * 1998-12-28 2001-11-26 日本電気株式会社 レシートフリー電子投票方法および装置
AU3770200A (en) 1999-03-25 2001-04-17 Votehere. Net Multiway election method and apparatus
US6834272B1 (en) * 1999-08-10 2004-12-21 Yeda Research And Development Company Ltd. Privacy preserving negotiation and computation
US20020078358A1 (en) * 1999-08-16 2002-06-20 Neff C. Andrew Electronic voting system
US20050160272A1 (en) * 1999-10-28 2005-07-21 Timecertain, Llc System and method for providing trusted time in content of digital data files
US7099471B2 (en) * 2000-03-24 2006-08-29 Dategrity Corporation Detecting compromised ballots
US20030028423A1 (en) * 2000-03-24 2003-02-06 Neff C. Andrew Detecting compromised ballots
DE60114833T2 (de) * 2000-03-24 2006-04-13 Dategrity Corp., Bellevue Überprüfbare, geheime mischung von verschlüsselten daten wie z. b. elgamal-verschlüsselte daten für gesicherte mehrinstanzwahlen
US7389250B2 (en) 2000-03-24 2008-06-17 Demoxi, Inc. Coercion-free voting scheme
US20060085647A1 (en) * 2000-03-24 2006-04-20 Neff C A Detecting compromised ballots
WO2002070998A2 (en) * 2000-11-20 2002-09-12 Amerasia International Technology, Inc. Electronic voting apparatus, system and method
US7422150B2 (en) 2000-11-20 2008-09-09 Avante International Technology, Inc. Electronic voting apparatus, system and method
US7461787B2 (en) * 2000-11-20 2008-12-09 Avante International Technology, Inc. Electronic voting apparatus, system and method
US20020077887A1 (en) * 2000-12-15 2002-06-20 Ibm Corporation Architecture for anonymous electronic voting using public key technologies
US7921033B2 (en) * 2001-01-29 2011-04-05 Microsoft Corporation System and method for high-density interactive voting using a computer network
WO2002067174A2 (en) * 2001-02-20 2002-08-29 Votehere, Inc. Detecting compromised ballots
US6865543B2 (en) * 2001-03-09 2005-03-08 Truvote, Inc. Vote certification, validation and verification method and apparatus
US7729991B2 (en) * 2001-03-20 2010-06-01 Booz-Allen & Hamilton Inc. Method and system for electronic voter registration and electronic voting over a network
KR100727281B1 (ko) * 2001-03-24 2007-06-13 데이트그리티 코포레이션 검증가능한 비밀 셔플들 및 전자 투표에 대한 그 응용
US6817515B2 (en) * 2001-04-25 2004-11-16 Level 3 Communications, Inc. Verifiable voting
AU2002307851A1 (en) * 2001-04-27 2002-11-11 Baltimore Technologies Limited System and method for processing a shared secret
US20030046144A1 (en) * 2001-08-28 2003-03-06 International Business Machines Corporation System and method for anonymous message forwarding and anonymous voting
US7828215B2 (en) * 2001-10-01 2010-11-09 Avante International Technology, Inc. Reader for an optically readable ballot
US7635087B1 (en) 2001-10-01 2009-12-22 Avante International Technology, Inc. Method for processing a machine readable ballot and ballot therefor
US7077313B2 (en) * 2001-10-01 2006-07-18 Avante International Technology, Inc. Electronic voting method for optically scanned ballot
US6942142B2 (en) * 2001-10-02 2005-09-13 Hewlett-Packard Development Company, L.P. Voting ballot, voting machine, and associated methods
AU2002338954A1 (en) * 2001-12-12 2003-06-23 Scytl On Line World Security, Sa Secure electronic voting method and the cryptographic protocols and computer programs used
US20050269406A1 (en) * 2004-06-07 2005-12-08 Neff C A Cryptographic systems and methods, including practical high certainty intent verification, such as for encrypted votes in an electronic election
ES2326175T3 (es) * 2004-06-30 2009-10-02 France Telecom Procedimiento y sistema de votacion electronica en red de alta seguridad.
US20060249578A1 (en) * 2005-05-06 2006-11-09 Fernando Morales Method of confidential voting using personal voting codes
US7986780B2 (en) * 2006-07-06 2011-07-26 Sap Ag Privacy-preserving substring creation
US7995750B2 (en) * 2006-07-06 2011-08-09 Sap Ag Privacy-preserving concatenation of strings
US8061589B2 (en) 2006-10-20 2011-11-22 Barry Cohen Electronic voting system
US8526621B2 (en) * 2006-12-01 2013-09-03 President And Fellows Of Harvard College Method and apparatus for time-lapse cryptography
US7937270B2 (en) * 2007-01-16 2011-05-03 Mitsubishi Electric Research Laboratories, Inc. System and method for recognizing speech securely using a secure multi-party computation protocol
US20090327141A1 (en) * 2007-04-18 2009-12-31 Rabin Michael O Highly efficient secrecy-preserving proofs of correctness of computation
US20090177591A1 (en) * 2007-10-30 2009-07-09 Christopher Thorpe Zero-knowledge proofs in large trades
US8066184B2 (en) * 2008-04-30 2011-11-29 Avante International Technology, Inc. Optically readable marking sheet and reading apparatus and method therefor
US8261985B2 (en) * 2009-04-07 2012-09-11 Avante Corporation Limited Manual recount process using digitally imaged ballots
CA2671269A1 (en) * 2009-07-08 2011-01-08 Ky M. Vu An anti-rigging voting system and its software design
US8261986B2 (en) * 2009-10-21 2012-09-11 Kevin Kwong-Tai Chung System and method for decoding an optically readable markable sheet and markable sheet therefor
ES2367940B1 (es) * 2009-12-04 2012-09-27 Scytl Secure Electronic Voting, S.A. Método para la verificación del correcto registro de una información.
WO2012149395A1 (en) 2011-04-29 2012-11-01 International Business Machines Corporation Fully homomorphic encryption
CN102970143B (zh) * 2012-12-13 2015-04-22 中国科学技术大学苏州研究院 采用加法同态加密方法进行安全计算双方持有数和的指数的方法
CA2823575C (en) 2013-03-15 2016-03-15 Election Systems & Software, Llc System and method for decoding marks on a response sheet
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
US9742556B2 (en) 2015-08-25 2017-08-22 International Business Machines Corporation Comparison and search operations of encrypted data
FR3040519B1 (fr) * 2015-08-28 2017-09-01 Election-Europe Methode de securisation et de verifiabilite d’un vote electronique
GB201800818D0 (en) 2018-01-18 2018-03-07 Nchain Holdings Ltd Computer-implemented system and method
US10897357B2 (en) * 2018-04-04 2021-01-19 International Business Machines Corporation Computation using lattice-based cryptography
CN110958107A (zh) * 2019-12-05 2020-04-03 全链通有限公司 基于区块链的电子投票方法、设备及存储介质
US11361606B1 (en) 2020-11-29 2022-06-14 Oren Zbeda Tamper resistant public ledger voting system
CN112787810A (zh) * 2021-01-07 2021-05-11 杭州链城数字科技有限公司 基于区块链和安全多方计算的电子投票选举方法及装置

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5412727A (en) * 1994-01-14 1995-05-02 Drexler Technology Corporation Anti-fraud voter registration and voting system using a data card

Also Published As

Publication number Publication date
EP0697776B1 (en) 2001-04-18
EP0697776A2 (en) 1996-02-21
DE69520714T2 (de) 2001-08-09
US5495532A (en) 1996-02-27
EP0697776A3 (en) 1999-06-09
ES2156594T3 (es) 2001-07-01
DE69520714D1 (de) 2001-05-23

Similar Documents

Publication Publication Date Title
JPH0863533A (ja) 部分的に互換性のある準同形を使用する保安電子投票の方法および装置
Neff A verifiable secret shuffle and its application to e-voting
JP4235453B2 (ja) 検証可能な秘密のシャッフルおよびそれらの電子投票への応用
Baudron et al. Practical multi-candidate election system
Boneh et al. Evaluating 2-DNF formulas on ciphertexts
Sako et al. Secure voting using partially compatible homomorphisms
Damgård et al. New convertible undeniable signature schemes
Lee et al. Receipt-free electronic voting scheme with a tamper-resistant randomizer
EP1302020B1 (en) Verifiable, secret shuffles of encrypted data, such as elgamal encrypted data for secure multi-authority elections
EP2429115B1 (en) Method for verification of decryption processes
Araújo et al. Towards practical and secure coercion-resistant electronic elections
Chen Efficient fair exchange with verifiable confirmation of signatures
JPH08263575A (ja) 匿名メッセージ伝送方式および投票方式
Rjašková Electronic voting schemes
Damgård et al. Client/server tradeoffs for online elections
WO2001020562A2 (en) Multiway election method and apparatus
Juang et al. A collision-free secret ballot protocol for computerized general elections
EP1361693B1 (en) Handle deciphering system and handle deciphering method, and program
Blanton et al. Improved signature schemes for secure multi-party computation with certified inputs
Chase et al. Verifiable elections that scale for free
Hirt Receipt-free K-out-of-L voting based on ElGamal encryption
Doan et al. Encryption mechanisms for receipt-free and perfectly private verifiable elections
EP1633077A2 (en) Verifiable, secret shuffles of encrypted data, such as elgamal encrypted data for secure multi-authority elections
Niemi et al. Cryptographic protocols and voting
Yang et al. RVBT: a remote voting scheme based on three-ballot

Legal Events

Date Code Title Description
A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 19990714