On the Difficulty of Searching for a String without Decryption

摘要

Let f be a one-to-one encryption function. Given f(m) and a stringK, can we efficiently determine whether m contains K as a substringor not? We investigate the compu- tational complexity of thisproblem, and show that it is equiv- alent to not only computingf~(-1) but also counting the number of K contained as substrings inm. Thus it is not determined in polynomial-time if f is in factone-way.