One-way permutation over a small interval?

Question

I am wondering what concrete computable functions we know that

• are a permutation over an integer interval of parameterizable size $s$, for relatively small $s$ starting circa $2^{64}$, to perhaps $2^{256}$; without loss of generality we'll translate the interval to $\{0\dots s-1\}$;
• are easily computable in the forward direction, but difficult to compute in the backward direction; I'm interested in maximizing the figure of merit $M$ defined as the ratio of the expected amount of work starting from a random point for one computation in backward direction, to that in forward direction (any necessary pre-computation starting from $s$ is included in said amounts of work).

Obvious remark: the merit $M$ can be no more than $s/2$, which corresponds to computing the inverse permutation by brute-forcing the forward direction. However I would be content with much lesser merit, and wonder what limit there is, be it theoretical or practical.

Any thought, idea, or reference?

Note: I want a permutation for any $s\ge2^{64}$, but a restriction to some mildly sparse subset of values for $s$ is enough, because a well-known technique allows to efficiently turn a permutation $\widehat P$ over an interval of size $\widehat s$ slightly larger than $s$ into the desired permutation $P$ over an interval of size $s$: for $x\in\{0\dots s-1\}$ we obtain $P(x)$ as the first $y_j<s$ with $y_0=\widehat P(x)$ and $y_{j+1}=\widehat P(y_j)$. The merit is not reduced too much: $M\ge s/\widehat s\cdot\widehat M$ holds, at least heuristically and if we ignore the work involved in finding the appropriate $\widehat s$ from $s$.

---

Side note (not part of the question): I actually want a family of permutations according to some key $K$ and indistinguishable from a random permutation, with some remaining security against inversion even when $K$ is available, as in that earlier question; but that's easily obtainable from a permutation $P$ as in the present question, and a fast keyed permutation (that is, a cipher) $C_K$ over $\{0\dots s-1\}$, by considering $C_K\circ P$; and we can construct $C_K$ from a block cipher with $\lceil\log_2s\rceil$-bit blocks, and the above technique. Also we can sort of stretch the figure of merit $M$ into sizable security against inversion even when $K$ is available, by iterating $C_{K_j}\circ P_j$ with derived keys ${K_j}$ as many times as practical given the performance constraints in the forward direction (with slightly different $P_j$, inasmuch as required to maintain the merit; and possibly lighter $C_{K_j}$).

Answer 1

How about this. Find an elliptic curve mod $p$, say $E:y^2=x^3+ax+b$ for some 256-bit prime $p$ such that the curve $E$ and its twist $E':dy^2=x^3+ax+b$ with $(\frac dp)_L=-1$ are both of prime order. Suppose the orders are $q$ and $r$, we have that $q+r=2p+2$ and corresponding to each $x$ there are either exactly two points $Q(x),-Q(x)$ on $E$ (exclusive) or two points $R(x),-R(x)$ on the twist $E'$. Fix generators $G$ and $G'$ for the two curves

Given input integer $t\in[0,p)$, map this to the union of intervals $t'\in(-q/2,-1]\cup[1,r/2)$ in the obvious way (the union has $p$ integers). If $t'$ lies in the first interval compute $t'G$ and output its $x$-coordinate; if $t'$ lies in the second interval compute $t'G'$ and output its $x$-coordinate.

Answer 2

You are looking for almost-prime-order cyclic groups $G$ of order $n$ that have an easily computed bijection $G \rightarrow \{0,1,2,\dots,n-1\}$, along with an estimate of how quickly discrete logarithms can be computed in $G$.

There seems to be two choices, a subgroup of $\mathbb{F}_p^*$ with $(p-1)/2$ prime, and the elliptic curve $E: Y^2 = X^3+1$ over the field $\mathbb{F}_p$ with $p \equiv 2 \pmod 3$.

For prime fields and $G \subseteq \mathbb{F}_p^*$ of prime order $(p-1)/2$, you have described the bijection (given the residue class $x + \langle p \rangle$, let $y$ be the integer with the smallest absolute value s.t. $x \equiv y \pmod{p}$, then map the residue class to $|y|-1$; this relies on the fact that when $x\not\equiv 0 \pmod{p}$, the residue class $x+\langle p \rangle$ is in $G$ iff $-x+\langle p \rangle$ is not in $G$).

A rough approximation for a straight-forward index calculus algorithm: the factor base should contain all the primes smaller than $$B \approx exp\left(\frac{1}{2} \sqrt{\log p \log\log p}\right),$$ which is $B \approx 655$ when $p \approx 2^{64}$. With $u=\log p/\log B \approx 7$, the fraction of smooth integers is about $u^{-u} \approx 10^{-6}$, which means that we need $\approx 2\cdot10^{10}$ arithmetic operations ((approx $100$ arithmetic operations to create a candidate + $100$ divisions to reject non-smooth numbers) times $10^6$ tries to get one relation times $100$ relations) to get the linear relations. Solving the resulting linear systems should require less than $\approx 10^6$ arithmetic operations (Gauss-elimination is $O(B^3)$).

So index calculus should take approximately as much time as BSGS or Pollard $\rho$. As $p$ increases, the cost of square root methods increase quickly, so index calculus should be competitive very soon.

Comparing the asymptotic complexity of index calculus $L_p(1/2,2)$ with NFS' $L_p(1/3,(64/9)^{1/3})$, we see that NFS should be approximately a lot faster, which means that this idea has potentially a very small merit. This is in contrast to factoring, where NFS is slower than QS for numbers of this size. But I don't know NFS well enough to say if this comparison is even close to correct.

For the supersingular elliptic curve $E: Y^2 = X^3+1$, there are $p+1$ points. We can map a point $(x,y)$ on the elliptic curve $E$ simply to $y$, and the point at infinity to $p$. This relies on the fact that $3$ has an inverse modulo $p-1$, which means that the map $x \mapsto x^3+1$ is invertible ($z \mapsto (z-1)^d$ for some $d$ s.t. $3d \equiv 1 \pmod{p-1}$). This means that for any $y$, $z = y^2$ is determined, which will determine $x^3+1$, which will determine $x$. We know that there are exactly two points on the curve with this $X$-coordinate, namely $(x,\pm y)$. We see that the $y$-coordinate uniquely specifies the point on the curve.

Going back and forth is trivial. Finding such curves amounts to finding primes $p$ such that $p+1$ is "almost" a prime, which is easy.

The arithmetic on the curve is more expensive than the arithmetic in a finite field (approximately a factor of 10).

There are two approaches to computing discrete logarithms on the curve. The first is the obvious approach, using BSGS or Pollard's $\rho$. This has about the same merit as the finite field case.

The other is to use the Weil pairing to map points on the curve into a subgroup of $F_{p^2}^*$ and then apply index calculus there. At first glance, this suggests an analysis much like above, but as far as I can tell, index calculus ($L_p(1/2,\sqrt{48})$?) and NFS is significantly more expensive in extension fields of low degree than in prime fields. I expect this to mean that index calculus will not be competitive except for primes larger than $2^{64}$, but I won't speculate on how much bigger.

I conjecture that this approach has merit about $\sqrt{p}$ for small $p$.

Answer 3

The problem with supersingular elliptic curves is that they're vulnerable to transfer attacks (which reduce the elliptic curve DLP into an additive or multiplicative group DLP) as explained on Bernstein's SafeCurves page.

Fortunately, it's possible to build a one-way permutation using an arbitrary elliptic curve $E$ over the field $\mathbb{F}_p$. The trick is to take the union of $E$ and its quadratic twist $E'$. Specifically, when written in Weierstrass normal form, the x-coordinates of the points in $E'$ precisely fill the gaps formed by the x-coordinates of the points in $E$. In particular, we have:

$$ |E| + |E'| = 2p+2 $$

and can construct an explicit two-way bijection from $E \cup E'$ to $\{0, 1, \dots, 2p+1\}$ by combining $x$ with the sign bit of $y$ (and doing some slight extra fudging to deal with points at infinity and points where $y = 0$).

Provided that the elliptic curves $E$ and $E'$ are cyclic groups (with respective generators $G$ and $H$) and intractable DLPs, then we can define a one-way bijection from $\{0, 1, \dots, 2p+1\}$ to $E \cup E'$ as follows:

• If $x < |E|$, then raise a basepoint $G \in E$ on the original curve to the power of $x$;
• If $x \geq |E|$, then raise a basepoint $H \in E'$ on the twisted curve to the power of $x$;

We can compose this with the aforementioned two-way bijection from $E \cup E'$ to $\{0,1,\dots,2p+1\}$ to yield a one-way permutation on the set $\{0,1,\dots,2p+1\}$. Reversing this permutation is equivalent to solving the elliptic curve DLP on either $E$ or $E'$, depending on the input, so it is best if the parameters are chosen such that both $E$ and its quadratic twist $E'$ are safe curves.

This idea seems to have first appeared in Kaliski 1991, where the author additionally proves (via a union bound) that it's possible to guarantee the existence of such a pair of cyclic curves $E, E'$.

In practice, you could choose $p = 2^{255} - 19$, hunt for a pair of suitable safe curves, and thereby obtain a one-way permutation on the interval $[0, 2^{256} - 37]$ with 128 bits of security.