スリーバロット

ThreeBallot は、2006 年にRon Rivestと Warren D. Smithによって発明された投票プロトコルです。ThreeBallotは、エンドツーエンド (E2E) の監査可能な投票システムであり、原理的には紙の上で実装できます。設計の目標は、暗号化キーを使用せずに暗号化投票システムの利点の一部を提供することでした。

投票を検証可能かつ匿名にすることは難しいかもしれません。ThreeBallot は、各投票者に 3 枚の投票用紙 (1 枚は検証可能、2 枚は匿名) を与えることでこの問題を解決しようとします。投票者はどの投票用紙が検証可能かを選択し、これを秘密にします。投票集計者はそれを知らないため、1 枚の投票用紙を破棄または変更したことが発覚する確率は 1/3 です。投票者は 3 枚の投票用紙のうち 2 枚を互いに打ち消し、1 度しか投票できないようにする必要があります。

ThreeBallot システムが同等の暗号化投票に比べて提供する重要な利点は次のとおりです。

1. その実装は、他の暗号化システムと比較して、有権者にとって見慣れた外観で理解しやすいものです(おそらく、これが最も重要な利点です)。
2. 投票用紙は、解読せずに直接数えることができます。これは、個々の投票セクションでは投票者の候補者の好みを明らかにすることはできませんが、マークの合計が候補者への投票の合計であるという特性があるためです。
3. セキュリティを維持するために保護や秘密保持を必要とするキーはありません(提案されている多くのシステムの「アキレス腱」)。
4. 投票用紙を投函する前に機械で検証する必要がありますが、その後の投票記録は完全に紙で記録されるため、従来の投票用紙に与えられるもの以上の追加のセキュリティ プロセスは必要ありません。

追加の理論的なシステム目標は次のとおりです。

1. 各有権者の投票は秘密にされ、票の売買や強制を防ぎます。
2. 各有権者は、自分の投票が破棄されず、正しく使用され、選挙結果の計算で変更されなかったことを確認できます。（そうでない場合、有権者は投票集計者が不正を行ったことを証明できます。）
3. 選挙結果が正しく計算されたことは誰でも確認できます。
4. この方法は紙の投票用紙を使用するように設計されており、主に低技術のデバイスを必要としますが、より高度な技術とも互換性があります。

ThreeBallot 投票システムでは、投票者に 3 枚の白紙投票用紙が渡されます。各投票用紙には固有の識別子が付けられており、それ以外は同一です。候補者に投票するには、投票者は 3 枚の投票用紙のうち 2 枚でその候補者を選択する必要があります。候補者に反対票を投じるには(他のシステムで投票用紙を白紙のままにしておくのと同じ)、投票者は1 枚の投票用紙でその候補者を選択する必要があります。

したがって、各候補者は少なくとも 1 枚のマーク付き投票用紙と 1 枚のマークなし投票用紙を受け取ります。

その結果、1 票を見ても、投票者がその候補者に投票したかどうかはわかりません。これは、3 票を合計すると各候補者が少なくとも 1 票を獲得することを意味しますが、すべての候補者に対するこの一定のオフセット (投票者数に等しい) は、すべての投票の最終合計から差し引くことができます。

ただし、投票者が投票用紙に記入ミスをしていないことを確認することが不可欠です。3 枚の投票用紙すべてで候補者を空白のままにしたり、3 枚の投票用紙すべてで候補者を選択したりすることはできません。

この要件は、3 票投票を行う前に、3 票すべてを機械に挿入して検証する必要があることを意味します。これを怠ると、投票者は賛成票と反対票の両方を追加で投じることができ、不正投票が可能になります。設計上、賛成票は一度投じられると反対票と区別できないため、この複数票による不正投票は最終集計検証まで検出できず (おそらくそのときも検出されないでしょう)、その時点で修正することも、特定の投票者まで追跡することもできません。

通常、投票者がマークを付けやすくするために、投票用紙は結合されますが、投票する前に、投票用紙を分離することが不可欠です。分離され、他の投票用紙とスクランブルされた順序で結合されると、実際の投票が暗号化されます。たとえば、上記のジョンとバーブの 3 列目の投票用紙だけを考えてみましょう。それぞれに「X」が付いていますが、投票者は実際にはバーブではなくジョンに投票しています。同様に、2 列目の投票用紙だけを見ると、ビルのマークしか表示されませんが、3 つの投票用紙を合わせた全体の投票は実際にはジョンに投票しています。3 つの投票用紙をすべて合計すると、合計はジョンに 2 マーク、バーブとビルにそれぞれ 1 マークが表示されます。投票者の数 (この場合は 1) を差し引くと、ジョンに 1 票、他の投票者には 0 票となります。

投票所では、投票者は 3 枚の投票用紙のうち 1 枚を ID 番号とともにコピーします。実際には、投票用紙を確認する機械が、投票者が 1 枚の投票用紙を自由に選択することに基づいて、この作業を自動的に実行します。その後、3 枚の投票用紙の原本がすべて投票箱に投函されます。投票者は 1 枚のコピーを領収書として保管します。

選挙の終わりに、すべての投票用紙が公開されます。各投票用紙には固有の識別子が付いているため、各有権者は、公開された投票用紙の中からレシートの識別子を探すことで、自分の投票がカウントされたことを確認できます。ただし、有権者はレシートとして受け取る投票用紙を選択できるため、レシートに任意の組み合わせのマークを付けることができます。したがって、有権者は他の政党に自分が誰に投票したかを証明することはできず、このレシートを使用して票の売買や強制などができなくなります。

投票用紙自体には、領収書を作成するためにどの投票用紙がコピーされたかは示されていません。したがって、ある時点で投票用紙が「紛失」したり、悪意を持って破棄されたりした場合、これが領収書投票用紙である可能性は 1/3 です。注意深い投票者であれば、この紛失に気付く可能性があります。

リベスト氏は記事の中で、他の利点と欠点についても論じている。^[1]特に、優先順位投票には適していない。フィールドテストでは、ThreeBallotにはプライバシー、セキュリティ、使いやすさの重大な問題があり、実装上の落とし穴もあることが判明した。^{[2] [3] [4] [5]}

^{ThreeBallot で使用されていた暗号化システムは、Charlie Strauss [4]}が考案した相関攻撃によって破られ、彼はそれを使ってどのように投票したかを証明する方法も示しました^[3] 。ThreeBallotは投票用紙に Yes/No の質問が 1 つしかない場合は安全ですが、1 つのレースで多くの候補者から選択する場合など、質問が複数ある場合は安全ではないと Strauss は指摘しました。彼の攻撃は、3 つの投票用紙のすべての組み合わせが有効な 3 連になるわけではないという事実を利用しました。つまり、投票用紙の任意の行 (関心のある 1 つのレースだけではない) に 3 票または 0 票が投じられた 3 連の組み合わせは、同じ投票者の投票ではあり得ないため、拒否できます。同様に、任意のレースで複数の候補者に投票することになる 3 連の組み合わせも拒否できます。一般的な投票所 (または世界中の人々) で投じられる投票数よりも指数関数的に多くの投票パターンが考えられるため、十分に長い投票用紙であれば、統計的にはほとんどの投票用紙を一意に 3 連にすることができます。^[4]通常、投票用紙の90％は、わずか11〜17の質問で再構成できます。^[5]これにより、投票者の投票は、領収書を持っている人なら誰でも知ることができる可能性があります。 さらに、領収書がなくても、投票者の主張する候補者の選択を信用できないものにする可能性のある情報が漏洩します。^[3]その結果、（金銭、強制、または後世のために）自分の投票を証明しようと共謀する投票者は、事前に合意された異常なパターンですべての投票用紙にマークを付けることができ、後で第三者に合意が守られたかどうかを証明できます（領収書を見なくても）。^[3]どちらの場合でも、秘密投票のベールは突き破られ、領収書のID番号まで追跡できます。

リベストは後に、この当初のコンセプトの論理的誤りを認め^[1]、最終出版物でRFCスキーマを改訂し、各行（各はい/いいえ）を個別に切り取る（質問の相関関係を壊す）ことと、各投票用紙の各マークに固有の追跡番号（各列の投票用紙に1つのIDだけではない）を付けることを義務付けました。これにより、このスキームの解読不可能な側面は回復しましたが、レシート（行ごとに1枚）と切り刻まれた投票用紙の増加により、投票の処理や投票者がレシートを確認する仕組みが著しく複雑になり、意図したシンプルさが損なわれました^[1] 。紙投票の実装と使いやすさの問題に対処する電子バージョンは、コスタらによって提案されました^[6]

• 選挙不正