<p>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.</p>

<p>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, <a href="http://portal.acm.org/citation.cfm?id=167197" rel="nofollow">http://portal.acm.org/citation.cfm?id=167197</a></p>

<p>"Cryptographic limitations on learning Boolean formulae and finite automata" -- Kearns, <a href="http://portal.acm.org/citation.cfm?id=174647&amp;dl=GUIDE" rel="nofollow">http://portal.acm.org/citation.cfm?id=174647&amp;dl=GUIDE</a>,</p>

<p>and many more recent results. </p>

CC BY-SA 2.5
2010-11-11T21:02:35.607Z
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
CC BY-SA 2.5
2010-11-11T21:10:46.440Z
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
CC BY-SA 2.5
2010-11-11T19:42:46.547Z
2010-11-11T19:42:46.547Z
Aaron Roth
<p>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"?</p>

<p>If so, I'll construct the following problem:</p>

<p>Let's first assume that one-way functions exist. Then, by the result of <a href="https://cstheory.stackexchange.com/q/2839/873#2848">Håstad <em>et al</em>.</a>, cryptographically-secure pseudo-random bit generators exist. </p>

<p>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 <strong>approximate</strong> $s$ given $(1^n,y)$.</p>

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

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

CC BY-SA 2.5
2010-11-11T21:02:08.683Z
2010-11-11T21:02:08.683Z
2017-04-13T12:32:28.167Z
Sadeq Dousti
<p>This question is inspired by a question posed by Shiva Kintali, <a href="https://cstheory.stackexchange.com/questions/2326/hardness-of-approximation-assuming-np-conp">Hardness of approximation assuming NP != coNP</a>
<a href="https://cstheory.stackexchange.com/questions/2326/hardness-of-approximation-assuming-np-conp"></a>. 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.</p>

<blockquote>
  <p>Are there any hardness of approximation results assuming the existence of one-way functions? </p>
</blockquote>

<p>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.</p>

<cc.complexity-theory><cr.crypto-security><one-way-function>
Hardness of approximation assuming the existence of one-way functions
Mohammad Al-Turkistany
# Hardness of approximation assuming the existence of one-way functions

(Asked by: username_0 on 2010-11-11)

This question is inspired by a question posed by Shiva Kintali, [Hardness of approximation assuming NP != coNP](https://cstheory.stackexchange.com/questions/2326/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.

**Tags:** cc.complexity-theory, cr.crypto-security, one-way-function


---

## 2 answers

### Answer by username_1 on 2010-11-11. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_2**: 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" :)  
> **username_1**: 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.  

---

### Answer by username_3 on 2010-11-11. Score: 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*.](https://cstheory.stackexchange.com/q/2839/873#2848), 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.


---

