Purdue University Graduate School
Browse

File(s) under embargo

10

month(s)

7

day(s)

until file(s) become available

Applications of Combinatorial Graph Theory to the Classical and Post-Quantum Security Analysis of Memory-Hard Functions and Proofs of Sequential Work

thesis
posted on 2024-04-26, 09:08 authored by Seunghoon LeeSeunghoon Lee

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.

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.

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.

Funding

CRII: SaTC: Towards the Development of Stronger Memory-Hard Functions for Secure Password Hashing

Directorate for Computer & Information Science & Engineering

Find out more...

Emerging Frontiers of Science of Information

Directorate for Computer & Information Science & Engineering

Find out more...

CAREER: Cryptographic Tools for Usable Human Authentication

Directorate for Computer & Information Science & Engineering

Find out more...

Purdue Bilsland Dissertation Fellowship

History

Degree Type

  • Doctor of Philosophy

Department

  • Computer Science

Campus location

  • West Lafayette

Advisor/Supervisor/Committee Chair

Jeremiah Blocki

Additional Committee Member 2

Mikhail J. Atallah

Additional Committee Member 3

Elena Grigorescu

Additional Committee Member 4

Hemanta K. Maji

Additional Committee Member 5

Vasileios Zikas

Usage metrics

    Categories

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC