4
$\begingroup$

I've been using "asymetric-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.

$\endgroup$
  • $\begingroup$ Would the 5th power also work fairly well in this context? $\endgroup$ – Mok-Kong Shen Feb 18 '16 at 14:47
  • $\begingroup$ A thread "How to take integer cube root?" of yesterday in reddit.com/r/crypto/ seems to eventually have some relevance to your issue. (I have only taken a superficial look at it.) $\endgroup$ – Mok-Kong Shen Feb 18 '16 at 15:05
  • $\begingroup$ Someone doing extended euclidean algorithm with $3$ and $p-1$ as an input would significantly change such an asymmetry ratio. Do not wait it to happen, learn RSA. $\endgroup$ – Vadym Fedyukovych Feb 18 '16 at 16:54
  • $\begingroup$ A function with a slightly better asymmetry ratio would be $f^{-1}(x) = x^2 \bmod p$; this is a permutation if we are allowed to restrict $x$ to Quadratic Residues (and $p=3 \bmod 4$) $\endgroup$ – poncho Feb 20 '16 at 0:16
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I had read that paper. But the verification logic needs to be public. I will emphasize that in the question. thanks $\endgroup$ – SDL Feb 20 '16 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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