9
$\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
  • 4
    $\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
  • 3
    $\begingroup$ @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). $\endgroup$ – Joshua Grochow May 6 '13 at 20:42
3
$\begingroup$

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

$\endgroup$
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.