Can I construct a PRP by sorting results of a PRF?

I am using HMAC-SHA256 as a pseudorandom function family (PRF). I read somewhere that a pseudorandom permutation family (PRP) can be implemented by applying a PRF and sorting the output.

For example, if $x_1$ mapped to $4$ under a specific key in the PRF, and $x_2$ mapped to $2$, then the PRP for $\{x_1, x_2\}$ would be $\{x_2, x_1\}$ under that same key.

Does that make sense? Is this PRP construction secure, or do I have to implement a Luby-Rackoff construction using the PRF?

• @fgrieu I didn't have the exact reference at the time that I wrote the question, but I dug up the reference: "The PRPs can actually be implemented by applying a PRF and then sorting the resulting output." -- eprint.iacr.org/2014/638.pdf. See Encryption Efficiency under section 5.5. See Ilmari Karonen's answer as well, as he appears to have understood the given construction. – JohnDvorak Nov 6 '16 at 16:17

2 Answers

Even if this worked in principle, I don't see how this could possibly be practical to implement for any but the smallest sets, since it requires you to enumerate (and sort) the set you want to permute.

Also, it seems to me that, unless the codomain of the PRF is much larger than its domain, you're going to have an issue with ties, i.e. with inputs $x_1 \ne x_2$ for which ${\rm PRF}(x_1) = {\rm PRF}(x_2)$. I don't see any obvious way to break such ties that could not be potentially used to distinguish the resulting PRP from a random permutation.

All that said, if you really just want to pseudorandomly shuffle a small set of values, feeding each of them to a PRF with a sufficiently large domain (like HMAC-SHA256) and sorting the values by the result should be a perfectly good and secure solution. Specifically, consider an adversary that tries to distinguish your pseudorandom shuffle from a truly random shuffle. For such an adversary to succeed (with probability greater than ½), they must either:

1. somehow distinguish the PRF from a random function, or
2. observe a collision among the PRF outputs.

The probability of option 1 will depend on the PRF (and on the assumed capabilities of the attacker), but it must be negligibly small for all practical attackers for the PRF to be deemed secure. On the other hand, assuming that the PRF is not distinguishable from a random function, the second probability can be calculated:

Specifically, given $k$ inputs to a PRF with an $n$-element codomain (where e.g. $n = 2^{256}$ for HMAC-SHA256), the probability $p$ of observing at least one collision is less than the expected number of collisions, which itself equals $\frac{k^2 - k}{2n} < \frac{k^2}{2n}$. Thus, for example, if $k \le 2^{64}$ and $n = 2^{256}$, then $p < \frac{(2^{64})^2}{2\cdot2^{256}} = 2^{-129}$.

• Ah, my notation might have gotten in the way of what I was trying to share. The codomain of my function is the same as the codomain of HMAC-SHA256, which should be plenty large enough for the number of inputs I'll need for each permutation call (on the order of hundreds, or possibly thousands). For the number of inputs in that range, would the above construction be secure? – JohnDvorak Nov 5 '16 at 20:00
• If not, I'm not totally sure how to start to implement a PRP family using my PRF as a building-block. – JohnDvorak Nov 5 '16 at 20:01
• Yes, for shuffling small sets this should be practical and secure, assuming that the PRF is secure and has long enough output. See edit above. – Ilmari Karonen Nov 5 '16 at 20:15

The observation made by the reference when it says

The PRPs can actually be implemented by applying a PRF and then sorting the resulting output

possibly has to do with the fact that if one has a function $F:\mathbb Z_a\to\mathbb Z_b$, one can build a permutation $P:\mathbb Z_a\to\mathbb Z_a$ defined by making a stable sort of the vector of the $F(j)$, then assigning to $P(j)$ the index of the position of $F(j)$ in the sorted vector; that is, $P(j)$ is defined as the number of $i$ in $\mathbb Z_a$ such that $F(i)<F(j)\text{ or }\big(F(i)=F(j)\text{ and }i<j\big)$.

And, when $a$ and $b$ are such that $F(i)=F(j)$ is not observable, this construction turns a PRF into a PRP.

Yet, I do not see how this can be turned into a practical implementation of a PRP unless $a$ is small enough to be enumerable (in which case we need $b\gg a^2$ to avoid $F(i)=F(j)$ to become observable).

One the other hand, we do have other approaches that work, like the Thorp Shuffle (Ben Morris, Phillip Rogaway, and Till Stegers, How to Encipher Messages on a Small Domain: Deterministic Encryption and the Thorp Shuffle, in proceedings of Crypto 2009).