Paper 2022/1503

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

Abstract

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) $$ and a cryptographic hash function $$. The pebbling complexity of the graph $$ characterizes the amortized cost of evaluating $$ multiple times as well as the total cost to run a brute-force preimage attack over a fixed domain $$, i.e., given $$ find $$ such that $$. While a classical attacker will need to evaluate the function $$ at least $$ times a quantum attacker running Grover's algorithm only requires $$ blackbox calls to a quantum circuit $$ evaluating the function $$. 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 $$. We first observe that a legal black pebbling strategy for the graph $$ 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 $$ corresponds to an algorithm with comparable complexity for evaluating $$. 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 $$ has reversible space-time complexity at most $$. (2) We show that any $$-reducible DAG has reversible space-time complexity at most $$. In particular, this implies that the reversible space-time complexity of Argon2i-A and Argon2i-B are at most $$ and $$, respectively. (3) We show that the reversible space-time complexity of DRSample is at most $$. We also study the cumulative pebbling cost of reversible pebblings extending a (non-reversible) pebbling attack of Alwen and Blocki on depth-reducible graphs.