情報量的に安全な秘密多項式評価法と電子投票への応用

摘要

本論文では情報量的に安全な秘密多項式評価法（Oblivious Polynomial Evaluation）を提案し、これに基づく電子投票方式の構成法を示す。 秘密多項式評価法は、NaorとPinkasが99年に提案した2-partyプロトコルであり、Aliceの持つ秘密多項式とBobの持つ秘密の値からBobの秘密値での多項式の評価結果をBobに出力させるプロトコルである。 提案法は、攻撃者の計算能力/記憶能力などに一切の仮定を置かずに安全性を保証できる秘密多項式評価法であり、先に筆者らが与えた秘密鍵サイズの限界式を満たす最適な方式になっている。 さらに、本論文ではこの秘密多項式評価法に基づいた情報量的に安全な公開検証可能秘密分散方式（Publicly Verifiable Secret Sharing: PVSS）と、これを用いた掲示板方式による電子投票方式の構成を示す。 提案する電子投票方式は有権者数が100万人規模の電子投票においても、投票者が持つべき秘密鍵のサイズが300MB程度と小さく、集票作業全体の検証に要する通信量も1000人まで、1万人までの結託を許す場合でそれぞれ27GB、220GB程度であり効率的である。