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

• Item type: SIG Technical Reports(1)
• 公開日: 2004-07-21
• タイトル: 情報量的に安全な秘密多項式評価法と電子投票への応用
• タイトル / 言語: en
• タイトル: Unconditionally Secure Polynomial Evaluation And Its Application To Electronic Voting
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: IPAセキュリティセンター
• 著者所属: 東京大学生産技術研究所
• 著者所属: 東京大学生産技術研究所
• 著者所属(英): en
• 著者所属(英): IT Security Center, IPA.
• 著者所属(英): en
• 著者所属(英): Institute of Industrial Science, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Institute of Industrial Science, University of Tokyo
• 著者名: 大塚玲; AndersonC.A.Nasciment; 今井, 秀樹
• 著者名(英): Akira, Otsuka; Anderson, C.A.Nascimento; Hideki, Imai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では情報量的に安全な秘密多項式評価法(Oblivious Polynomial Evaluation)を提案し，これに基づく電子投票方式の構成法を示す。秘密多項式評価法は，NaorとPinkasが99年に提案した2-partyプロトコルであり、Aliceの持つ秘密多項式とBobの持つ秘密の値からBobの秘密値での多項式の評価結果をBobに出力させるプロトコルである。提案法は、攻撃者の計算能力／記憶能力などに一切の仮定をおかずに安全性を保証できる秘密多項式評価法であり、先に筆者らが与えた秘密鍵サイズの限界式を満たす最適な方式になっている。さらに、本論文ではこの秘密多項式評価法に基づいた情報量的に安全な公開検証可能秘密分散方式（Publicly Verifiable Secret Sharing: PVSS）とこれを用いた掲示板方式による電子投票方式の構成を示す。提案する電子投票方式は有権者数が100万人規模の電子投票においても、投票者が持つべき秘密鍵のサイズが300MB程度と小さく，集票作業全体の検証に要する通信量も1000人まで、1万人までの結託を許す場合でそれぞれ27GB、220GB程度であり効率的である。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose an unconditionally secure oblivious polynomial evaluation (UE-OPE) and a novel electronic voting scheme based on US-OPE. Oblivious Polynomial Evaluation is a 2-party protocol proposed by Neor and Pinkas in 1999 where Alice and Bob are given a secret polynomial, a secret value respectively, and after executing the protocol Bob privately outputs a value of the polynomial evaluated at the secret value without giving any useful information on their secrets. The proposed US-OPE is secure without assuming any computational/storage bound on adversary, and is an optimal construction satisfying the lower bounds previously shown by the authors. Moreover, in this paper, we will present an construction of unconditionally secure publicly verifiable secret sharing (US-PVSS) and an electronic voting scheme in the bulletin board model based on our PVSS.The proposed electronic voting scheme is efficient. For example, in a case of 1 million voters, the storage complexity to store private key required to store for each voter is as small as 300MB. communication complexity to verify the overall tallying process is 27GB in a case of tolerating up to 1000 colluding users, and 220GB in a case of tolerating up to 10,000 users.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11235941
• 書誌情報: 情報処理学会研究報告コンピュータセキュリティ（CSEC）; 巻 2004, 号 75(2004-CSEC-026), p. 351-358, 発行日 2004-07-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会