10

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

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
Thomas
  • 2,803
  • 19
  • 29
  • Yes, existence of OWFs implies that the polynomial hierarchy is infinite since P=NP iff P=PH. – Mohammad Al-Turkistany May 05 '13 at 15:04
  • @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 May 05 '13 at 15:39
  • 4
    Have you checked the literature on Impagliazzo's worlds? – Kaveh May 05 '13 at 16:50
  • 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 May 05 '13 at 16:51
  • @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 May 05 '13 at 17:04
  • 2
    @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 05 '13 at 17:36
  • @Kaveh It's difficult to find what I want. Although I found papers relating OWFs to zero-knowledge. Any pointers? Thanks. – Thomas May 05 '13 at 18:48
  • 2
    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 05 '13 at 22:02
  • 2
    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 May 05 '13 at 22:28
  • 4
    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 May 06 '13 at 17:50
  • 3
    @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 06 '13 at 20:42

2 Answers2

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

user17164
  • 351
  • 2
  • 4
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?, 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.

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149