My question is related to: When we turn Random shuffle to Pseudorandom Shuffle

The idea is to permute the elements in vector $\mathbf{v}$ pseudorandomly, where $|\mathbf{v}|=n$;

I am aware that we can use Fisher-Yates shuffle for pseudorandom shuffle (in fact we replace the random generator with a pseudorandom one). So we can use a key: $k$, when we want to pseudorandomly shuffle the vector.

Let the pseudorandom shuffle be: $\pi (k,\mathbf{v})$

  1. How to formally define the pseudorandom function? For instance, do we need to say pseudorandom shuffle must be indistinguishable from random shuffle?

  2. Is there any textbook or paper has already defined it?

  • 1
    $\begingroup$ A block cipher is a pseudorandom shuffle. Some use the name block cipher only when the set shuffled has $2^b$ elements, where $b$ is the block size; but the definition has been generalized in Format Preserving Encryption. I see no reason why a pseudorandom shuffle's formal definition would differ from that of a block cipher extended to input/output domain of arbitrary finite size. $\endgroup$ – fgrieu Jan 27 '17 at 15:42
  • $\begingroup$ @fgrieu Thank you for the comment. Then why would people use Fisher-Yates shuffle instead of using a block cipher. Is that because the shuffle algorithm is faster than a block cipher? $\endgroup$ – user153465 Jan 27 '17 at 16:30
  • 2
    $\begingroup$ The Fisher-Yates shuffle gives a perfect block cipher, and is useful and common for actual implementation of one over a small input/output domain. For domain too large for Fisher-Yates, there's the option of an imperfect but computationally secure block cipher constructed otherwise, like Feistel's construction. $\endgroup$ – fgrieu Jan 27 '17 at 17:18
  • $\begingroup$ @fgrieu Do you happen to have a reference regarding using the Fisher-Yates shuffle as a block cipher that way? I'm interested in learning more. $\endgroup$ – Ella Rose Jan 27 '17 at 20:08
  • 1
    $\begingroup$ @Ella Rose: the Fisher-Yates shuffle is also known as Knuth's shuffle. In A Synopsis of Format-Preserving Encryption, Phillip Rogaway presents it as one of the simplest way to implement FPE for tiny domains, and gives several references for this shuffle. $\endgroup$ – fgrieu Jan 28 '17 at 12:57

A PRP (pseudorandom permutation) can be mapped onto the index of each element in vector $\mathbf{v}$ to generate a new index for that element in the shuffled array.

As long as the PRP is secure, the shuffle should be indistinguishable from random. Theoretically, this works if the PRP's input/output is the same size as the number of elements in the array. But in the real world, a PRP construction that can vary it's input/output size for various lengths doesn't exist.

AES-256 could be used as the PRP if there were $2^{256}$ elements in the array. Any stream cipher could be used as long as the size of the vector was a power of $2$. In the real world, there are also memory issues as you have to store values somewhere as you shuffle them. Fisher-Yates solves both these issues by using a PRNG to choose elements to exchange.

That's just my idea of a way to define a pseudorandom shuffle. Using a PRP should make the proof easy. Here's a paper that defines a pseudorandom shuffle in a different way: "The Strength of Weak Randomization: EasilyDeployable, Efficiently Searchable Encryptionwith Minimal Leakage"

  • 1
    $\begingroup$ Why is one bit per element required to represent a permutation? I expected a permutation of n elements to contain $log_2(n!)$ bits of information rather than $n$ $\endgroup$ – Adrian Self Apr 26 '20 at 19:46
  • $\begingroup$ It takes log(n), I believe. Maybe you got confused when I said the vector had to be the size of the input space. I meant this as 2^256, not 256. $\endgroup$ – Grifball Apr 27 '20 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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