The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Mari f menjadi fungsi penyulitan satu sama satu. Diberi f(m) dan rentetan K, bolehkah kita dengan cekap menentukan sama ada m mengandungi K sebagai subrentetan atau tidak? Kami menyiasat kerumitan pengiraan masalah ini, dan menunjukkan bahawa ia bersamaan dengan bukan sahaja pengkomputeran f-1 tetapi juga mengira bilangan K terkandung sebagai subrentetan dalam m. Oleh itu ia tidak ditentukan dalam masa polinomial jika f sebenarnya adalah sehala.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Takako ITO, Hiroki SHIZUYA, "On the Difficulty of Searching for a String without Decryption" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 1, pp. 134-137, January 1999, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_1_134/_p
Salinan
@ARTICLE{e82-a_1_134,
author={Takako ITO, Hiroki SHIZUYA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Difficulty of Searching for a String without Decryption},
year={1999},
volume={E82-A},
number={1},
pages={134-137},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={January},}
Salinan
TY - JOUR
TI - On the Difficulty of Searching for a String without Decryption
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 134
EP - 137
AU - Takako ITO
AU - Hiroki SHIZUYA
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1999
AB - 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.
ER -