# How does this generate a permutation?

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[.]

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?

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.
• Darn! So they really just mean “A bijective $f: \{0,1\}^n\to\{0,1\}^n$”? (I could have avoided so much effort if I'd checked somewhere other than Wikipedia for definitions…) May 27, 2021 at 16:53