Blake Holman

selected publications

1. The Impact of Reversibility on Parallel Pebbling

   Blocki, Jeremiah,  Holman, Blake, and Lee, Seunghoon

   2024

   Abs PDF

   We use parallel pebbling to design parallel quantum circuits with low amortized space-time complexity. In particular, we show that we can map any classical algorithm for a function to a quantum algorithm computing the function, with only a subpolynomial overhead in amortized space-time complexity. We use this transformation to design quantum attacks against several practical memory-hard functions, and show that these attacks are near-optimal.

2. The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs

   Blocki, Jeremiah,  Holman, Blake, and Lee, Seunghoon

   In TCC 2022

   Abs PDF

   The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function f with a static data-dependency graph G. Of particular interest in the field of cryptography are data-independent memory-hard functions f_G,H which are defined by a directed acyclic graph (DAG) G and a cryptographic hash function H. The pebbling complexity of the graph G characterizes the amortized cost of evaluating f_G,H multiple times as well as the total cost to run a brute-force preimage attack over a fixed domain \mathcalX, i.e., given y ∈{0,1}^* find x ∈\mathcalX such that f_G,H(x)=y. While a classical attacker will need to evaluate the function f_G,H at least m=|\mathcalX| times a quantum attacker running Grover’s algorithm only requires Ø\sqrtm blackbox calls to a quantum circuit C_G,H evaluating the function f_G,H. Thus, to analyze the cost of a quantum attack it is crucial to understand the space-time cost (equivalently width times depth) of the quantum circuit C_G,H. We first observe that a legal black pebbling strategy for the graph G does not necessarily imply the existence of a quantum circuit with comparable complexity — in contrast to the classical setting where any efficient pebbling strategy for G corresponds to an algorithm with comparable complexity for evaluating f_G,H. Motivated by this observation we introduce a new parallel reversible pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new reversible pebbling game to analyze the reversible space-time complexity of several important graphs: Line Graphs, Argon2i-A, Argon2i-B, and DRSample. Specifically, (1) we show that a line graph of size N has reversible space-time complexity at most ØN^1+\frac2\sqrt\log N. (2) We show that any (e,d)-reducible DAG has reversible space-time complexity at most ØNe+dN2^d. In particular, this implies that the reversible space-time complexity of Argon2i-A and Argon2i-B are at most ØN^2 \log \log N/\sqrt\log N and ØN^2/\sqrt[3]\log N, respectively. (3) We show that the reversible space-time complexity of DRSample is at most ØN^2 \log \log N/\log N. We also study the cumulative pebbling cost of reversible pebblings extending a (non-reversible) pebbling attack of Alwen and Blocki on depth-reducible graphs.

3. Sustained Space and Cumulative Complexity Trade-offs for Data-Dependent Memory-Hard Functions

   Blocki, Jeremiah, and Holman, Blake

   In CRYPTO 2022

   Abs PDF

   Memory-hard functions (MHFs) are a useful cryptographic primitive which can be used to design egalitarian proof of work puzzles and to protect low entropy secrets like passwords against brute-force attackers. Intuitively, a memory-hard function is a function whose evaluation costs are dominated by memory costs even if the attacker uses specialized hardware (FPGAs/ASICs), and several cost metrics have been proposed to quantify this intuition. For example, space-time cost looks at the product of running time and the maximum space usage over the entire execution of an algorithm. Alwen and Serbinenko (STOC 2015) observed that the space-time cost of evaluating a function multiple times may not scale linearly in the number of instances being evaluated and introduced the stricter requirement that a memory-hard function has high cumulative memory complexity (CMC) to ensure that an attacker’s amortized space-time costs remain large even if the attacker evaluates the function on multiple different inputs in parallel. Alwen et al. (EUROCRYPT 2018) observed that the notion of CMC still gives the attacker undesirable flexibility in selecting space-time tradeoffs e.g., while the MHF Scrypt has maximal CMC $Ω(N^2), an attacker could evaluate the function with constant O(1) memory in time O(N^2). Alwen et al. introduced an even stricter notion of Sustained Space complexity and designed an MHF which has s=Ω(N/\log N) sustained complexity t=Ω(N) i.e., any algorithm evaluating the function in the parallel random oracle model must have at least t=Ω(N) steps where the memory usage is at least Ω(N/\log N). In this work, we use dynamic pebbling games and dynamic graphs to explore tradeoffs between sustained space complexity and cumulative memory complexity for data-dependent memory-hard functions such as Argon2id and Scrypt. We design our own dynamic graph (dMHF) with the property that any dynamic pebbling strategy either (1) has Ω(N) rounds with Ω(N) space, or (2) has CMC Ω(N^3-ε) — substantially larger than N^2. For Argon2id we show that any dynamic pebbling strategy either(1) has Ω(N) rounds with Ω(N^1-ε) space, or (2) has CMC ω(N^2). We also present a dynamic version of DRSample (Alwen et al. 2017) for which any dynamic pebbling strategy either (1) has Ω(N) rounds with Ω(N/\log N) space, or (2) has CMC Ω(N^3/\log N)$.