Slow one-way pseudo-random permutation?
The main difficulty in designing what I asked, is coming up with a permutation over a relatively small set, that is easy to compute in the forward direction, but convincingly much more difficult to invert. The least unsatisfactory I have so far is based on the discrete logarithm problem in $\mathbb Z_p$. If $p$ and $(p-1)/2$ are primes, and $g\in\{2\dots p-2\}$ with $g^{(p-1)/2}\not\equiv1\pmod p$, then
$$P:\begin{cases}
 x\mapsto g^x\bmod p&amp; \text{if } x\in\{1\dots p-1\}\\
  0\mapsto0
\end{cases}$$
is a permutation of $\{0\dots p-1\}$ which is easy to compute, but markedly harder to invert. At least, the problem is well-studied, with the best known algorithms the index calculus algorithm and some specialized GNFS variants. Bad news is that the problem is workable for 530-bit $p$, and here I'll be stuck with $p$ like 80-bit (for $b=64$ and other realistic parameters).

It seems possible to build a slow one-way pseudorandom permutation over $\{0,1\}^b$ from such $P$, while keeping about the same security gap (ratio of work in backward to forward direction) as in $P$. I sketch such a construction below. Again this is not fully satisfactory, for the above (family of) $P$ does not have a high-enough security gap, given the order of magnitude I can use for $p$. I badly need a better $P$ !!



Update: The best attacks on $P$ require a heavy pre-computation, then can go from $P(x)$ to $x$ at comparably low cost. I have tuned the following to account for that fact.

The construction requires an expected $c_0\cdot c_1$ evaluations of the above $P$ with $p\approx c_0\cdot2^b$, and forces an adversary trying to brute-force the forward direction to mobilize about $m\cdot2^m$ bits of memory for each few instances run in parallel. Realistic parameters could be $b=64$, $c_0=2^{12}$, $c_1=2^{12}$, $m=20$.


Derive from $K$ a pseudo-random $g$ in $\{2\dots c_0\cdot2^{b-1}\}$ ;
Derive from $K$ an arbitrary permutation $M$ of $\{0,1\}^m$, stored as $2^m$ words of $m$ bits of memory;
Repeat for $c_1$ rounds (identifier by round counter $r$) the following keyed permutation of the current $b$-bit state $s$:


derive from $K$ and $r$ a pseudo-random prime $p$ in range $\big[{3\over4}\cdot c_0\cdot2^b\dots{5\over4}\cdot c_0\cdot2^b\big]$, such that $(p-1)/2$ is prime and $(g^{(p-1)/2}\bmod p)=p-1$ (note: it is advantageous to perform the later test right after insuring that $p$ and $(p-1)/2$ have no small divisors);
Repeat 


If $s&lt;\big\lfloor p/2^m\big\rfloor\cdot2^m$ (which is, most of the time)


Replace the low $m$ bits of $s$ with their image through $M$;

If $s\ne0$ (which is, most of the time)


Replace $s$ with $g^s\bmod p$;


Until $s&lt;2^b$.



Note: $s$ temporarily grows to at most $b+\big\lceil\log_2({5\over4}\cdot c_0)\big\rceil$ bits.

For each round, the repeat..until iteration is expected to be executed about $c_0$ times, with an exponential distribution. Increasing the number of rounds $c_1$ makes the runtime more predictable, and less likely that pre-computations for inverting $P$ can help an attack. Each iteration requires one memory lookup, and $\epsilon\cdot\log_2 p$ multiplications $\bmod p$ (we can have $\epsilon\ll1$ with some pre-computation).

(Optionally, the construction could end (or/and start) with some conventional $b$-bit block cipher using key $K_d$ derived from key $K$, perhaps TDES for $b=64$ (with additionally one bit of $K_d$ devoted to making the resulting permutation odd or even, by conditionally swapping output values $0$ and $1$). This, combined with use in other steps of permutations not chosen from $K_d$, convincingly insures that the overall construction is indistinguishable from a random permutation for one not knowing $K$).