パンチスキャン

パンチスキャン

開発者	Richard Carback、David Chaum、Jeremy Clark、Aleks Essex、Stefan Popoveniuc。
安定版リリース	1.0 (2006年11月2日) [±]
プレビューリリース	1.5 (2007年7月16日) [±]
書かれた	ジャワ
オペレーティング·システム	クロスプラットフォーム
利用可能	英語
タイプ	投票集計システム
ライセンス	改訂BSDライセンス
Webサイト	http://punchscan.org/

Punchscan は、暗号学者David Chaumが発明した光学スキャン 投票集計システムです。Punchscan は、整合性、プライバシー、透明性を提供するように設計されています。このシステムは投票者による検証が可能で、エンドツーエンド (E2E) 監査メカニズムを提供し、各投票者に投票受領書を発行します。このシステムは、2007 年の大学投票システム コンテストで最優秀賞を受賞しました。

Punchscanに組み込まれているコンピュータソフトウェアはオープンソースであり、ソースコードは2006年11月2日に改訂BSDライセンスの下でリリースされました。^{[1]しかし、Punchscanはソフトウェアに依存せず、} DRE投票機のようなソフトウェアセキュリティに頼るのではなく、暗号化機能からセキュリティを引き出します。このため、PunchscanはMicrosoft Windowsなどのクローズドソースのオペレーティングシステム上で実行でき、無条件の整合性を維持できます。

Punchscan チームはその後、追加の貢献者とともにScantegrity を開発しました。

パンチスキャン投票用紙は2 層の紙で構成されています。上層には候補者の名前の横に記号または文字が記されています。候補者リストの下の投票用紙の上層には、丸い穴がいくつか開いています。下層の穴の内側には、対応する記号が印刷されています。

候補者に投票するには、投票者は候補者名の横にある記号に対応する記号のある穴を見つけなければなりません。この穴はビンゴスタイルのインク ドーバーでマークされており、意図的に穴よりも大きくなっています。次に、投票者は投票用紙を切り離し、上層または下層のいずれかをレシートとして保管し、もう一方の層を細断します。レシートは投票所でスキャンされ、集計されます。

候補者名の横の記号の順序は、投票用紙ごとにランダムに生成されるため、投票用紙ごとに異なります。穴の中の記号の順序も同様です。このため、レシートにはどの候補者に投票したかを判断するのに十分な情報は含まれていません。最上層が保持されている場合、穴を通る記号の順序は不明です。最下層が保持されている場合、候補者名の横の記号の順序は不明です。したがって、投票者は自分がどのように投票したかを他の人に証明することができず、票の買収や投票者への脅迫を防ぐことができます。

例として、上の図に示すように、コカコーラとペプシの2人の候補者の選挙を考えてみましょう。候補者名の横の文字の順序は、A、B、またはB、Aの順になります。この順序を と呼び、前者の順序を =0、後者の順序を =1 とします。したがって、 ${\displaystyle P_{1}}$${\displaystyle P_{1}}$${\displaystyle P_{1}}$

${\displaystyle P_{1}}$: 候補リストの横の記号の順序、

${\displaystyle P_{1}\in \{0,1\}=\{{\mbox{AB}},{\mbox{BA}}\}\,}$。

同様に、投票用紙の他の部分についても一般化できます。

${\displaystyle P_{2}}$: 穴を通る記号の順序、

${\displaystyle P_{2}\in \{0,1\}=\{{\mbox{AB}},{\mbox{BA}}\}\,}$。

${\displaystyle P_{3}}$: どの穴がマークされているか、

${\displaystyle P_{3}\in \{0,1\}=\{{\mbox{1st}},{\mbox{2nd}}\}\,}$。

${\displaystyle R}$: 投票結果、

${\displaystyle R\in \{0,1\}=\{{\mbox{コカコーラ}},{\mbox{ペプシ}}\}\,}$。

候補者名の順序はすべての投票で固定されていることに注意してください。投票結果は次のように直接計算できます。

${\displaystyle R=P_{1}+P_{2}+P_{3}{\bmod {2}}\,}$ （式１）

しかし、投票用紙の1層が裁断されると、またはが破壊されてしまうため、レシート（スキャンしたもの）から計算するのに十分な情報がありません。選挙結果を計算するには、電子データベースが使用されます。 ${\displaystyle P_{1}}$${\displaystyle P_{2}}$${\displaystyle R}$

選挙前に、次のような一連の列を持つデータベースが作成されます。データベースの各行は投票用紙を表し、投票用紙がデータベースに格納される順序はシャッフルされます (各候補者がに提供できる暗号化キーを使用)。最初の列 には、シリアル番号のシャッフルされた順序が含まれます。には、キーから生成された疑似ランダムビット ストリームが含まれ、ストリーム暗号として機能します。には中間結果が格納されます。には、次のビットが含まれます。 ${\displaystyle D_{1}}$${\displaystyle D_{2}}$${\displaystyle D_{3}}$${\displaystyle D_{4}}$

${\displaystyle D_{2}+D_{4}=P_{1}+P_{2}{\bmod {2}}\,}$

各投票の結果は別の列 に保存され、投票の順序が再度並べ替えられます。 には、結果が配置される列 の行番号が含まれます。${\displaystyle R}$${\displaystyle D_{5}}$${\displaystyle R}$

選挙が実行され、値がスキャンされた後、次のように計算されます。 ${\displaystyle P_{3}}$${\displaystyle D_{3}}$

${\displaystyle D_{3}=P_{3}+D_{2}{\bmod {2}}\,}$

結果は次のように計算されます。

${\displaystyle R=D_{3}+D_{4}{\bmod {2}}\,}$

これは式1と同等である。

${\displaystyle {\begin{aligned}R&=(D_{3})+D_{4}{\bmod {2}}\\&=(P_{3}+D_{2})+D_{4}{ \bmod {2}}\\&=P_{3}+(D_{2}+D_{4}){\bmod {2}}\\&=P_{3}+(P_{1}+P_{2}){\bmod {2}}\end{整列}}}$

結果の列は公開されますが、投票用紙が（2 回）シャッフルされているため、結果の列の順序はどの結果がどの投票番号によるものかを示すものではありません。したがって、選挙管理当局は投票をシリアル番号で追跡することはできません。

候補者がいる選挙の場合、上記の手順は、modulo -n 方程式を使用して実行されます。 ${\displaystyle n}$

投票者の投票用紙受領書には、どの候補者に投票したかは記載されていないため、秘密情報ではありません。選挙後、選挙管理委員会は各受領書の画像をオンラインで公開します。投票者はシリアル番号を入力して自分の投票用紙を検索し、選挙管理委員会が保持する情報が自分の投票用紙と一致しているかどうかを確認できます。このようにして、投票者は自分の投票が意図したとおりに行われたと確信できます。

投票者や関係者は、データベースの一部を検査して、結果が正しく計算されたことを確認することもできます。データベース全体を検査することはできません。そうしないと、投票を投票用紙のシリアル番号にリンクできてしまうからです。ただし、データベースの半分はプライバシーを侵害することなく安全に検査できます。開封するか、それともランダムに選択されるかが決定されます (この選択は秘密鍵から導き出すことも、サイコロ^[2]や株式市場^[3]などの真のランダムソースから導き出すこともできます)。この手順により、投票者はすべての投票が投票されたと確信できます。 ${\displaystyle \{D_{1},D_{2},D_{3}\}}$${\displaystyle \{D_{3},D_{4},D_{5}\}}$

すべての投票が投じられたとおりに数えられ、意図したとおりに投じられた場合、すべての投票が意図したとおりに数えられます。したがって、選挙の正当性は非常に高い確率で証明できます。

パンチスキャン選挙の信頼性をさらに高めるために、完全に腐敗した選挙管理当局から保護するためのいくつかの追加措置を講じることができます。

データベース内の、、およびはすべて疑似ランダムに生成されるため、これらの列に異なるランダム値を持つ複数のデータベースを作成できます。各データベースは他のデータベースから独立しているため、一部のデータベースの前半を開いて検査し、他のデータベースの後半を開いて検査することができます。各データベースは同じ最終集計を生成する必要があります。したがって、選挙管理委員会が最終集計を歪めるためにデータベースを改ざんする場合、各データベースを改ざんする必要があります。監査で改ざんが明らかになる可能性は、独立したデータベースの数に応じて増加します。 ${\displaystyle D_{1}}$${\displaystyle D_{2}}$${\displaystyle D_{5}}$

選挙の前に、選挙管理委員会は投票用紙を印刷し、データベースを作成します。この作成プロセスの一部には、各投票用紙とデータベースに含まれる固有の情報のコミットが含まれます。これは、情報に暗号化の一方向関数を適用することで実現されます。この関数の結果であるコミットメントは公開されますが、コミットされる実際の情報は封印されたままです。関数は一方向であるため、公開されたコミットメントのみに基づいて封印された投票用紙の情報を判断することは計算上不可能です。

選挙前には、選挙で使用する予定数の 2 倍の投票用紙が作成されます。これらの投票用紙の半分がランダムに選択され (または各候補者が投票用紙の一部を選択することもできます)、開封されます。選択された投票用紙に対応するデータベースの行をチェックして、計算が正しく、改ざんされていないことを確認できます。選挙管理局はどの投票用紙が選択されるかを事前に知らないため、この監査に合格することは、データベースが非常に高い確率で適切に構成されていることを意味します。さらに、投票用紙をそのコミットメントと照合して、投票のコミットメントが正しいことを高い確率で確認することができます。

• ストリーム暗号
• コミットメントスキーム
• ゼロ知識証明

• プロジェクトホームページ
• Vocomp 提出書類 — システムのあらゆる側面を説明する 80 ページの包括的な文書
• 電子民主主義 — BBC ワールドのDigital Planet でDavid Chaum 氏に音声インタビュー。
• あらゆる電子投票を有効活用する — IEEE Spectrum。
• Punchscan による透明でオープンな投票: パート I とパート II
• David Chaumとの Future Tense 音声インタビュー。