Are there other asymmetric-time permutations than x^3 (mod p)?

Question

I've been using asymmetric-time bijective functions (or permutations) for several practical uses. I've applied them to solve problems in software-attestation and proof of unique blockchain storage.

An asymmetric-time permutation is basically a public permutation F that takes a lot of time to perform in one direction (expensive direction) and very short time in the inverse direction (cheap direction). The most interesting property of an a-t permutation is the asymmetry ratio, which is the (average) ratio between expensive and cheap computation times.

This is a practical construction that is evaluated both ways in a protocol so the expensive computation must not be unfeasible: it may take 1 second of computation for a target CPU. Generally the expensive direction time is chosen so that is takes more than the time a response must be sent by a prover in an interactive challenge-response protocol.

One of the best a-t permutations I found is $f^{-1}(x)= x^3 (\bmod p)$, where $p$ is a large prime. The ratio is $O(n)$, where $n$ is the number of bits in $p$.

Another desired property is that you cannot break F by pre-computing and then turn expensive evaluations into cheap ones. So the domain size must be $> 2^{64}$.

The a-t function may have other desired properties, such as the ability to probabilistically test if $f^{-1}(x) = y$, given only a part of $x$ chosen by the challenger.

Are there other a-t functions with comparable or higher asymmetry ratios?

Candidates may be a trapdoor function such that the trapdoor is unknown and no third-party trust is required (nothing up my sleeve number). In other words, the verification logic must be public, and not limited to the challenger.

Note: I think I'm the first to specifically focus on a-t functions and its practical applications, but let me know if you find any prior mention.

Answer 1

One approach is suggested by the ideas introduced by this paper. I'll spell them out for you:

• The verifier selects two large safe primes $p, q$ (that is, primes where $(p-1)/2$ and $(q-1)/2$ are also prime), the value $n = p \times q$, an integer $z$, and a quadratic residue ($\bmod n$) $a$.

• The challenge (the "hard direction") is, given the values $n, z$ and $a$, compute $a^{2^{z}} \bmod n$

• The verification (the "easy direction") is, given $a^{2^z} \bmod n$, recover $a$ (which is moderately easy to do, effectively an RSA operation, if you know the factorization of $n$).

This is a trapdoor function, but one which the verifier knows the trap door (and doesn't need to rely on anyone else). This works fine if we have a unique verifier (as in a challenge-response system); it's less useful if the verification logic needs to be public.

And, the function is a permutation, if we restrict ourselves to the quadratic residues modulo $n$.

The point of this construction is that the asymmetry ratio can be as large as desired; it's effectively $O(z / \log n)$, as $z$ is an arbitrary integer, we can set this to whatever we feel like.