# One-way permutation over a small interval?

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}$).

My current status (improved thanks to a comment by Ricky Demer):

One well known family of one-way permutations $P$ is based on the hardness of the Discrete Logarithm Problem in $\mathbb Z_p$. If $p=2\cdot s+3$ is prime, and $(p-1)/2=s+1$ is prime, then $\forall g\in\{2\dots p-2\}$, $$P:x\mapsto \min\big((g^{x+1}\bmod p),p-(g^{x+1}\bmod p)\big)-2$$ is a permutation over $\{0\dots s-1\}$ and hard to invert to some degree. However GNFS and the index calculus method apply, thus the merit $M$ for small $s$ is only so-so. I welcome a numeric estimate of merit as a function of $s$.

Note: The factor $2$ in $p=2\cdot s+3$ gives a welcome increase in the merit for a given $s$. Various offsets are here to make each of the $s$ values $P(x)$ potentially dependent on $g$, which is a nice-to-have (it allows the choice of $g$ to act as a small key, or parameter instantiating one of a member in a function family). It is not necessary to check whether $g$ is a generator (but it was suggested it could somehow impact how to best invert the permutation).

Another option might be to use an Elliptic Curve group for which there is an efficient mapping to and from an interval, such as in this answer; however this seems to work only for some special curves, and is not entirely clear to me. I welcome details, especially about:

• the working of such a system,
• what is the merit (perhaps relative to the $\mathbb Z_p$ scheme above),
• Elliptic Curve selection allowing mapping from interval to the curve, and back, efficiently enough that it does not kill the merit,
• if there is any hope of using a generic Elliptic Curve group (or other generic group).
• You can get one for $\;\; p \: = \: (2\hspace{-0.03 in}\cdot \hspace{-0.03 in}s)+3 \;\;$ by using the elements of order exactly $p$. $\hspace{1.7 in}$ (The main trick is $\: x\mapsto \operatorname{min}(x,p\hspace{-0.04 in}-\hspace{-0.04 in}x) \;$.) $\;\;\;\;\;\;\;\;$ – user991 Feb 6 '14 at 0:35
• (You obviously figured this part out, but my previous comment should say "exactly $q$" instead of "exactly $p$".) – user991 Feb 6 '14 at 6:28
• I think that whether or not $g$ should be a generator depends on whether $\hspace{1.86 in}$ index calculus or generic attacks are faster. $\:$ – user991 Feb 6 '14 at 7:29
• About your elliptic curve remark: There are special elliptic curves (e.g. supersingular curves, composite degree curves), where variations of Index Calculus also work, but there is no "one fits all" algorithm as far as we know. But on the other side, we don't know if there are algorithms for all kinds of elliptic curves. You will have to base your estimates on heuristics or the generic group model. – tylo Feb 6 '14 at 18:32
• @tylo: I'd be quite happy to use a generic Elliptic Curve and the associated heuristic estimates of the cost of the DLP based on the generic group model. However I do not know how to derive an efficiently computable one-way permutation over an interval from that. I can only (vaguely) see that is possible for supersingular Elliptic Curves, and I'm told that the DLP on such curves is vastly easier than in the generic group model. – fgrieu Feb 6 '14 at 20:04

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