電子社会の安全な基盤形成に向けて、Paillier暗号、ElGamal暗号などの公開鍵暗号方式と、秘密分散法、しきい値法、Oblivious Transferなどを用いたセキュアで効率的な電子投票方式は最も大事な暗号プロトコルの応用です。これは過去20年にわたって研究されており、投票と票の集計には様々な方法が提案されています。効率的な投票方式は一般的にblind signatureを用いたタイプ、homomorphic　encryptionを用いたタイプ、mix-netを用いたタイプに分類されています。 現実の世界での大統領選挙では、各投票者が候補者の中で一人の候補者にのみ投票し、過半数でなくても得票数を一番多く得たトップの候補者が選ばれます。Plurality（絶対多数）投票方式とも呼ばれるこの方式では投票者の意思を正しく反映させることが難しいのが現状です。 一方で、一人が一票だけを投票する方式だけではなく、複数の選択肢を選ぶアンケートや、複数の選択肢に順位を付けて投票するCondorcet方式、Borda方式、Alternative方式などが存在します。 この論文では、各投票者が候補者のすべてに選好による順序を付けて投票し選挙の結果が各候補者間の一対一の比較によって決定されるCondorcet投票方式に注目します。
我々は、現実の選挙を代替するために要求されている条件を満たしながら安全性・効率性を満たす暗号技術を使った安全かつ普遍的に証明可能なone-on-one comparison privacyを満たしているCondorcet電子投票を提案します。更に、選挙の結果は各投票者が指定した候補者の順序を明らかにせずに決定することができます。選好によるすべての候補者の順序を表わすためにマトリックスを使用し、one-on-one comparison privacyを満たすためには準同型性を用いています。 我々の方式はmix-netあるいはblind signatureの使用により、投票者の計算上のコスト及びデータのサイズを小さくすることができます。また、mix-netに基づいた方式では、各投票者が候補者のすべてに付けた選好による順序やどの候補者が何票で勝ったのかが明らかになってしまいますが、我々の方式ではセキュリティの必要条件であるone-on-one comparison privacyを満たすことが出来ます。 そのために、mix-netに基づいた方式を単に適用する代わりに、各投票者の選好の順序による票が合算され、その結果に対する再び再暗号化及び置換を行うマトリックスと準同型性を使用します。 このようにして我々の提案方式では最終の結果や候補者の順序を明らかにせず、 one-on-one comparison privacyを満たしながらどの候補者が選挙で勝ったのかという結果だけを決定します。

2005 International Conference on Computational Intelligence and Security (CIS-05)
December 16, 2005