Slow one-way pseudo-random permutation? I'm looking for a slow one-way pseudo-random permutation; or in other words a block cipher $E_K: P\in\{0,1\}^b\mapsto C\in\{0,1\}^b$ with moderate block size $b\approx 64$ bits, wide key $K$, indistinguishable from a random permutation for one not knowing $K$, and additional characteristics:


encryption $E_K$ is controllably slow according to a parameter $c$, similar to the iteration count parameter in PBKDF2; an additional memory size parameter $m$ as in Scrypt would be nice;
there is no efficient decryption method even knowing $K$, ideally so that the least costly method to decipher ciphertext blocks $C_j$ would be to try and (slowly) encipher candidate plaintext until finding a match. Update: Otherwise said, there should be a security gap as wide as possible between decryption and encryption, expressed as a ratio of work; and that should remain sizable when the cost of encryption is raised using parameter $c$.


Is there some established (or arguably secure) construct for that? One idea is outlined in this interesting answer to a related question (but unfortunately, the one-wayness obtained using a permutation polynomial seems dubious).

Update: I'd also be satisfied with a slightly expanding injective function, e.g. $E_K: P\in\{0,1\}^b\mapsto C\in\{0,1\}^{b+1}$.



Updated example application: 2-D barcode cards (or other kind of write-once memory cards) are issued to individuals with data including a unique serial number $S$ of $s=32$ bits (sequentially assigned, thus largely guessable from another $S$), and other data $Q_S$ (which we assume has sizable entropy). The serial number is used for some initial purpose, and (interpretations of) regulatory requirements protecting individual's privacy prevent from storing that identifier for purposes unrelated to the initial purpose. Nevertheless, merchants would like to lawfully reuse the same cards in an existing loyalty application, identifying cards with an identifier of small size, and able to work off-line (at least, as a backup). We thus want to transform $S$ and $Q_S$ into a short digest (practically public), computable from $S$, $Q_S$, and a key $K$, that remains unique to a given card (as $S$ is); the digest should leak no information about $S$ and $Q_S$ without access to $K$; and, inasmuch as possible, the confidentiality of $S$ and $Q_S$ should be preserved from an attacker knowing digest and key (thus easing the requirements on secure storage and use of the key). Notice that a truncated MAC would not match the "remains unique to a given card" requirement.

With a function as in the question, we could use as digest $E_K(S||R_S)$ where $R_S$ has $b-s$ bits, and is obtained, say using Scrypt, from $Q_S$, $S$, and $K$. Notice that encryption slowness in the forward/encryption direction is necessary to prevent checking guesses of $S$ and enumerated $R_S$; and even more slowness (ideally, next to $2^b$ times as much slowness) is required in the backward/decryption direction, in order to prevent deciphering of the digest. Notice that either attack would reveal $S$, and also allow forged cards misappropriating the same $S$ and digest as the original, if not the same $Q_S$.
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$).