【EuroS&P 2021】量子耐性を備えた検証可能なE2E電子投票プロトコルEpoque
TL;DR
E2E e-voting プロトコル
実用的な格子ベースなABB IBEスキームの暗号化プリミティブを利用
形式的にセキュリティを証明
verifiability
accountability
vote privacy
はじめに
本文
セキュアな電子投票には、個人の投票方法を明らかにすることなく、最終的な選挙結果が正しく投票を反映され、これを投票者を含む全員が確認できることが求められる。本論文ではこれをE2E verifiablity and vote privacyと呼んでいるが、vefifiablityとvote privacyの両立は一般には実現の難易度が高い。さらに既存研究で提案されているような実用的なE2E verifiable 電子投票プロトコルは素因数分解や離散対数の困難性に依存しており、量子コンピュータの台頭してきた場合に備え、長期的にvote privacyを守ることが求められる。そこで本論文では、Epoqueという量子耐性を備えた検証可能なE2E電子投票プロトコルを提案している。
既存のポスト量子暗号電子投票プロトコルとして以下2種類が紹介されており、Epoqueはこれらをベースに実用さの観点で改良を加えている。
【1】Boyenらによる、completely lattice-based verifiable decryption mix netの提案
completelyな分、現実の選挙で利用するためには実現性の課題がある
【2】Del Pinoらによるpractical lattice-based cryptographic primitivesの提案
こちらは準同型電子投票プロトコルだが、verifiableでない
ベーシックな準同型秘密分散電子投票システムは以下TABLE 1のように秘密分散と準同型コミットメントスキームを組み合わせて実現される。各コミットメントは投票が0か1のどちらかであるZKPであり、不正な投票を検出できる仕組みとなっている。
https://gyazo.com/60f61aa561b8eb4c3aa297766199afad
(論文中より引用)
上記方式は公開鍵暗号方式(PKE)で実現されるが、課題となってくるのが悪意あるTrusteeの存在であり、具体的には以下の問題に帰着する。
メッセージ$ mに関する情報を明らかにせずに、暗号文$ e_k^iが本当にTrusteeの公開鍵$ pk_kで暗号化(もしくは暗号化に失敗した)されたものであることをどうやって証明するか
これをどうやってlattice-basedかつpracticalに実現するか
Epoqueではこれを解決するため、PKEスキームの代わりにIND-ID-CPA(選択平文攻撃に対する安全性)を持つIBEスキームを採用している。各Trusteeがオリジナルの公開鍵を持つ代わりにmaster publik key $ mpk_kを保持させる。これによって投票者$ V_iがTrustee $ T_kの$ mpk_iを使ってk番目のopening values$ (v_k^i, r_k^i)を送信($ e_k^i)し、第三者にtrusteeが正しいことを証明できる※。
IBEスキームを用いた場合のベンチマークは以下の通りであり、実用的な水準であることが言及されている。
https://gyazo.com/26bf86e2a1c545f599d75971ea80cd5c
(論文中より引用)
ここで$ nは格子の次元であり、セキュリテイパラメータ。論文中ではその他のパラメータについて以下のように定義している。
https://gyazo.com/e8255bc7067c32c33580946bd91910ef
(論文中より引用)
終わりに
長期的なvote privacyを守りながら、verifiableな電子投票プロトコルの提案であり、非常に興味深く読むことができた。また準同型のコミットメントスキームと秘密分散を組み合わせるアプローチも参考になる部分が多く、実際の選挙で利用できるよう実用的な水準で実現する方式を検討している点も学びが多かった。本論文ではわかりやすさのため数式の数を絞ったため、より厳密な議論は本論文を参照されたい。なお形式的な議論もなされている。(文責・恩田) References
【1】 Xavier Boyen, Thomas Haines, and Johannes Muller. A Verifiable ¨and Practical Lattice-Based Decryption Mix Net with External Auditing. In Liqun Chen, Ninghui Li, Kaitai Liang, and Steve A. Schneider, editors, Computer Security - ESORICS 2020 - 25th European Symposium on Research in Computer Security, ESORICS 2020, Guildford, UK, September 14-18, 2020, Proceedings, Part II, volume 12309 of Lecture Notes in Computer Science, pages 336–
356. Springer, 2020.
【2】Rafael del Pino, Vadim Lyubashevsky, Gregory Neven, and Gregor ¨ Seiler. Practical Quantum-Safe Voting from Lattices. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017, pages 1565–1581, 2017.
Appendix
※投票者とTrusteeのそれぞれが悪意ある場合について考えると、IND-ID-CPA安全性のもとで悪意ある投票やコミットメントを検出できることがわかる(詳細は論文参照)