<p>Some functions are conjectured to have that property, aptly called <em>moderately hard</em>. They were first proposed in the context of spam fighting, and then found their ways into more complicated applications, such as <em>concurrent zero knowledge</em> and <em>timed commitment</em>. They usually use a function of the form $f(x) = g^{2^{2^x}} \bmod N$, first suggested by <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.2151&amp;rep=rep1&amp;type=ps" rel="nofollow">Rivest, Shamir and Wagner</a>:</p>

<blockquote>
  <p>N is a product of two large primes. Without knowing the factorization of N, the best that is known is repeated squaring - a very sequential computation in nature.</p>
</blockquote>

<p>If $VNP=VP$, then factorization can be performed efficiently, and therefore we do not have to resort to repeated squaring. However, performing factorization for someone who does not know the factors of N incurs a polynomial overhead.</p>

<p>You may also be interested in the concept of <a href="http://www.springerlink.com/content/fr0l41857352q6m0/" rel="nofollow">feebly one-way functions</a>, though they are not exactly related to the question.</p>

<p>See the following references as well:</p>

<ol>
<li><a href="http://www.wisdom.weizmann.ac.il/~naor/PAPERS/pvp.ps" rel="nofollow">Pricing via Processing -or- Combatting Junk Mail</a> by Dwork and Naor.</li>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.2923&amp;rep=rep1&amp;type=pdf" rel="nofollow">Moderately Hard Functions: From Complexity to Spam Fighting</a> by Naor.</li>
<li><a href="http://groups.csail.mit.edu/cis/zk/DS.ps" rel="nofollow">Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints</a> by Dwork and Sahai.</li>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.108.7127&amp;rep=rep1&amp;type=pdf" rel="nofollow">Timed Commitments</a> by Boneh and Naor.</li>
</ol>

CC BY-SA 3.0
2011-07-11T15:59:11.030Z
Thank you. Do they break down if $VNP = VP$?
v s
CC BY-SA 3.0
2011-07-11T18:29:00.143Z
@v s: Sorry, forgot to mention that. See the edited answer.
Sadeq Dousti
CC BY-SA 3.0
2011-07-11T15:39:32.050Z
2011-07-12T01:23:14.953Z
2011-07-12T01:23:14.953Z
Sadeq Dousti
<p>Is there a trap-door-like function whose encoding complexity is polynomial time $n^{k_{1}}$ and inverting complexity(without secret key) is also a polynomial function in input length $n^{k_{2}}$ with $k_{1} &lt;&lt; k_{2}$ (say $k_{1} = 2$ and $k_{2}$ is unconditionally provable to be bounded below by $1000$)? What are the implications of such functions if $VNP = VP$?</p>

<cc.complexity-theory><complexity-classes><cr.crypto-security><one-way-function>
One-way functions with polynomial inverting complexity
v s
# One-way functions with polynomial inverting complexity

(Asked by: username_0 on 2011-07-11)

Is there a trap-door-like function whose encoding complexity is polynomial time $n^{k\_{1}}$ and inverting complexity(without secret key) is also a polynomial function in input length $n^{k\_{2}}$ with $k\_{1} << k\_{2}$ (say $k\_{1} = 2$ and $k\_{2}$ is unconditionally provable to be bounded below by $1000$)? What are the implications of such functions if $VNP = VP$?

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


---

## 1 answers

### Answer by username_1 on 2011-07-11. Score: 8

Some functions are conjectured to have that property, aptly called *moderately hard*. They were first proposed in the context of spam fighting, and then found their ways into more complicated applications, such as *concurrent zero knowledge* and *timed commitment*. They usually use a function of the form $f(x) = g^{2^{2^x}} \bmod N$, first suggested by [Rivest, Shamir and Wagner](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.2151&rep=rep1&type=ps):

> N is a product of two large primes. Without knowing the factorization of N, the best that is known is repeated squaring - a very sequential computation in nature.

If $VNP=VP$, then factorization can be performed efficiently, and therefore we do not have to resort to repeated squaring. However, performing factorization for someone who does not know the factors of N incurs a polynomial overhead.

You may also be interested in the concept of [feebly one-way functions](http://www.springerlink.com/content/fr0l41857352q6m0/), though they are not exactly related to the question.

See the following references as well:

1. [Pricing via Processing -or- Combatting Junk Mail](http://www.wisdom.weizmann.ac.il/~naor/PAPERS/pvp.ps) by Dwork and Naor.
2. [Moderately Hard Functions: From Complexity to Spam Fighting](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.2923&rep=rep1&type=pdf) by Naor.
3. [Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints](http://groups.csail.mit.edu/cis/zk/DS.ps) by Dwork and Sahai.
4. [Timed Commitments](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.108.7127&rep=rep1&type=pdf) by Boneh and Naor.

> **Comments:**
> **username_0**: Thank you. Do they break down if $VNP = VP$?  
> **username_1**: @username_0: Sorry, forgot to mention that. See the edited answer.  

---

