文献

J-GLOBAL ID：200902262106740247   整理番号：09A0848719

量子アルゴリズムによるFeistel型暗号の安全性解析

Quantum Distinguisher for Feistel Ciphers

著者 (2件)： 桑門秀典 (神戸大 大学院工学研究科) ,  森井昌克 (神戸大 大学院工学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 109  号： 143(IT2009 6-31)  ページ： 131-135  発行年： 2009年07月16日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 量子計算機の優れた計算能力は,公開鍵暗号だけでなく,共通鍵暗号の安全性にも大きな影響を与える。Groverの量子探索アルゴリズムは,nビットの鍵を0(2^n/2)の計算量で探索することができる。この攻撃は,共通鍵暗号の内部構造に依存しない汎用的な攻撃である。本研究では,共通鍵暗号の内部構造として広く用いられているFeistel構造とランダム置換の識別困難性を量子アルゴリズムを用いて検討する。もしランダム置換の識別困難であれば,そのFeistel構造には理論的な脆弱性がないことが保証されるため,この識別困難性は古典アルゴリズムの観点から盛んに研究が行われきた。本論文では,2ラウンドと3ラウンドのFeistel構造は,量子アルゴリズムを用いると,古典アルゴリズムのときよりも少ない計算量でランダム置換と識別可能であることを示す。(著者抄録)

シソーラス用語： *暗号 ,  安全解析 ,  *コンピュータセキュリティ ,  *コンピュータ ,  公開鍵暗号 ,  秘密鍵暗号 ,  *計算量 ,  計算機アルゴリズム ,  性質 ,  *量子コンピュータ ,  量子アルゴリズム
準シソーラス用語： *Feistel型暗号 ,  安全性解析 ,  共通鍵暗号 ,  脆弱性 ,  *量子計算機

分類 (4件)： 符号理論  (ND02030R) ,  データ保護  (JD01020V) ,  その他の計算機  (JC06020B) ,  計算理論  (JB02000A)

引用文献 (6件)：

• AARONSON, S. Quantum lower bound for the collision problem. Proceedings of the 34th ACM Symposium on the Theory of Computing, 2002. 2002, 635-642
• BRASSARD, G. Quantum algorithm for the collision problem. quant-ph/9705002. 1997
• GROVER, L. K. A fast quantum mechanical algorithm for database search. Proceedings of The 28th ACM Symposium on the Theory of Computing, 1996. 1996, 212-219
• LUBY, M. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing. 1998, 17, 2
• MAURER, U. M. A simplified and generalized treatment of Luby-Rackoff pseudorandom permutation generators. Advances in Cryptology-EUROCRYPT'92. 1993, 239-255

タイトルに関連する用語 (3件)： 量子アルゴリズム ,  暗号 ,  安全性解析