| 講演名 | 2004/3/8 計算量の下界と暗号の安全性について(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会) 岡本 龍明, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では、最近の我々の結果[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. |
| キーワード(和) | 計算量理論 / 計算量下界 / P vs NP / 暗号 |
| キーワード(英) | computational complexity / computational lower bound / P vs NP / cryptography |
| 資料番号 | IT2003-71,ISEC2003-111,WBS2003-189 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2004/3/8(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 計算量の下界と暗号の安全性について(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会) |
| サブタイトル（和） | |
| タイトル（英） | Computational Lower Bounds and the Security Of Cryptography |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 計算量理論 / computational complexity |
| キーワード(2)（和/英） | 計算量下界 / computational lower bound |
| キーワード(3)（和/英） | P vs NP / P vs NP |
| キーワード(4)（和/英） | 暗号 / cryptography |
| 第 1 著者 氏名（和/英） | 岡本 龍明 / Tatsuaki Okamoto |
| 第 1 著者 所属（和/英） | NTT情報流通プラットフォーム研究所 NTT Laboratories |
| 発表年月日 | 2004/3/8 |
| 資料番号 | IT2003-71,ISEC2003-111,WBS2003-189 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 712 |
| ページ範囲 | pp.- |
| ページ数 | 2 |
| 発行日 | |