Slow one-way pseudo-random permutation?

Question

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

Answer 1

Here's the best I can do. Let $\mathbb{G}$ be an elliptic curve group over a 64-bit prime. Define $f:\{0,1,2,\dots,2^{64}-1\} \to \mathbb{G}$ by $f(n) = ng$, where $g \in \mathbb{G}$ is a generator of order at least $2^{64}$. Notice that you can represent any group element in 65 bits, using point compression. Also, notice that $f$ is injective.

This gives you a one-way injective function $f$ that takes a few group operations to compute in the forward direction and about $2^{32}$ group operations to compute in the reverse direction. The function takes a 64-bit input and produces a 65-bit output, so it is not a one-way permutation, but it is close enough for your application (in your application, you just need the output of the function to be not much larger than the input and the function to be injective).

Now if you want to make it pseudorandom, you can use Dmitry Khovratovich's technique. Define

$$F(k,x) = E'(k_1,f(E(k_0,x)))$$

where $k_0,k_1$ are derived from $k$, where $E(k_0,\cdot)$ is a block cipher with a 64-bit block width, and $E'(k_1,\cdot)$ is a block cipher with a 65-bit block width. I don't know how to make this slow for the owner of the key $k$.

The problem with this is that an attacker who knows the key $k$ can still invert with $2^{32}$ operations, which is much faster than you were hoping for. Even worse, if the attacker wants to invert many such values, he can probably amortize his effort (the time per value inverted probably decreases as a function of the number of values to be inverted), thanks to the properties of the discrete log problem. Therefore, I suspect this likely won't be sufficient in practice.

In practice I suspect your best bet is going to be to use a trusted server or HSM at the back-end containing a database holding the desired mapping, and let the server enforce all of the restrictions you have in mind (e.g., about only being able to compute the mapping in one direction).

Answer 2

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& \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<\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<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$).

Answer 3

I have a 128-bit block cipher that can be modified to fit your requirements (possibly).

It is an AES variant with a 16x16 matrix multiplication that operates on the entire state instead of the standard 4x4. ShiftRows is maintained but not necessary for diffusion. The matrix is its own self inverse. The s-box has been replaced with one that has a more complicated algebraic properties. The key schedule uses Keccak with c=1024,r=576, and generates round keys with a squeeze operation with 448 bits of output ignored. The key size and round counts are specified up to 512-bit keys.

In the standard form it is slow because of the large matrix multiplication, but in 32-bit and larger systems table lookups can be used (with about 64KB of memory for the tables) that combine the matrix with the sbox. The decryption process is simple, using the same "equivalent inverse" method that AES uses. The design can be shrunk to 64-bits using an 8x8 matrix, or extended to 256-bits using a 32x32 matrix.

In order to modify it to meet your requirements, additional rounds could be a parameter to slow it down. The ease of decryption part can be solved with using a non invertible MDS matrix. Additional slowdowns can be made by changing the round count of Keccak when generating round keys. Brute forcing a key with a 96-round Keccak based key schedule will be hundreds, if not thousands of times slower than AES.

Since this is a permutation, all unique inputs are guaranteed to produce unique outputs with a given key. With a non invertible matrix there should be no efficient decryption. With parametrized round counts and flexible key sizes, in addition to its design, it should be as slow as you want it to be on all platforms. The design should make its pseudo-randomness equal to or better than AES at a given round count (for a 128-bit block anyway). All of your requirements except for configurable memory requirements should be met.

Round function pseudocode modified since decryption not required

AddRoundKey 0
for i = 1 to Rounds
  Sbox(state)
  MatrixMultiply(state)
  AddRoundKey i
next i

16x16 MDS matrix modulo 0x11B (not tested for noninvertibility but sure looks it)

5C E8 9C 6C 77 0C 0E F7 47 79 5C CE A4 FA 80 B5
E8 2C 23 A9 08 70 5F 43 6B 15 84 29 32 5E DA 4E
9C 23 5F 41 87 FA 37 AF CA E4 79 24 85 42 2D DC
6C A9 41 EB C7 E0 BD E2 71 4E 27 93 9F 62 33 53
77 08 87 C7 48 15 1C 5B B5 6B B7 99 D3 52 D3 86
0C 70 FA E0 15 CE 24 72 B1 D4 DB 98 EE DA A2 5A
0E 5F 37 BD 1C 24 91 D5 75 35 A1 86 5A AF B3 87
F7 43 AF E2 5B 72 D5 6A 0E 54 AA 3D 6D CA F3 F7
47 6B CA 71 B5 B1 75 0E 86 8A 64 5E 44 EA AC DD
79 15 E4 4E 6B D4 35 54 8A 83 6E B3 CC F5 BD 49
5C 84 79 27 B7 DB A1 AA 64 6E 1D 2F 04 10 B8 74
CE 29 24 93 99 98 86 3D 5E B3 2F DA F1 DF B4 69
A4 32 85 9F D3 EE 5A 6D 44 CC 04 F1 3C 2D 87 6C
FA 5E 42 62 52 DA AF CA EA F5 10 DF 2D B6 41 62
80 DA 2D 33 D3 A2 B3 F3 AC BD B8 B4 87 41 7A D5
0E 1F EE BC C4 F7 48 81 F7 48 DE 4D 57 C4 A3 A4