How does this generate a permutation?

Question

In the process of trying to answer this question, I ended up getting stuck. I found a paper which seems to solve their issue: its authors define a process which yields a pseudorandom permutation generator $h$ when applied to a pseudorandom function $f$ and the resulting $g$ composed twice onto itself:

Let $f=\{f\}^n$ be a pseudorandom function generator where the key length function is $l(n)$. Define a function generator $g=\{g\}^n$ in terms of $f$ as follows. Let $k$ be a string of length $l(n)$, let $k'$ be a string of length $l(n+1)$, let $L$, $R$, and $L'$ be strings of length $n$, and let $R$ be a string of length $n+1$. Then $$g_{k}^{2n}(L\bullet R)=R\bullet[L\oplus f_k^n(R)]$$ $$g_{k'}^{2n+1}=R'\bullet[L'\oplus\text{first }n\text{ bits of }f_{k'}^{n+1}(R')]$$

…

Let $h=g\circ g\circ g$. … Theorem 1 shows that $h$ is pseudorandom if $f$ is pseudorandom… [however, note that] $h=g\circ g$ is not at all pseudorandom[.]

– Michael Luby and Charles Rackoff, How to construct pseudorandom permutations from pseudorandom functions.

However, as I'm implementing it, it seems not to be actually yielding a rearrangement of the input bits. I'll show an example where I provide an input with a hamming weight of 4, but it returns a string with a hamming weight of 15 -- so, clearly not a permutation of the input.

• Parameters:
  • $f$ = SHAKE256
  • $m = 00001000\ 00000100\ 00000010\ 00000001$
  • $n = 32$
  • $l(n) = 0 \Rightarrow k = \text{‘’}$

So, going through it step-by-step:

1. $g_{k}^{n}(g_{k}^{n}(g_{k}^{n}(m)))$

2. $g_{k}^{n}(g_{k}^{n}(g_{k}^{n}(00001000\ 00000100\bullet 00000010\ 00000001)))$

3. $g_{k}^{n}(g_{k}^{n}(00000010\ 00000001\bullet[00001000\ 00000100\oplus f_k^{n/2}(00000010\ 00000001)]))$

   • Python: Crypto.Hash.SHAKE256.new(k).update(b'\x02\x01').read( (n//2) // 8 )

4. $g_{k}^{n}(g_{k}^{n}(00000010\ 00000001\bullet[00001000\ 00000100\oplus 10111101\ 00000101]))$

5. $g_{k}^{n}(g_{k}^{n}(00000010\ 00000001\bullet 10110101\ 00000001))$

6. $g_{k}^{n}(10110101\ 00000001\bullet[00000010\ 00000001\oplus f_k^{n/2}(10110101\ 00000001)])$

   • Python: Crypto.Hash.SHAKE256.new(k).update(b'\xb5\x01').read( (n//2) // 8 )

7. $g_{k}^{n}(10110101\ 00000001\bullet[00000010\ 00000001\oplus 10100111\ 01010000])$

8. $g_{k}^{n}(10110101\ 00000001\bullet 10100101\ 01010001)$

9. $10100101\ 01010001\bullet[10110101\ 00000001\oplus f_k^{n/2}(10100101\ 01010001)]$

   • Python: Crypto.Hash.SHAKE256.new(k).update(b'\xa5\x51').read( (n//2) // 8 )

10. $10100101\ 01010001\bullet [10110101\ 00000001\oplus 10000010\ 01010011]$

11. $10100101\ 01010001\ 00110111\ 01010010$

Since this has not yielded a permutation of $m$, how do the authors actually intend this composition to be done? Am I misinterpreting $\bullet$? Am I botching the composition? Should I be splitting $m$ differently? I did not see any special requirements on $f$ other than it be able to output $n$ bits (and even that looked non-strict, being croppable when an odd number of bits is required), so what am I missing here?

Answer 1

It is a permutation not in the sense that it permutes the bit positions of the given input, but in the sense that it is a one-to-one correspondence from a set (of bitstrings) to the same set, as defined in that paper:

2. Terminology …

Let $F^n$ be the set of all ${2^n}^{2^n}$ functions mapping $\{0,1\}^n$ into $\{0,1\}^n$… Let $P^n\subset F^n$ be the set of such functions that are permutations, i.e., they are 1-1 onto functions.