# Consequences of OWFs for Complexity

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).

• Have you checked the literature on Impagliazzo's worlds? – Kaveh May 5 '13 at 16:50
• @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}$. – Sasho Nikolov May 5 '13 at 17:36
• Thomas, there are quite a few cryptographic lowerbounds for efficient PAC learning. I believe they are hinted in Impagliazzo's five worlds paper – Sasho Nikolov May 5 '13 at 22:02
• 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. – MCH May 6 '13 at 17:50
• @MarzioDeBiasi: $P \neq UP$ iff OWFs exist is for the "structural complexity" kind of OWFs (injective poly-time computable functions with no poly-time inverse). The kind of OWFs needed for crypto, as in the question, seem quite a bit stronger (requiring non-invertibility by randomized or non-uniform adversaries on average-case inputs). – Joshua Grochow May 6 '13 at 20:42