計算量の下界と暗号の安全性について
-
- 岡本 龍明
- NTT情報流通プラットフォーム研究所
書誌事項
- タイトル別名
-
- Computational Lower Bounds and the Security of Cryptography
この論文をさがす
説明
本稿では、最近の我々の結果[1]について簡単に紹介する。まず、P \not=NPのような多項式時間の計算量の下界を示すためには、超多項式時間の計算能力が必要であることなどを示す。また、この結果に基づき、標準的な暗号のモデルにおいて、計量的暗号の安全性を示すことが不可能であることを示す。
This manuscript briefly introduce our recent result [1]. It shows that the proof complexity (minimum computational complexity of proving formally or asymptotically of "P \not=NP" is super-polynomial-time with respect to a theory T, which is a consistent extension of Peano Arithmetic (PA), and PTM-\omega-consistent, where the PTM-\omega-consistency is a polynomial-time Turing machine (PTM) version of \omega-consistency. In other words, to prove P \not=NP (by any technique requires super-polynomial-time computational power over T. This result implies that P \not= NP is formally unproven in PTM-\omega-consistent theory T. We also show that to prove the independence of P vs NP from T by proving the PTM-\omega-consistency of T requires super-polynomial-time computational power. Based on this result, we show that the security of any computational cryptographic scheme is unprovable in the standard setting of modern cryptography, where an adversary is modeled as a polynomial-time Turing machine.
収録刊行物
-
- 電子情報通信学会技術研究報告. ISEC, 情報セキュリティ
-
電子情報通信学会技術研究報告. ISEC, 情報セキュリティ 103 (712), 87-88, 2004-03-08
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1573105977177344512
-
- NII論文ID
- 110003296344
-
- NII書誌ID
- AN10060811
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles
