| 講演名 | 2015-03-02 準同型暗号の安全性証明の限界について 高橋 大樹, 長谷川 真吾, 磯辺 秀司, 小泉 英介, 静谷 啓樹, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では,準同型暗号を対象として,安全性証明の根拠となり得る言語の複雑さを評価することで,安全性証明の限界について検討する.具体的には,任意の二項組(b,c)が与えられたとき,cが平文bの暗号文になっているかどうかを判定する問題(暗号文検証問題)の複雑さがNPの内部階層のLow階層で特徴付けられる場合について,準同型暗号方式に対する安全性証明の限界がLow階層で特徴づけられることを示す.さらに,暗号文検証問題が統計的ゼロ知識証明を持つ言語のクラスSZKで特徴付けられる場合についても同様の考察を行い,この場合については,安全性証明の限界がSZKとAM∩coAMの中間に位置する程度のクラスで特徴付けられることを示す. |
| 抄録(英) | In this paper, we explore on the limitation of security proofs for homomorphic encryptions. We consider the computational complexity for verifying the validity of the plaintext-ciphertext pairs, that is, on any given pair (b, c), to determine whether or not c is a ciphertext of the plaintext b. We show that for any homomorphic encryption scheme, if the complexity of its verification problem is characterized by the classes in the low hierarchy within NP, then the scheme cannot be proven to be secure beyond the low hierarchy classes via reduction proofs. We also discuss the case where the complexity of the verification problem is characterized by SZK, the class of languages that have statistical zero-knowledge proofs, and show that the limitation of the security proofs is characterized by some intermediate class between SZK and AM ∩ coAM. |
| キーワード(和) | 準同型暗号 / 安全性証明 / Low階層 / 統計的ゼロ知識証明 |
| キーワード(英) | homomorphic encryption / security proof / low hierarchy / statistical zero-knowledge |
| 資料番号 | IT2014-67,ISEC2014-80,WBS2014-59 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2015/2/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 準同型暗号の安全性証明の限界について |
| サブタイトル（和） | |
| タイトル（英） | On the Limit of Security Proof for Homomorphic Encryption |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 準同型暗号 / homomorphic encryption |
| キーワード(2)（和/英） | 安全性証明 / security proof |
| キーワード(3)（和/英） | Low階層 / low hierarchy |
| キーワード(4)（和/英） | 統計的ゼロ知識証明 / statistical zero-knowledge |
| 第 1 著者 氏名（和/英） | 高橋 大樹 / Daiki TAKAHASHI |
| 第 1 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 2 著者 氏名（和/英） | 長谷川 真吾 / Shingo HASEGAWA |
| 第 2 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 3 著者 氏名（和/英） | 磯辺 秀司 / Shuji ISOBE |
| 第 3 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 4 著者 氏名（和/英） | 小泉 英介 / Eisuke KOIZUMI |
| 第 4 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 5 著者 氏名（和/英） | 静谷 啓樹 / Hiroki SHIZUYA |
| 第 5 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 発表年月日 | 2015-03-02 |
| 資料番号 | IT2014-67,ISEC2014-80,WBS2014-59 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | 471 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |