<p dir="ltr">Combinatorial graph theory is an essential tool in the design and analysis of cryptographic primitives such as Memory-Hard Functions (MHFs) and Proofs of Sequential Work (PoSWs). MHFs are used to design egalitarian Proofs of Work and to help protect low-entropy secrets such as user passwords against brute-force attacks in password hashing. A PoSW is a protocol for proving that one spent significant sequential computation work to validate some statement. PoSWs have many applications, including time-stamping, blockchain design, and universally verifiable CPU benchmarks. Prior work has used combinatorial properties of graphs to construct provably secure MHFs and PoSWs. However, some open problems still exist, such as improving security bounds for MHFs, finding approximation algorithms for measuring their memory hardness, and analyzing the post-quantum security of MHFs and PoSWs. This dissertation addresses these challenges in the security analysis of MHFs and PoSWs using combinatorial graph theory. </p><p dir="ltr">We first improve the understanding of the classical security of MHFs in the following ways. (1) We present improved security bounds for MHF candidates such as Argon2i and DRSample under plausible graph-theoretic conjectures. (2) We prove that it is Unique Games-hard to approximate the cumulative pebbling complexity of a directed acyclic graph, which is an important metric to understand the memory-hardness of data-independent MHFs. (3) We provide the first explicit construction of extremely depth-robust graphs with small indegree. Here, (extreme) depth-robustness is a crucial combinatorial tool to construct secure MHFs and PoSWs. (4) We build a new family of graphs that achieves better provable parameters for concrete depth-robustness.</p><p dir="ltr">Second, as we progress toward developing quantum computers, we initiate the post-quantum security analysis of MHFs and PoSWs. Specifically, we make the following contributions. (1) We introduce the parallel reversible pebbling game, which captures additional restrictions in quantum computing. We use combinatorial graph theory as a tool to analyze the space-time complexity and the cumulative pebbling complexity of MHF candidates such as Argon2i and DRSample in a reversible setting, which we call reversible space-time/cumulative pebbling cost, respectively. (2) We prove that the reversible cumulative pebbling cost is never too much larger than the classical cumulative pebbling cost, along with the separation result that, in some instances, the reversible cumulative pebbling cost is asymptotically larger than the classical one. (3) We prove that it is also Unique Games-hard to approximate the reversible cumulative pebbling cost of a directed acyclic graph. (4) Finally, we establish the post-quantum security of a PoSW from Cohen and Pietrzak (EUROCRYPT 2018) in the parallel quantum random oracle model by extending Zhandry's compressed oracle technique (CRYPTO 2019) and utilizing underlying combinatorial techniques of PoSWs.</p>

<p dir="ltr">Brute force guessing attacks continue to pose a significant threat to user passwords. To protect user passwords against brute force attacks, many organizations impose restrictions aimed at forcing users to select stronger passwords. Organizations may also adopt stronger hashing functions in an effort to deter offline brute force guessing attacks. However, these defenses induce trade-offs between security, usability, and the resources an organization is willing to investigate to protect passwords. In order to make informed password policy decisions, it is crucial to understand the distribution over user passwords and how policy updates will impact this password distribution and/or the strategy of a brute force attacker.</p><p dir="ltr">This first part of this thesis focuses on developing rigorous statistical tools to analyze user password distributions and the behavior of brute force password attackers. In particular, we first develop several rigorous statistical techniques to upper and lower bound the guessing curve of an optimal attacker who knows the user password distribution and can order guesses accordingly. We apply these techniques to analyze eight password datasets and two PIN datasets. Our empirical analysis demonstrates that our statistical techniques can be used to evaluate password composition policies, compare the strength of different password distributions, quantify the impact of applying PIN blocklists, and help tune hash cost parameters. A real world attacker may not have perfect knowledge of the password distribution. Prior work introduced an efficient Monte Carlo technique to estimate the guessing number of a password under a particular password cracking model, i.e., the number of guesses an attacker would check before this particular password. This tool can also be used to generate password guessing curves, but there is no absolute guarantee that the guessing number and the resulting guessing curves are accurate. Thus, we propose a tool called Confident Monte Carlo that uses rigorous statistical techniques to upper and lower bound the guessing number of a particular password as well as the attacker's entire guessing curve. Our empirical analysis also demonstrate that this tool can be used to help inform password policy decisions, e.g., identifying and warning users with weaker passwords, or tuning hash cost parameters.</p><p dir="ltr">The second part of this thesis focuses on developing stronger password hashing algorithms to protect user passwords against offline brute force attacks. In particular, we establish that the memory hard function Scrypt, which has been widely deployed as password hash function, is maximally bandwidth hard. We also present new techniques to construct and analyze depth robust graph with improved concrete parameters. Depth robust graph play an essential rule in the design and analysis of memory hard functions.</p>