Thorp shuffle

The Thorp shuffle is a model of a riffle shuffle, introduced by Edward O. Thorp in 1973 in his study of nonrandom shuffling and the game of faro. The deck is split into two equal packets. For each pair of current bottom cards, a fair coin decides whether the left card or the right card is dropped first, and then the other card is dropped. This continues until both packets are empty.

As the number of rounds approaches infinity, the output of the Thorp shuffle approaches the distribution of a uniformly sampled permutation. For a deck whose size is a power of two, the shuffle is equivalent to a maximally unbalanced Feistel network. It has applications in cryptography, including private information retrieval.

Procedure

For an even number $n$ of cards, split the deck into two equal packets. Keep the order inside each packet, and pair the cards having the same depth in the two packets. For every pair toss an independent fair coin, and use that coin to decide which member of the pair occupies the earlier of the two corresponding output positions. Thus there are $n / 2$ independent coin tosses in one shuffle.

Number the positions from $0$ to $n - 1$ . For every pair of cards in positions $x$ and $x + n / 2$ , a coin decides which one will be placed in position $2 x$ and which one in position $2 x + 1$ , where $0 \leq x < n / 2$ . Repeat with fresh random choices for each round.

Binary representation

For a deck of $n = 2^{d}$ cards, write each position as a $d$ -digit binary number $(b, x)$ , with first bit $b$ and remaining bits $x$ . The shuffle pairs positions whose binary numbers differ only in that first bit, namely $(0, x)$ and $(1, x)$ .

For each pair, toss a fair coin independently to decide whether to swap the two cards. Let $ξ_{x} = 1$ for a swap and $ξ_{x} = 0$ otherwise. Moving the first bit of the resulting position number to the end completes the shuffle: $(b, x) ⟼ (x, b \oplus ξ_{x}),$ where $\oplus$ denotes exclusive OR, or addition modulo two.

In an eight-card deck, the card at $101$ is paired with the card at $001$ . Without a swap, the rotation sends it to $011$ ; with a swap, it moves first to $001$ and then to $010$ .

Butterfly network

A block of $d$ Thorp shuffles on $2^{d}$ cards is equivalent to one butterfly switching network. One way to visualize what the network does is as follows. Take a $d$ -dimensional hypercube and color its edges by coordinate direction. Put $n$ numbered balls on the $n$ vertices of the cube. Go sequentially through the $d$ colors, and for each edge of the current color, switch the balls at its ends with probability one half, independently of the other edges.

A ball placed at any starting vertex has the same probability $1 / n$ of finishing at any vertex. This uniform distribution for one ball does not imply that the whole permutation is uniform.

Mixing time

The total number of shuffles required to make all shuffling outcomes have almost uniform distribution (equally likely, independent of initial card order) is called the mixing time. The acceptable error is expressed as total variation distance.

For $n = 2^{d}$ cards, Ben Morris obtained a full-deck upper bound of $O (d^{44})$ in big O notation. Morris subsequently proved an $O ((\log n)^{4})$ bound for arbitrary even $n$ , and then, for $n = 2^{d}$ , reduced the full-deck bound to $O (d^{3})$ . Morris, Rogaway and Stegers also obtained estimates for subsets of the cards, which can mix much faster than the whole deck.

An $n$ -card deck has $n!$ possible orders, but one round of the Thorp shuffle has only $2^{n / 2}$ possible outcomes. After $r$ rounds, at most $2^{r n / 2}$ orders can be reached. To come within a fixed total variation distance $0 < ε < 1$ of uniform, at least $(1 - ε) n!$ orders must be reachable. This forces $r$ to grow at least linearly with $d = \log_{2} n$ , giving an information-theoretic lower bound.

Cryptographic applications

The resulting position of a single card can be computed without performing the whole shuffle, by checking only a small number of bits. The same holds for the inverse shuffle. In a cryptographic implementation, a seed for a pseudorandom generator, together with a description of how many rounds to run, specifies the permutation. The seed is used to generate the bits in each step and allows the shuffle to be evaluated in either direction.

In ThorPIR, a protocol for private information retrieval from a single server, the client and server first run a joint preprocessing algorithm. The client can then retrieve elements from the database privately, without revealing which element was requested. During preprocessing, the server computes the Thorp shuffle under fully homomorphic encryption.

References

1 2 3 4 Jiang 2026, p. 2.
↑ Thorp 1973, p. 844.
1 2 3 Fisch et al. 2024, p. 10.
↑ Fisch et al. 2024, p. 41.
↑ Morris, Rogaway & Stegers 2018, p. 523.
1 2 Fisch et al. 2024, p. 1.
1 2 3 Jiang 2026, p. 4.
↑ Morris, Rogaway & Stegers 2018, p. 522.
1 2 Fisch et al. 2024, p. 11.
↑ Gelman & Ta-Shma 2014, p. 329.
1 2 3 Gelman & Ta-Shma 2014, p. 330.
↑ Jiang 2026, p. 6.
↑ Morris, Rogaway & Stegers 2018, p. 524.
↑ Morris, Rogaway & Stegers 2018, p. 525.
↑ Jiang 2026, p. 3.
↑ Fisch et al. 2024, p. 5.

Sources

Fisch, Ben; Lazzaretti, Arthur; Liu, Zeyu; Papamanthou, Charalampos (2024). "ThorPIR: Single Server PIR via Homomorphic Thorp Shuffles" (PDF). Cryptology ePrint Archive (2024/482). Archived (PDF) from the original on 2 January 2026.
Gelman, Efraim; Ta-Shma, Amnon (2014). "The Benes Network is q(q−1)/2n-Almost q-set-wise Independent". In Raman, Venkatesh; Suresh, S. P. (eds.). 34th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics. Vol. 29. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 327–338. doi:10.4230/LIPIcs.FSTTCS.2014.327.
Jiang, Yunjiang (3 October 2026). "A subquadratic upper bound for the mixing time of the Thorp shuffle". arXiv. arXiv:2610.18884v1.
Morris, Ben; Rogaway, Phillip; Stegers, Till (2018). "Deterministic Encryption with the Thorp Shuffle". Journal of Cryptology. 31 (2): 521–536. doi:10.1007/s00145-017-9262-z.
Thorp, Edward O. (December 1973). "Nonrandom Shuffling with Applications to the Game of Faro" (PDF). Journal of the American Statistical Association. 68 (344): 842–847. doi:10.1080/01621459.1973.10481434.

This article incorporates text by Efraim Gelman and Amnon Ta-Shma available under the CC BY 3.0 license.

This article incorporates text by Ben Fisch, Arthur Lazzaretti, Zeyu Liu and Charalampos Papamanthou available under the CC BY 4.0 license.

This article incorporates text by Yunjiang Jiang available under the CC BY 4.0 license.

Passages from these sources have been reproduced and adapted, with omissions and changes to notation and wording.

[FOOTNOTEJiang20262-1] 1 2 3 4 Jiang 2026, p. 2.

[FOOTNOTEThorp1973844-2] Thorp 1973, p. 844.

[FOOTNOTEFischLazzarettiLiuPapamanthou202410-3] 1 2 3 Fisch et al. 2024, p. 10.

[FOOTNOTEFischLazzarettiLiuPapamanthou202441-4] Fisch et al. 2024, p. 41.

[FOOTNOTEMorrisRogawayStegers2018523-5] Morris, Rogaway & Stegers 2018, p. 523.

[FOOTNOTEFischLazzarettiLiuPapamanthou20241-6] 1 2 Fisch et al. 2024, p. 1.

[FOOTNOTEJiang20264-7] 1 2 3 Jiang 2026, p. 4.

[FOOTNOTEMorrisRogawayStegers2018522-8] Morris, Rogaway & Stegers 2018, p. 522.

[FOOTNOTEFischLazzarettiLiuPapamanthou202411-9] 1 2 Fisch et al. 2024, p. 11.

[FOOTNOTEGelmanTa-Shma2014329-10] Gelman & Ta-Shma 2014, p. 329.

[FOOTNOTEGelmanTa-Shma2014330-11] 1 2 3 Gelman & Ta-Shma 2014, p. 330.

[FOOTNOTEJiang20266-12] Jiang 2026, p. 6.

[FOOTNOTEMorrisRogawayStegers2018524-13] Morris, Rogaway & Stegers 2018, p. 524.

[FOOTNOTEMorrisRogawayStegers2018525-14] Morris, Rogaway & Stegers 2018, p. 525.

[FOOTNOTEJiang20263-15] Jiang 2026, p. 3.

[FOOTNOTEFischLazzarettiLiuPapamanthou20245-16] Fisch et al. 2024, p. 5.