2
$\begingroup$

I have a set that is too large to hold in memory but I have a function that I can use to compute a value within the set given an index. I'm curious if there's a standard way to shuffle this set, a pseudo-shuffle is acceptable and expected.

I imagine a function that is initialized with some parameters, including the size of the set to be shuffled, and that I can call repeatedly, getting unique and pseudo-random indexes each time that I can use to generate the corresponding value in my set. I also imagine that this function is periodic and repeats after I've gone through all values once (so there's some mod relation).

This function need not be cryptographically secure but rather be easy to construct and hold in memory so that the next "random" value of the set may be generated.


Here's a concrete formulation of the problem. I want to iteratively generate "random" colors in the RGB spectrum without repeats. I don't want to create an array of 256^3 elements and shuffle them. I want a function that on each call provides an index in the range that I have not yet received, until I've exhausted the range.

How might you construct a function that satisfies the above?

$\endgroup$
2
  • $\begingroup$ 256^3 is not “too large for memory”. $\endgroup$
    – gnasher729
    Apr 9, 2020 at 19:18
  • $\begingroup$ Sure, pick domain that is too large for memory. $\endgroup$ Apr 10, 2020 at 20:58

1 Answer 1

1
$\begingroup$

Let $n$ denote the number of items in the set, and $f(i)$ denote the $i$th value. Use format-preserving encryption to construct a random permutation $\sigma:\{1,\dots,n\} \to \{1,\dots,n\}$. Define $g(i) = f(\sigma(i))$. Then $g$ is a representation of a randomly shuffled version of your set, and specific items can be accessed very efficiently.


To address your concrete problem, you'd pick a random permutation on $\{0,1\}^{24}$, i.e., $\sigma : \{0,1\}^{24} \to \{0,1\}^{24}$. This can be done using format-preserving encryption: format-preserving encryption will give you a block cipher $E:K \times \{0,1\}^{24} \to \{0,1\}^{24}$ such that if you pick a key $k \in K$ random, $E_k$ will be (indistinguishable from) a random permutation on $\{0,1\}^{24}$. Moreover, $E_k$ can be efficiently evaluated. Then, if you want $m$ random RGB colors, you'd pick a random key $k$ and output the $m$ colors $E_k(0), E_k(1), \dots, E_k(m-1)$.

A reasonable way to build a 24-bit block cipher is to use a Feistel cipher on 24 bits: say, 4 rounds, where in the $i$th round you map the input $L||R$ to the output $R||(L \oplus f_k(R,i))$, where $L,R$ are each 12 bits long and $f_k$ is a PRF, say $f_k = AES_k(R||i)$, and $||$ denotes concatenation of bits. You can adjust the number of rounds (fewer rounds is faster; more rounds gives higher amount of pseudorandomness; you probably want at least 3 rounds), and you can adjust the choice of $f$ (for instance, instead of a cryptographic-based construction, you could use any fast, non-cryptographic hash function). This is the construction proposed in https://en.wikipedia.org/wiki/Format-preserving_encryption#FPE_from_a_Feistel_network. I suggest referring to the Wikipedia link I shared above for an overview of standard constructions for format-preserving encryption.

$\endgroup$
4
  • $\begingroup$ How might I go about constructing 𝜎? $\endgroup$ Apr 7, 2020 at 16:13
  • $\begingroup$ @geofflittle, use format-preserving encryption. $\endgroup$
    – D.W.
    Apr 7, 2020 at 17:36
  • $\begingroup$ I've added a more concrete problem to the question. What would be your construction to satisfy the problem? $\endgroup$ Apr 8, 2020 at 19:15
  • $\begingroup$ @geofflittle, see revised answer. $\endgroup$
    – D.W.
    Apr 8, 2020 at 19:50

Your Answer

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

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