投票ブースの役割とオラクル問題：インターネット選挙とレシートフリー

14 min readJul 5, 2020

人間の営みのオンライン化

COVID-19の感染拡大は我々の生活のあり方を大きく変え、これまで物理的に行なっていた営みを、できうる限りオンライン上で行えるようにするという動きを加速している。投票や選挙も、その有力なユースケースとして話題になっている。一方で、投票や選挙のような、民主主義の根幹であり、一方で悪意や攻撃が常に存在しうるユースケースのセキュリティがどのような性質を満たすべきであり、それがインターネット上のプロトコルだけで実現できるのかについて深く考えないと、社会の営みのどこがオンライン化できるのか、という疑問には答えられれない。そこで、本稿では、投票や選挙というユースケースで、物理的な投票ブースがいかに素晴らしい役割を果たしているのかを紐解きながら、ごく一部のセキュリティ要件においても、これが簡単な問題ではないことを述べる。

日本における電子投票の歴史

インターネットを通じた電子投票の技術的実現については、1990年代から様々な研究がなされている。日本においては、2002年に電子投票法[1]が施行となり、地方自治体での投票の電子化が可能となっている。しかし、これは、即、電子投票＝インターネット投票ということを意味していない。日本においては、1997年に自治省（現在の総務省）が電子機器利用による選挙システム研究会を発足させて検討を開始し、電子投票を主に3段階で発展的に普及させていく計画であった[2]。

- 第1段階：投票所のキオスク端末で投票を行い、集計を行う。ただし、投票者は決められた投票所に赴く
- 第2段階：投票所のキオスク端末で投票を行い、集計を行う。ただし、投票者は任意の投票所で投票が可能
- 第3段階：インターネットを利用して、任意の場所から投票を行うことができる

しかし、この計画は第1段階で頓挫する。2003年に岐阜県可児市で行われた市議会議員選挙で、投票システムのトラブルが発生した。これは後に裁判の末、選挙自体が無効になっている。その結果として2005年には自書式で再度選挙が行われ、2008年には国政選挙でも電子投票を認める電子投票法改正案が廃案になっている。そして、2018年には、唯一電子投票を実施していた青森県六戸町も電子投票の実施をやめるに至っている[3]。つまりは、投票という行為は民主主義の根幹であるがゆえに、その営みを支えるシステムには極めて高い信頼が必要であり、それはプロトコルだけでなく、実装、そして運用に至るまで問題がないことが求められる。

インターネット投票の要件

本稿では、その一部しか取り上げないが、公職選挙として信頼されるセキュアなインターネット投票を実現するには、以下のような性質が必要であるとされる（これが全てではないことに注意）。

(1) 有権者以外の投票の禁止
(2) 同一有権者による二重投票の禁止
(3) 投票の秘密（投票者と投票内容が紐付けられないこと）
(4) 投票の公平性（投票締め切り前に誰も投票の（途中）結果を知ることができない）
(5) 投票結果の非改竄（投票結果が、投票者による入力結果の集計から改竄されないこと）
(6) 集計結果の正しさが検証できること

なお、インターネットタイプの電子投票スキームについては、長い歴史の中、1990年代から、Mix-netを使う方法、準同型暗号を使う方法など実に様々な実現方法が提案されている（筆者も、2003年に準同型暗号を用い、複数票を複数の選択肢に分割投票できるタイプのインターネット投票プロトコルを提案している[4]）。これらをサーベイすることは大変な労力を要するため、本稿では対象外とする。

物理的な投票ブースもたらす素晴らしい効用：レシートフリー

さて、本題として、我々が投票所で投票する時の流れをおさらいしたい。自宅に郵送される投票券を持参し、まずは受付で投票人名簿との照合を行い、投票人名簿に記載されている人であること（有権者以外の投票の禁止）と、すでにその人による投票が行われていないこと（二重投票の禁止）の確認を行う。その上で、選挙管理委員会の押印がなされた投票用紙を受領する。そして、投票者は、誰もが覗くことがない投票ブースで意中の候補者の名前を記入し、投票箱にその紙を投じる。そして、この全体の流れを、立会人が見守るという体制になっている。朝1番に行う「0票確認」（最初の投票者が、投票箱には何も入っていないことを確認する手続き）を含めて、前述の(1)から(5)の要件を満たすために重要な役割を果たしている。

しかし、ここで、先述のインターネット投票の要件には明示的に書かれてなかったが、上記の物理的な投票の流れには、投票や選挙にとって極めて重要な性質の実現方法が書かれている。それがレシートフリーと呼ばれるものだ。これは、選挙における買収や脅迫と大きな関係がある。残念ながら、実際の選挙には、買収や脅迫のような民主主義に対する挑戦が発生してしまう。しかし、立会人が見張っている投票ブースで投票用紙に記入して、投票箱に投票用紙を入れる限りにおいて、仮にその投票者に金品が渡り買収行為がされていたとしても、実際の投票行動に結び付いたかどうかを検証することができない。逆に、買収を試みた候補者に投票した人が投票行為の何らかの経過を見せることが、投票先の証拠になるとすれば、それが買収行為の投資効果を確認できる手段となり、買収を試みたいと考える候補者に大きなインセンティブを与えてしまう。この構造から、投票プロセスの経過の情報が、投票行為の証拠にならない、という性質が必要になる。これをレシートフリー（無証拠性）と呼ぶ。

インターネット投票におけるレシートフリーの研究として最初の論文は26年前の1994年のBenalohらによるSTOCの論文である[5]。翌年1995年のEurocryptで、Mix-netタイプの投票におけるレシートフリーの実現方法が、佐古（現在、早稲田大学教授）とKilianによって提案されている[6]。インターネットを通じた投票の最大のチャレンジの1つはレシートフリーの達成であり、25年以上の歴史のある古い問題であることは強く認識する必要がある。そして、いくら集計システム自体を堅牢に作ったとしても、そこに入力されるデータが本来の趣旨に反している（投票の場合は買収の存在）場合には、システムに期待される役割を果たせなくなる、ということは、近年言われているブロックチェーンにおけるオラクル問題（入力データの確からしさの問題）の1つであると言える。また、これはProvenancy（典拠性）があったとしても解決しないことに注意が必要だ。

もちろん、レシートフリーが実現できれば、買収や脅迫がなくなるわけではなく、投資効果を確認しにくくすることによって、インセンティブを下げる効果しかない。ただ、先述の3段階の中で、第2段階までは投票ブースがあるのに対して、第3段階で投票ブースがなくなることにより、この問題が発生する。そのための、レシートフリーはインターネット投票にとって非常に重要な性質である。現在、インターネット投票を在外投票で実施するための検討が行われているが、ここにおいても、レシートフリーの性質を実装することは極めて重要だ。

なお、買収行為を確実にする別の攻撃手法として、投票者Aが正規の投票用紙を投票したフリをして実際には投票せずに投票所外に持ち出し、投票所外で候補者名を書いて別の投票者Bに託し、その投票者Bが代わりに投票箱に投じて、何も書いていない正規の投票用紙を持ち出し、別の投票者Cに託すことを繰り返す、というタイプの攻撃があることが古くから知られている。これも買収の温床になることが知られているが、これは立会プロセスの厳格化で対応する必要がある。

エストニアが見つけたアナログな緩和方法

電子投票が国家レベルで実施されているエストニアでは、このレシートフリーと買収の問題をユニークな方向で緩和（解決ではない）している。エストニアにおけるインターネット投票の成立過程については[7]に詳しいが、エストニアで採用している方式は「何度でもやり直して上書きができる。何なら、最後は投票日に、投票ブースを使った物理的投票で上書きしても良い」である。この詳細については、筆者による[8], [9]を参照いただきたいが、仮に買収されて結果の投票をしたとしても、最終的には当日に投票所にいくことで、買収された内容と異なる投票を行うことは可能である。これによって、買収を試みる人にとっての投資効果の算定の精度を下げて、インセンティブを削ぐということをしている。つまりは、レシートフリーを実現するには、現実的な解としては物理的な投票所がもたらす信頼に立ち戻るというのが、先進例とされるエストニアですら発生している現実である。

ブロックチェーンは何が助けになって、何が助けにならないのか

選挙や投票があるたびに、ブロックチェーンを使ってセキュアに実現する、という言葉が踊るが、これは果たして実現できるのであろうか。ブロックチェーンのインターネット投票への応用については、いくつかの論文が査読付き国際会議で発表されている。Google Scholorでは、重複もあると考えられるが1万件を超える結果が検索される（もちろん、それら全部が技術提案ではない）。一方で、これが古くから認知されている大きな問題であるにもかかわらずレシートフリーも含めて検討されている例は、それに比べて非常に少ない。2020年6月19日に出版された[10]が、この問題を正面から検討した論文であり、過去のブロックチェーンを使ったインターネット投票の流れを含めて記述されており、参考になる。

「ブロックチェーン技術は改竄に強い」というステートメントに引っ張られる形で、ブロックチェーン技術があればインターネット越しに投票ができるという主張は、専門家と呼ばれる人を含めて比較的よく目にするが、残念ながらこの主張が誤りである。ブロックチェーン技術は、過去のインターネット投票プロトコルの中で公開掲示板を利用していた部分を置き換えるかもしれないが、それはインターネット投票を実現するために必要なセキュリティ上の性質のごく一部に過ぎない。ブロックチェーンの応用を考える際には、常にオラクル問題が存在し、それが典拠性の問題である場合には、TEEを用いた電子署名などの方法が（TEEが脆弱でないことを前提に）一定の解決にはなるが、レシートフリーのような性質は、さらに高度な対応が必要になる。この問題への対応を避けるわけにはいかない。もし、ブロックチェーンのインターネット投票への応用を考えるのであれば、むしろ、セキュアな投票を実現するために必要な性質と背景となる信頼を改めて分析をして、ブロックチェーン技術を使うべきか否かを考えるべきではないだろうか。本稿で取り上げた投票ブースとレシートフリーは、その単なる一例であるが、適切なデザインがなされない限り、ほんの第一段階で失敗して信頼を失ってしまった、17年前と同じ轍を踏むだけに終わるだろう。

参考文献

[1] 地方公共団体の議会の議員及び長の選挙に係る電磁的記録式投票機を用いて行う投票方法等の特例に関する法律, https://www.soumu.go.jp/senkyo/senkyo_s/news/touhyou/denjiteki/pdf/houritsu.pdf
[2] 日立総合計画研究所, 「電子投票」、日経XTECH、https://xtech.nikkei.com/it/free/NGT/govtech/20050509/160519/
[3] 朝日新聞, 「企画特集【電子投票のいま】（上）「可児ショック」今も尾を引く」、http://www.asahi.com/area/gifu/articles/MTW20191210220150001.html
[4] Ishida N., Matsuo S., Ogata W. (2003) Divisible Voting Scheme. In: Boyd C., Mao W. (eds) Information Security. ISC 2003. Lecture Notes in Computer Science, vol 2851. Springer, Berlin, Heidelberg
[5] Benaloh, Josh and Tuinstra, Dwight, “Receipt-Free Secret-Ballot Elections (Extended Abstract,” STOC ’94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 544–553https://doi.org/10.1145/195058.195407
[6] Sako K., Kilian J. (1995) Receipt-Free Mix-Type Voting Scheme. In: Guillou L.C., Quisquater JJ. (eds) Advances in Cryptology — EUROCRYPT ’95. EUROCRYPT 1995. Lecture Notes in Computer Science, vol 921. Springer, Berlin, Heidelberg
[7] 中井遼, “エストニアにおけるインターネット投票導入に係る法改正の議事・投票記録”, 北九州市立大学法政論集第46巻第 1・2 合併号(2018年12月), https://www.kitakyu-u.ac.jp/law/kenkyu/pdf/46-1_2nakai2.pdf
[8] 松尾, R. Laanoja, “暗号プロトコルの社会実装に向けた課題と解決の方向性 — エストニアにおけるケーススタディ”, 3C1–5, 暗号と情報セキュリティシンポジウム2011
[9] 松尾、大久保、”暗号プロトコルの研究活動 ― 標準化及び外部との共同研究 ―”, 情報通信研究機構季報 57((3・4)), 201–210, 2011–09, http://www.nict.go.jp/publication/shuppan/kihou-journal/kihou-vol57no3_4/kihou-vol57no3-4_0404.pdf
[10] T. Dimitriou, “Efficient, Coercion-free and Universally Verifiable Blockchain-based Voting,” Computer Networks, Volume 174, 19 June 2020, 107234, https://doi.org/10.1016/j.comnet.2020.107234

著者

Shin’ichiro Matsuo, Ph.D

Georgetown University, Department of Computer Science, Research Professor. Blockchain Technology and Ecosystem Design (B-TED) Research Center, Director.

アカデミアの立場からブロックチェーン技術を成熟させる活動を行い、ブロックチェーンに関するセキュリティを中心とした研究成果を発表している。ジョージタウン大学Department of Computer Scienceの研究教授として、CuberSMART研究センターのDirectorを務めている。日本では、東京大学、慶應義塾大学を中心としたブロックチェーンに関する中立な産学連携のためのBASEアライアンスを立ち上げ、東京大学生産技術研究所・リサーチフェロー、慶應義塾大学大学院政策・メディア研究科特任教授としても活動中。2020年3月に設立された、ブロックチェーン技術のグローバルなマルチステークホルダー組織Blockchain Governance Initiative Network (BGIN)暫定共同チェア。

ブロックチェーン専門学術誌LEDGER誌エディタ、IEEE, ACM, W3C, CBT, BPASE等のブロックチェーン学術会議やScaling Bitcoinのプログラム委員を務める。ブロックチェーンの中立な学術研究国際ネットワークBSafe.networkプロジェクト共同設立者。ISO TC307におけるセキュリティに関するTechnical Reportプロジェクトのリーダー・エディタ、またおよびセキュリティ分野の国際リエゾンを務める。過去にはISO/IEC JTC1における暗号技術の標準化の日本National Bodyの代表、電子政府推奨暗号を定める暗号技術検討会構成員を歴任。