10
$\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).

Improve this question
$\endgroup$
11
  • 4
    $\begingroup$ Have you checked the literature on Impagliazzo's worlds? $\endgroup$
    – Kaveh
    May 5, 2013 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, 2013 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, 2013 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$
    – Mahdi Cheraghchi
    May 6, 2013 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, 2013 at 20:42

2 Answers 2

Reset to default
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

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.