2
$\begingroup$

I was reading Charles Bennett's Thermodynamics of Computer Science and a passage (p. 926) caught my eye

The construction of a reversible machine from an irreversible machine implies that the open question, of whether there exists a 1:1 function much easier to compute by an irreversible machine than by any reversible machine, is equivalent to the question of whether there is an easy 1:1 function with a hard inverse.

I was quite surprised the existence of an easy 1:1 function with a hard inverse was open, and even more surprised at how hard it seemed to find sources on this (though I'm very unfamiliar with this area, so it's wholly possible I was just searching the wrong things). Seeing as this paper is almost 40 years old, I was wondering if this question was still open, and whether any sources discuss it in more depth.

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ Is this different from the question of whether or not one-way permutations exist? $\endgroup$
    – Yonatan N
    Oct 26, 2021 at 23:08
  • $\begingroup$ @YonatanN This seems to be a weaker definition, as one-way functions allow for negligible error. So I suppose there's no way the problem has been answered positively, but it doesn't seem impossible that it's been answered negatively. Thank you for the reference though, it's much closer to anything I found, surprised I missed it! $\endgroup$
    – Alexander Tenenbaum
    Oct 26, 2021 at 23:14
  • $\begingroup$ Oh, it seems this is exactly the definition of worst-case one-way function, rather than the more usual average-case one-way function, the existence of which is known to be equivalent to P=NP, so I suppose it is open :) $\endgroup$
    – Alexander Tenenbaum
    Oct 26, 2021 at 23:20

1 Answer 1

Reset to default
4
$\begingroup$

Following some direction provided by Yonatan's comment it seems this is exactly the problem of the existence of a worst-case one-way function, which is equivalent to $P\ne NP$

Ref: A survey of one-way functions in complexity theory Alan L. Selman 1992

Edit: It seems this terminology may not be entirely unambiguous. As far as I can tell, there is the notion of a one-way (deterministic) function in computational complexity theory, which is the notion mentioned by Selman and the one closest to what I am looking for, and the much more common cryptographic notion of a one-way (probabilistic) function.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ $P \neq NP$ is not known to imply the existence of one-way functions. This is a long-standing open problem in computational complexity. $\endgroup$
    – Martin Berger
    Oct 27, 2021 at 11:47
  • 1
    $\begingroup$ @MartinBerger I know $P\ne NP$ does not imply the existence of the much more common average-case one-way functions, but sources I have found state that it does imply the existence of worst-case one-way functions (see the reference given). Is this wrong? $\endgroup$
    – Alexander Tenenbaum
    Oct 28, 2021 at 1:46
  • 1
    $\begingroup$ Fair enough. I overlooked the "worst case" qualifier. I've taken the liberty to highlight it in your answer. A definition of can be found in these lecture notes, is this the definition you had in mind? $\endgroup$
    – Martin Berger
    Oct 28, 2021 at 11:33
  • $\begingroup$ Interesting, that still seems like the wrong notion. This answer lead me to believe that worst-case OWFs were the deterministic equivalent of average-case ones, and the paper by Selman was linked elsewhere and seems to use the definition I was looking for. I'm asking about a deterministic polytime function with no deterministic polytime inverse (up to trivialities involving large inputs with small outputs), which seems to be what Selman discusses and claims exist iff $P\ne NP$, though it seems these may not be called worst case OWFs. $\endgroup$
    – Alexander Tenenbaum
    Oct 28, 2021 at 17:27
  • $\begingroup$ @JoshuaGrochow makes a slightly different claim: worst-case one-way functions exist if and only if $𝖯 \neq 𝖴𝖯$ with the relationship between $NP $ and $UP$ being open. $\endgroup$
    – Martin Berger
    Oct 28, 2021 at 21:35

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.