<p>Yes, such a function was found by Levin himself, published somewhat recently:</p>

<p><a href="https://arxiv.org/abs/cs/0012023" rel="noreferrer">The tale of one-way functions</a>. Problems of Information Transmission (= Problemy Peredachi Informatsii), 39(1):92-103, 2003.</p>

CC BY-SA 4.0
2018-09-15T01:54:18.670Z
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.
Timothy Chow
CC BY-SA 4.0
2019-09-06T01:46:47.597Z
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.
galmeida
CC BY-SA 4.0
2019-09-08T01:00:09.433Z
@BjørnKjos-Hanssen https://cstheory.stackexchange.com/questions/44496/describe-levins-tile-expansion-one-way-functon-in-layman-terms
galmeida
CC BY-SA 4.0
2018-09-15T00:05:37.050Z
2018-09-15T00:16:37.957Z
2018-09-15T00:16:37.957Z
Bjørn Kjos-Hanssen
<p>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.</p>

<p>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?</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 4.0
2018-09-15T11:20:25.120Z
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
Avi Tal
CC BY-SA 4.0
2018-09-16T13:10:37.567Z
@AviTal See for example this: http://www.scholarpedia.org/article/Universal_search
Vanessa
<universal-computation><one-way-function>
Function that is guaranteed to be one-way if one-way functions exist?
Timothy Chow
# Function that is guaranteed to be one-way if one-way functions exist?

(Asked by: username_0 on 2018-09-14)

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?

**Tags:** universal-computation, one-way-function

> **Comments:**
> **username_1**: Hi username_0, 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  
> **username_2**: @AviTal See for example this: http://www.scholarpedia.org/article/Universal_search  

---

## 1 answers

### Answer by username_3 on 2018-09-15. Score: 12 | Accepted answer

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

[The tale of one-way functions](https://arxiv.org/abs/cs/0012023). Problems of Information Transmission (= Problemy Peredachi Informatsii), 39(1):92-103, 2003.

> **Comments:**
> **username_0**: 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.  
> **username_4**: 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.  
> **username_4**: @BjørnKjos-Hanssen https://cstheory.stackexchange.com/questions/44496/describe-levins-tile-expansion-one-way-functon-in-layman-terms  

---

