5

This question is inspired by a question posed by Shiva Kintali, Hardness of approximation assuming NP != coNP . Multiplication of two prime numbers of equal size is strong candidate for one-way function. We know the $P \ne NP$ does not imply the existence of one-way functions.

Are there any hardness of approximation results assuming the existence of one-way functions?

Ideally, assuming $P \neq NP$ would not be sufficient to prove such hardness of approximation result and we must assume that existence of one-way functions to prove such hardness of approximation result.

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

2 Answers2

6

The problem of learning in the PAC model is really just a problem of combinatorial optimization: with a large enough sample size, finding a function $f \in C$ which has low prediction error is equivalent to finding a function $f \in C$ which best classifies some finite sample from the distribution.

In this area, there are plenty of hardness of approximation results that depend on the existence of one-way functions. For example, "Cryptographic Hardness of Distribution Specific Learning" -- Kharitonov, http://portal.acm.org/citation.cfm?id=167197

"Cryptographic limitations on learning Boolean formulae and finite automata" -- Kearns, http://portal.acm.org/citation.cfm?id=174647&dl=GUIDE,

and many more recent results.

Aaron Roth
  • 9,870
  • 1
  • 43
  • 68
  • 1
    You can be even more direct and say RSA is hard to approximate. But actually your assumptions are stronger, as those papers assume specific functions are one-way. We can always just say "the inverses of one way functions are hard to approximate" :) – Lev Reyzin Nov 11 '10 at 21:02
  • I guess its not clear what the notion of "approximation" is when you are talking about inverting one-way functions directly. For learning, it is clear what approximation means: how well you approximate the optimal error rate. Even weak learning is hard, so these really are hardness of approximation results. – Aaron Roth Nov 11 '10 at 21:10
4

Are you after some problem $\Pi$ such that "it is hard to approximate $\Pi$ within a (possibly non-constant) factor $\alpha$ unless one-way functions do not existence"?

If so, I'll construct the following problem:

Let's first assume that one-way functions exist. Then, by the result of Håstad et al., cryptographically-secure pseudo-random bit generators exist.

Let $G(\cdot)$ be such a generator. On input $1^n$ (where $n \in \mathbb{N}$ is the security parameter), pick a random seed $s \in \{0,1\}^n$. Let $y$ be a polynomially bounded prefix of the output of $G(s)$. The problem is to approximate $s$ given $(1^n,y)$.

In the above context, you may interpret the word approximate arbitrarily; since by definition, $(1^n,y)$ does not leak any partial information about $s$.

The above result holds as long as one-way functions exist. Otherwise, by Håstad et al. result, cryptographically-secure pseudo-random bit generators do NOT exist, and therefore the approximation is no longer hard.

Community
  • 1
Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152