5
$\begingroup$

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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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" :) $\endgroup$
    – Lev Reyzin ♦
    Nov 11, 2010 at 21:02
  • $\begingroup$ 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. $\endgroup$
    – Aaron Roth
    Nov 11, 2010 at 21:10
4
$\begingroup$

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.

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.