14
$\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?

Improve this question
$\endgroup$
2
  • $\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, 2018 at 11:20
  • $\begingroup$ @AviTal See for example this: scholarpedia.org/article/Universal_search $\endgroup$
    – Vanessa
    Sep 16, 2018 at 13:10

1 Answer 1

Reset to default
12
$\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.

Improve this answer
$\endgroup$
3
  • $\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, 2018 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, 2019 at 1:46
  • $\begingroup$ @BjørnKjos-Hanssen cstheory.stackexchange.com/questions/44496/… $\endgroup$
    – galmeida
    Sep 8, 2019 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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