Mixing Times of Markov Chains with Applications to Cryptography

研究者将研究离散概率问题，其中大多数涉及马尔可夫链的混合时间。索普洗牌是一种基于“局部交换”的洗牌方法，已经在应用密码学中找到了应用。它是一种新算法的基础，用于加密诸如社会安全号码之类的小信息。最近，基于索普洗牌变体的算法被提出，该算法同时使用局部和全局交换。计划为这些洗牌获得良好的混合时间界限。这些洗牌似乎具有很强的混合性质，这与密码学的不可微分概念有关。计划严格地证明这一点。还计划研究一些关于图上随机漫步的问题，包括Aldous和Fill的猜想，即对于合并随机漫步，所有粒子合并的期望时间最多是任何顶点的最大期望撞击时间的常数倍。这个项目的主要目标是找到改进的方法来分析马尔可夫链。马尔可夫链在统计学、统计物理、仿真和优化等领域有着广泛的应用。本项目重点研究“小空间”加密算法中使用的马尔可夫链。随着人们对身份盗窃的担忧日益增加，对社会安全号码等小信息进行加密的方法具有很大的实际意义。

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.