3
$\begingroup$

Down to what $k$ and how can we devise a practical, public, efficiently computable One Way Permutation $P$ of the set $\{0,1\}^k$ of $k$-bit bitstrings, if possible without involving a trusted party for parameter setup ? Note: I want $P$ to be a permutation in the mathematical sense, and computationally hard to invert for some definition of that.


For values of $k$ starting at bout $2000$, we can use the assumed hardness of the Discrete Logarithm Problem (RSA also works if we trust a party to generate and publish an appropriate public key, and destroy any clue that could lead to factorization of the modulus).

For example, with the DLP, we find the smallest prime $p$ at least $\sqrt[3]{9}\,2^k$ such that $q=(p-1)/2$ is also prime, find the smallest $g$ at least $p/\pi$ such that $g^q\bmod p=1$, and define function $F$ over the set $\{1,2\dots q\}$ as $F(x)=\min\big(g^x\bmod p,p-(g^x\bmod p)\big)$. As far as we know, $F$ is an OWP over that set. We then use cycling to reduce $F$ to a permutation $P$ of $\{0,1\}^k$: we convert the input bitsring to integer, add one, apply $F$ and iterate (on average $\sqrt[3]{9}/2\approx1.04$ times) until the result is at most $2^k$, subtract one, convert back to bitstring.


Addition: I'll cowardly let the answer state its security claim. Informally, I'd be happy with a vague argument that more than $\min(2^n,2^{128})$ cycles of classical CPU are required for anything that should require more than $2^n$ evaluations in the forward direction, like finding a bitstring $x$ with the first $n$ bits of $P(x)$ all-zero (or other arbitrary $n$-bit value defined independently of the definition of $P$).

Motivation: I read that OWPs are more useful than OWFs. I wonder if that matters in practice. I reason that if we can't get $k$ down to say 256, we could as well use as a practical equivalent of a OWP a hash of $k$ bit (and same input size); it's most likely not a OWP, but it can't be computationally distinguished from that if the hash is secure.

$\endgroup$
  • 1
    $\begingroup$ Since you are in the concrete security setting, you should state the concrete $(t,e)$ bounds you want... $\endgroup$ – fkraiem Dec 20 '17 at 8:51
  • $\begingroup$ Is the above question different from this one? $\endgroup$ – Occams_Trimmer Dec 21 '17 at 13:03
  • 1
    $\begingroup$ @Occams_Trimmer: not much. This new one asks for a bound on $k$, when the other sets it (because I had an application in mind, which ultimately ended up with FPE). And the new one remains simpler (even after I spoiled that with example and addition). But that's the same overall subject and author :-) $\endgroup$ – fgrieu Dec 21 '17 at 14:56
  • $\begingroup$ This doesn't really make sense as asked, because the term ‘one-way permutation’ itself implies the asymptotic setting, about the shape of the growth curve of algorithm costs as $k$ grows. When you enter the realm of the concrete setting, ‘preimage-resistant’ is a little more appropriate, but the security notion is a bit different. So even if we did pick a fixed member of a preimage-resistant permutation family on $\{0,1\}^k$, that probably wouldn't get us anything practical out of the theory you cited. $\endgroup$ – Squeamish Ossifrage Dec 23 '17 at 22:42
1
$\begingroup$

Here is an outline of a system that would yield $k \approx 256$.

Let us select an elliptic curve (based on a prime field of size $N \approx 2^{256}$ with:

  • Is secure, and has twist security (that is, the discrete log problem on the curve and on its twist is infeasible)

  • Has a single point of order two (the $x=y=0$ point)

  • Both the curve, and its twist form a cyclic group (which is mostly a consequence of the previous two assumptions)

We'll select a generator of the curve $G$ and a generator of the twist $G^*$ (note: if you are basing this on Curve25519, then the conventional $g=9$ does not work, as that generates a prime-order subgroup, not the entire curve)

Then, if the order of the curve is $q$ and the order of the twist is $q^*$, then every value between 1 and $N-1$ can be represented as either (but not both):

  • The $x$ coordinate of a point $kG$, for some $1 \le k < q/2$

  • The $x$ coordinate of a twisted point $kG^*$, for some $1 \le k < q^*/2$

So, if we map the integers $k \in [1, q/2)$ to the $x$ coordinate of $kG$, and the integers $k \in [q/2, q/2 + q^*/2)$ to the $x$ coordinate of $(k - q/2 + 1)G^*$, I believe that gives a hard-to-invert permutation of the integers in the range $[1, N-1]$. And, you can use the tricks you have listed to make that down into a slightly smaller range $[0, 2^k)$.

Do you see any obvious problems with this?

$\endgroup$
  • $\begingroup$ I had to look for the definition of twist in the Handbook of Elliptic and Hyperelliptic Curve Cryptography, thus I'm (at least for now) miles from being able to detect even the most obvious problem, if any. $\endgroup$ – fgrieu Dec 22 '17 at 11: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.