| Presentation | 2004/3/8 Computational Lower Bounds and the Security Of Cryptography Tatsuaki Okamoto, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | computational complexity / computational lower bound / P vs NP / cryptography |
| Paper # | IT2003-71,ISEC2003-111,WBS2003-189 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2004/3/8(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Computational Lower Bounds and the Security Of Cryptography |
| Sub Title (in English) | |
| Keyword(1) | computational complexity |
| Keyword(2) | computational lower bound |
| Keyword(3) | P vs NP |
| Keyword(4) | cryptography |
| 1st Author's Name | Tatsuaki Okamoto |
| 1st Author's Affiliation | NTT Laboratories() |
| Date | 2004/3/8 |
| Paper # | IT2003-71,ISEC2003-111,WBS2003-189 |
| Volume (vol) | vol.103 |
| Number (no) | 712 |
| Page | pp.pp.- |
| #Pages | 2 |
| Date of Issue | |