On the Difficulty of Searching for a String without Decryption (Special Section on Cryptography and Information Security)
スポンサーリンク
概要
- 論文の詳細を見る
Let f be a one-to-one encryption function. Given f(m) and a string K, can we efficiently determine whether m contains K as a substring or not? We investigate the computational complexity of this problem, and show that it is equivalent to not only computing f^<-1> but also counting the number of K contained as substrings in m. Thus it is not determined in polynomial-time if f is in fact one-way.
- 社団法人電子情報通信学会の論文
- 1999-01-25
著者
-
Ito Takehiro
Graduate School Of Information Sciences Tohoku University
-
SHIZUYA Hiroki
Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku Un
-
Ito T
Tohoku Univ. Sendai‐shi Jpn
-
ITO Takako
Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku Un
-
Shizuya Hiroki
Department Of Computer And Mathematical Sciences Graduate School Of Information Sciences Tohoku Univ
関連論文
- Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings
- Numerical Simulation of Effect of Wall in a Basic Pulse-Tube Refrigerator
- Numerical Analysis of Heat and Fluid Flow in Pulse Tube Refrigerator(Emerging Fields in Thermal Engineering)
- TED-AJ03-164 NUMERICAL ANALYSIS OF HEAT AND FLUID FLOW IN PULSE TUBE REFRIGERATOR
- NPMV-Complete Functions That Compute Discrete Logarithms and Integer Factorization
- Partitioning a Multi-Weighted Graph to Connected Subgraphs of Almost Uniform Size(Graph Algorithms,Foundations of Computer Science)
- Algorithms for Multicolorings of Partial ★-Trees (Special Issue on Selected Papers from LA Symposium)
- On the Difficulty of Searching for a String without Decryption (Special Section on Cryptography and Information Security)
- Making Cryptographic Primitives Harder
- Toward Separating Integer Factoring from Discrete Logarithm mod p(Foundations,Cryptography and Information Security)
- On the Polynomial Time Computability of Abstract Ray-Tracing Problems(Discrete Mathematics and Its Applications)
- Acquired Resistance to Infliximab Against Uveitis Due to Behcet's Disease After One Year of Administration
- Unexpected death of a patient with rheumatoid arthritis complicated by a cervical deformity
- An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree
- On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions
- On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions