CryptoDB
The Parallel Reversible Pebbling Game: Analyzing the PostQuantum Security of iMHFs
Authors: 


Download:  
Presentation:  Slides 
Conference:  TCC 2022 
Abstract:  The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, spacetime, cumulative space) necessary to evaluate a function $f$ with a static datadependency graph $G$. Of particular interest in the field of cryptography are dataindependent memoryhard 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 bruteforce preimage attack over a fixed domain $\mathcal{X}$, i.e., given $y \in \{0,1\}^*$ find $x \in \mathcal{X}$ such that $f_{G,H}(x)=y$. While a classical attacker will need to evaluate the function $f_{G,H}$ at least $m=\mathcal{X}$ times a quantum attacker running Grover's algorithm only requires $O(\sqrt{m})$ 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 spacetime 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 evaluating $f_{G,H}$. Motivated by this observation we introduce a new parallel reversible pebbling game which captures additional restrictions imposed by the NoDeletion Theorem in Quantum Computing. We apply our new reversible pebbling game to analyze the reversible spacetime complexity of several important graphs: Line Graphs, Argon2iA, Argon2iB, and DRSample. Specifically, (1) we show that a line graph of size $N$ has reversible spacetime complexity at most $O(N^{1+\frac{2}{\sqrt{\log N}}})$. (2) We show that any $(e,d)$reducible DAG has reversible spacetime complexity at most $O(Ne+dN2^d)$. In particular, this implies that the reversible spacetime complexity of Argon2iA and Argon2iB are at most $O(N^2 \log \log N/\sqrt{\log N})$ and $O(N^2/\sqrt[3]{\log N})$, respectively. (3) We show that the reversible spacetime complexity of DRSample is at most $O(N^2 \log \log N/\log N)$. We also study the cumulative pebbling cost of reversible pebblings extending a (nonreversible) pebbling attack of Alwen and Blocki on depthreducible graphs. 
BibTeX
@inproceedings{tcc202232581, title={The Parallel Reversible Pebbling Game: Analyzing the PostQuantum Security of iMHFs}, publisher={SpringerVerlag}, author={Jeremiah Blocki and Blake Holman and Seunghoon Lee}, year=2022 }