Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-13T22:46:59.271Z Has data issue: false hasContentIssue false
  • English
  • Français

Improved Mixing Time Bounds for the Thorp Shuffle

Published online by Cambridge University Press:  07 December 2012

BEN MORRIS
BEN MORRIS*
Affiliation:
Department of Mathematics, University of California, Davis, CA 95616, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

E. Thorp introduced the following card shuffling model. Suppose the number of cards is even. Cut the deck into two equal piles, then interleave them as follows. Choose the first card from the left pile or from the right pile according to the outcome of a fair coin flip. Then choose from the other pile. Continue this way, flipping an independent coin for each pair, until both piles are empty.

We prove an upper bound of O(d3) for the mixing time of the Thorp shuffle with 2d cards, improving on the best known bound of O(d4). As a consequence, we obtain an improved bound on the time required to encrypt a binary message of length d using the Thorp shuffle.

Keywords

Primary 60J10
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 1 , January 2013 , pp. 118 - 132
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bellare, M., Rogaway, P. and Spies, T. (2010) The FFX mode of operation and format preserving encryption (draft 1.1). NIST submission.Google Scholar
[2]Cover, T. and Thomas, J. (1991) Elements of Information Theory, Wiley.Google Scholar
[3]Jonasson, J. (2011) Mixing time bounds for overlapping cycles shuffles. Electron. J. Probab. 16 1281–1295.Google Scholar
[4]Luby, M. and Rackoff, C. (1988) How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17 373–386.Google Scholar
[5]Maurer, U. (1993) A simplified and generalized treatment of Luby–Rackoff pseudorandom permutation generators. In Advances in Cryptology: EUROCRYPT 1992, Vol. 658 of Lecture Notes in Computer Science, Springer, pp. 239–255.Google Scholar
[6]Maurer, U. and Pietrzak, K. (2003) The security of many-round Luby–Rackoff pseudorandom permutations. In Advances in Cryptology: EUROCRYPT 2003, Vol. 2656 of Lecture Notes in Computer Science, Springer, pp. 544–561.CrossRefGoogle Scholar
[7]Montenegro, R. and Tetali, P. (2006) Mathematical Aspects of Mixing Times in Markov Chains, Foundations and Trends in Theoretical Computer Science, Now Publishers.Google Scholar
[8]Morris, B. (2008) The mixing time of the Thorp shuffle. In STOC 2005, SIAM J. Comput. 38 484–504.Google Scholar
[9]Morris, B. (2009) Improved mixing time bounds for the Thorp shuffle and L-reversal chain. Ann. Probab. 37 453–477.Google Scholar
[10]Morris, B., Rogaway, P. and Stegers, T. (2009) How to encipher messages on a small domain: Deterministic encrption and the Thorp shuffle. In Advances in Cryptology: CRYPTO 2009, Vol. 5677 of Lecture Notes in Computer Science, Springer, pp. 286–302.Google Scholar
[11]Naor, M. and Reingold, O. (1999) On the construction of pseudo-random permutations: Luby–Rackoff revisited. J. Cryptology 12 29–66.CrossRefGoogle Scholar
[12]Patarin, J. (1991) New results on pseodorandom permutation generators based on the DES scheme. In Advances in Cryptology: CRYPTO 1991, Vol. 576 of Lecture Notes in Computer Science, Springer, pp. 301–312.Google Scholar
[13]Patarin, J. (1998) About Feistel schemes with six (or more) rounds. In Fast Software Encryption 1998, Vol. 1372 of Lecture Notes in Computer Science, Springer, pp. 103–121.Google Scholar
[14]Patarin, J. (2004) Security of random Feistel schemes with 5 or more rounds. In Advances in Cryptology: CRYPTO 2004, Vol. 3152 of Lecture Notes in Computer Science, Springer, pp. 106–122.Google Scholar
[15]Saloff-Coste, L. (2004) Random walks on finite groups. In Probability on Discrete Structures, Vol. 110 of Encyclopedia of Mathematical Sciences (Kesten, H., ed.), Springer, pp. 263–346.Google Scholar
[16]Rudich, S. (1989) Limits on the provable consequences of one-way functions. PhD Thesis, UC Berkeley.Google Scholar
[17]Thorp, E. (1973) Nonrandom shuffling with applications to the game of Faro. J. Amer. Statist. Assoc. 68, 842–847.Google Scholar