UC Davis

This dissertation analyzes two algorithms for shuffling cards: the swap-or-not shuffle and the overlapping cycles shuffle.

The swap-or-not shuffle was developed by Hoang, Morris, and Rogaway as a building block for quick data encryption algorithms with concrete security bounds. In Chapter 1 we introduce concepts from cryptography using the language of probability. We also reproduce an important theorem from cryptography first shown by Maurer, Pietrzak, and Renner which says that a random permutation with a total variation mixing time of t steps can be used to create an encryption algorithm with strong security against chosen ciphertext attacks after 2t rounds. We also prove a new theorem that says that a random permutation with a separation mixing time of t steps will create an algorithm with strong chosen ciphertext attack security after only t rounds.

In Chapter 2 we show that for the swap-or-not shuffle on n cards, the separation mixing time of square root of n of the cards is about log base 2 of n. We combine this with our theorem from Chapter 1 to tighten the best known bound on the CCA security of the n card swap-or-not shuffle in the special case of fewer than square root of n queries.

In Chapter 3 we consider the overlapping cycles shuffle. In each step of the overlapping cycles shuffle on n cards, a fair coin is flipped which determines whether the mth card or the nth card is moved to the top of the deck. Angel, Peres, and Wilson showed the following interesting fact: If m = cn where c is rational, then the relaxation time of a single card in the overlapping cycles shuffle is O(n^2). However if c is the inverse golden ratio, then the relaxation time is O(n^(3/2)). We show that the mixing time of the entire deck under the overlapping cycles shuffle matches these relaxation times for a single card up to a factor of log(n)^3.