7
$\begingroup$

It it well-known that the existence of one-way functions is necessary and sufficient for much of cryptography (digital signatures, pseudorandom generators, private-key encryption, etc.). My question is: What are the complexity-theoretic consequences of the existence of one-way functions? For example, OWFs imply that $\mathsf{NP}\ne\mathsf{P}$, $\mathsf{BPP}=\mathsf{P}$, and $\mathsf{CZK}=\mathsf{IP}$. Are there other known consequences? In particular, do OWFs imply that the polynomial hierarchy is infinite?

I'm hoping to better understand the relationship between worst-case and average-case hardness. I'm also interested in results going the other way (i.e. complexity-theoretic results that would imply OWFs).

$\endgroup$
  • 4
    $\begingroup$ Have you checked the literature on Impagliazzo's worlds? $\endgroup$ – Kaveh May 5 '13 at 16:50
  • 2
    $\begingroup$ @MohammadAl-Turkistany so $\mathsf{P} \neq \mathsf{NP}$ implies $\mathsf{P} \neq \mathsf{PH}$. However it does not rule out a collapse: it's still consistent with $\mathsf{NP} = \mathsf{PH}$. $\endgroup$ – Sasho Nikolov May 5 '13 at 17:36
  • 2
    $\begingroup$ Thomas, there are quite a few cryptographic lowerbounds for efficient PAC learning. I believe they are hinted in Impagliazzo's five worlds paper $\endgroup$ – Sasho Nikolov May 5 '13 at 22:02
  • 2
    $\begingroup$ As far as I know "$P = UP \Rightarrow^? PH$ collapses" is still an open problem. ($P \neq UP$ if and only if OWFs exist) $\endgroup$ – Marzio De Biasi May 5 '13 at 22:28
  • 3
    $\begingroup$ I don't think existence of OWFs (according to their standard definition) implies $P=BPP$. For such derandomizations, we need pseudorandom generators with exponential stretch and OWFs are not suitable for such purposes. $\endgroup$ – MCH May 6 '13 at 17:50
2
$\begingroup$

Integer factorization is widely considered the best candidate for one way functions and it is in TFNP. From the abstract of this paper, Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?, it gives a relativized negative result by constructing an oracle under which TFNP functions are efficiently computable but the polynomial-time hierarchy is infinite. However, the result is not exactly what you are looking for.

$\endgroup$

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.