| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2015-03-02 14:05 準同型暗号の安全性証明の限界について ○高橋大樹・長谷川真吾・磯辺秀司・小泉英介・静谷啓樹（東北大）  IT2014-67 ISEC2014-80 WBS2014-59 |
|
| 抄録 | （和） | 本稿では, 準同型暗号を対象として, 安全性証明の根拠となり得る言語の複雑さを評価することで, 安全性証明の限界について検討する. 具体的には, 任意の二項組$(b,c)$が与えられたとき, $c$が平文$b$の暗号文になっているかどうかを判定する問題(暗号文検証問題)の複雑さが$mathbf{NP}$の内部階層のLow階層で特徴付けられる場合について, 準同型暗号方式に対する安全性証明の限界がLow階層で特徴づけられることを示す. さらに, 暗号文検証問題が統計的ゼロ知識証明を持つ言語のクラス $SZK$ で特徴付けられる場合についても同様の考察を行い, この場合については, 安全性証明の限界が $SZK$ と $AMcapcoAM$ の中間に位置する程度のクラスで特徴付けられることを示す. |
| （英） | 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 $mathbf{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 $AMcapcoAM$. |
|
| キーワード | （和） | 準同型暗号 / 安全性証明 / Low階層 / 統計的ゼロ知識証明 / / / / |
| （英） | homomorphic encryption / security proof / low hierarchy / statistical zero-knowledge / / / / | |
| 文献情報 | 信学技報, vol. 114, no. 471, ISEC2014-80, pp. 33-38, 2015年3月. | |
| 資料番号 | ISEC2014-80 | |
| 発行日 | 2015-02-23 (IT, ISEC, WBS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IT2014-67 ISEC2014-80 WBS2014-59 |
|
| 研究会情報 | |
| 研究会 | ISEC IT WBS |
| 開催期間 | 2015-03-02 - 2015-03-03 |
| 開催地（和） | 北九州市立大学 ひびきのキャンパス |
| 開催地（英） | The University of Kitakyushu |
| テーマ（和） | IT・ISEC・WBS合同研究会 |
| テーマ（英） | joint meeting of IT, ISEC, and WBS |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2015-03-ISEC-IT-WBS |
| 本文の言語 | 日本語 |
| タイトル（和） | 準同型暗号の安全性証明の限界について |
| サブタイトル（和） | |
| タイトル（英） | On the Limit of Security Proof for Homomorphic Encryption |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 準同型暗号 / homomorphic encryption |
| キーワード(2)（和/英） | 安全性証明 / security proof |
| キーワード(3)（和/英） | Low階層 / low hierarchy |
| キーワード(4)（和/英） | 統計的ゼロ知識証明 / statistical zero-knowledge |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 高橋 大樹 / Daiki Takahashi / タカハシ ダイキ |
| 第1著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 長谷川 真吾 / Shingo Hasegawa / ハセガワ シンゴ |
| 第2著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 磯辺 秀司 / Shuji Isobe / イソベ シュウジ |
| 第3著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 小泉 英介 / Eisuke Koizumi / コイズミ エイスケ |
| 第4著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第5著者 氏名（和/英/ヨミ） | 静谷 啓樹 / Hiroki Shizuya / シズヤ ヒロキ |
| 第5著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2015-03-02 14:05:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | IT2014-67, ISEC2014-80, WBS2014-59 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | no.470(IT), no.471(ISEC), no.472(WBS) |
| ページ範囲 | pp.33-38 |
| ページ数 | 6 |
| 発行日 | 2015-02-23 (IT, ISEC, WBS) |
[研究会発表申込システムのトップページに戻る]