One-way functions with polynomial inverting complexity

Question

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$?

Answer 1

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:

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, though they are not exactly related to the question.

See the following references as well:

1. Pricing via Processing -or- Combatting Junk Mail by Dwork and Naor.
2. Moderately Hard Functions: From Complexity to Spam Fighting by Naor.
3. Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints by Dwork and Sahai.
4. Timed Commitments by Boneh and Naor.