13
$\begingroup$

There is an old trick for writing down an algorithm that, if P = NP, solves SAT in polynomial time. Essentially, one lists all polynomial time machines and multi-tasks over them.

Is there an analogous trick for one-way functions (or even one-way trapdoor functions)? That is, can we write down a function that, if one-way functions exist, is necessarily a one-way function?

There seems to be no easy way to mimic the P = NP trick. In that case, we can quickly recognize a solution when we get one. But if I multi-task over all polynomial time functions, there's no obvious way to recognize a one-way function when I arrive at one.

If the answer to the above question is no, is there some kind of argument why we can't do it? Maybe writing down such a function would somehow prove that one-way functions exist?

$\endgroup$
  • $\begingroup$ Hi Timothy Chow, maybe you can help and point to a link where the trick for writing down an algorithm, that if P = NP, solves SAT in polynomial time, is formalized? Thanks allot $\endgroup$ – Avi Tal Sep 15 '18 at 11:20
  • $\begingroup$ @AviTal See for example this: scholarpedia.org/article/Universal_search $\endgroup$ – Vanessa Sep 16 '18 at 13:10
11
$\begingroup$

Yes, such a function was found by Levin himself, published somewhat recently:

The tale of one-way functions. Problems of Information Transmission (= Problemy Peredachi Informatsii), 39(1):92-103, 2003.

$\endgroup$
  • $\begingroup$ Thanks! Using Google Scholar, I was able to use this reference to find a reference for a complete public key cryptosystem, by Grigoriev, Hirsch, and Pervyshev, Groups-Complexity-Cryptology 1 (2009), 1-12. $\endgroup$ – Timothy Chow Sep 15 '18 at 1:54
  • $\begingroup$ Could you please explain details of this function? As why it aborts after n^2 steps, why to 'preserve a copy of the program prefix and force it, as well as the input length, on the output' and what 'only at places where such possible extension is unique' means exactly. I don't know if this deserves a separate question. $\endgroup$ – galmeida Sep 6 at 1:46
  • $\begingroup$ @BjørnKjos-Hanssen cstheory.stackexchange.com/questions/44496/… $\endgroup$ – galmeida Sep 8 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.