<p>This is a late response. </p>

<p>First, to correct what you wrote: 
Cryptographic pseudorandomness (the one obtained from OWFs) doesn't have enough stretch to derandomize "naturally defined" computational complexity classes. In an old paper (beginning of 80s) Andrew Yao shows some subexponential time derandomization for RP etc using these objects (btw, this is immediate), but no stronger derandomization is known. Note, that in terms of fooling power cryptographic PRGs are stronger than what you need for derandomization but at the same time in terms of their stretch are weaker than their typical complexity-theoretic analogues (this follows by the order of quantification in the definition of the PRGs). </p>

<p>As Sasho Nikolov mentioned there are plenty of examples in PAC learning. Have a look at a very early paper by Kearns and Valiant on the impossibility of learning formulas and automata (follow in google scholar the references from there). Also, there are consequences in proof complexity through interpolation -- have a look in the also early works by Jan Krajicek and Pavel Pudlak. However, I am not sure if you consider these to be complexity-theoretic implications (but I do). </p>

<p>-- Periklis</p>

CC BY-SA 4.0
2019-08-08T16:27:58.917Z
2019-08-08T16:27:58.917Z
user17164
<p>Integer factorization is widely considered the best candidate for one way functions and it is in TFNP. From the abstract of this paper, <a href="http://people.cs.uchicago.edu/~fortnow/papers/phq.pdf" rel="nofollow">Does the Polynomial Hierarchy Collapse if Onto
Functions are Invertible?</a>, 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.</p>

CC BY-SA 3.0
2013-05-05T20:19:10.473Z
2013-05-05T20:35:25.617Z
2013-05-05T20:35:25.617Z
Mohammad Al-Turkistany
<p>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: <strong>What are the <em>complexity-theoretic</em> consequences of the existence of one-way functions?</strong> 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?</p>

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

CC BY-SA 3.0
2013-05-05T15:04:45.767Z
Yes, existence of OWFs implies that the polynomial hierarchy is infinite since P=NP iff P=PH.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-05-05T15:39:25.303Z
@MohammadAl-Turkistany I don't see the backward direction be necessarily true. For example, it could be that $P \neq NP$ but polynomial hierarchy collapses on the second level, for example.
chazisop
CC BY-SA 3.0
2013-05-05T16:50:39.893Z
Have you checked the literature on Impagliazzo's worlds?
Kaveh
CC BY-SA 3.0
2013-05-05T16:51:37.570Z
In Descriptive Complexity, by Immerman Corollary 7.23 implies that P=NP iff P=PH. Have look at this post: http://cstheory.stackexchange.com/questions/5463/can-one-amplify-p-np-beyond-p-ph
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-05-05T17:04:46.087Z
@chazisop P=PH is stronger than the polynomial hierarchy collapsing. If P=NP then we can prove that P=PH by induction on the level, and the backward direction is trivial since NP is a subset of PH.
Yuval Filmus
CC BY-SA 3.0
2013-05-05T17:36:35.120Z
@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
CC BY-SA 3.0
2013-05-05T18:48:50.550Z
@Kaveh It's difficult to find what I want. Although I found papers relating OWFs to zero-knowledge. Any pointers? Thanks.
Thomas Steinke
CC BY-SA 3.0
2013-05-05T22:02:31.623Z
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
CC BY-SA 3.0
2013-05-05T22:28:17.480Z
As far as I know "$P = UP \Rightarrow^? PH$ collapses" is still an open problem. ($P \neq UP$ if and only if OWFs exist)
Marzio De Biasi
CC BY-SA 3.0
2013-05-06T17:50:09.597Z
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.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-05-06T20:42:08.607Z
@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
<cc.complexity-theory><reference-request><complexity-classes><cr.crypto-security><one-way-function>
Consequences of OWFs for Complexity
Thomas Steinke
# Consequences of OWFs for Complexity

(Asked by: username_0 on 2013-05-05)

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

**Tags:** cc.complexity-theory, reference-request, complexity-classes, cr.crypto-security, one-way-function
> **Comments:**
> **username_1**: Yes, existence of OWFs implies that the polynomial hierarchy is infinite since P=NP iff P=PH.  
> **username_2**: @MohammadAl-Turkistany I don't see the backward direction be necessarily true. For example, it could be that $P \neq NP$ but polynomial hierarchy collapses on the second level, for example.  
> **username_3**: Have you checked the literature on Impagliazzo's worlds?  
> **username_1**: In Descriptive Complexity, by Immerman Corollary 7.23 implies that P=NP iff P=PH. Have look at this post: http://cstheory.stackexchange.com/questions/5463/can-one-amplify-p-np-beyond-p-ph  
> **username_4**: @chazisop P=PH is stronger than the polynomial hierarchy collapsing. If P=NP then we can prove that P=PH by induction on the level, and the backward direction is trivial since NP is a subset of PH.  
> **username_5**: @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}$.  
> **username_0**: @Kaveh It's difficult to find what I want. Although I found papers relating OWFs to zero-knowledge. Any pointers? Thanks.  
> **username_5**: Thomas, there are quite a few cryptographic lowerbounds for efficient PAC learning. I believe they are hinted in Impagliazzo's five worlds paper  
> **username_6**: As far as I know "$P = UP \Rightarrow^? PH$ collapses" is still an open problem. ($P \neq UP$ if and only if OWFs exist)  
> **username_7**: 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.  
> **username_8**: @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).  

---

## 2 answers

### Answer by username_9 on 2019-08-08. Score: 3

This is a late response.

First, to correct what you wrote:
Cryptographic pseudorandomness (the one obtained from OWFs) doesn't have enough stretch to derandomize "naturally defined" computational complexity classes. In an old paper (beginning of 80s) Andrew Yao shows some subexponential time derandomization for RP etc using these objects (btw, this is immediate), but no stronger derandomization is known. Note, that in terms of fooling power cryptographic PRGs are stronger than what you need for derandomization but at the same time in terms of their stretch are weaker than their typical complexity-theoretic analogues (this follows by the order of quantification in the definition of the PRGs).

As Sasho Nikolov mentioned there are plenty of examples in PAC learning. Have a look at a very early paper by Kearns and Valiant on the impossibility of learning formulas and automata (follow in google scholar the references from there). Also, there are consequences in proof complexity through interpolation -- have a look in the also early works by Jan Krajicek and Pavel Pudlak. However, I am not sure if you consider these to be complexity-theoretic implications (but I do).

-- Periklis


---

### Answer by username_1 on 2013-05-05. Score: 2

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?](http://people.cs.uchicago.edu/~fortnow/papers/phq.pdf), 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.


---

