Mixing Times of Markov Chains with Applications to Cryptography

University Of California-Davis, Davis CA

Investigators

Abstract

The investigator will study problems in discrete probability, most of which concern mixing times for Markov chains. The Thorp shuffle, which is a method of card shuffling based on "local swaps" has found applications to applied cryptography. It is the basis of a new algorithm to encipher small messages such as social security numbers. Recently, algorithms based on variants of the Thorp shuffle that use both local and global swaps have been proposed. It is planned to obtain good mixing time bounds for these shuffles. These shuffles appear to have a very strong mixing property that relates to the cryptographic notion of indifferentiability. It is planned to prove this rigorously. It is also planned to study a number of problems concerning random walks on graphs, including Aldous and Fill's conjecture that for coalescing random walks, the expected time for all particles to coalesce is at most a constant times the maximum expected hitting time of any vertex. The primary goal of this project is to find improved methods to analyze Markov chains. Markov chains have been used widely in statistics, statistical physics, simulation and optimization. This project focuses on Markov chains used in "small space" encryption algorithms. With rising concerns about identity theft, methods to encrypt small messages such as social security numbers are of great practical interest.