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?


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

  • $\begingroup$ 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…) $\endgroup$ May 27, 2021 at 16:53
  • $\begingroup$ So, I wasn't just crazy… it looks like some papers use "permutation" in the common-language sense: eprint.iacr.org/2020/… citeseerx.ist.psu.edu/viewdoc/… $\endgroup$ May 27, 2021 at 17:00
  • $\begingroup$ Bijection and permutation are often used interchangeably. $\endgroup$
    – hola
    May 28, 2021 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.