Paper 2022/1503
The Parallel Reversible Pebbling Game: Analyzing the PostQuantum Security of iMHFs
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 $\mathcal{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 for 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 $\mathcal{O}\left(N^{1+\frac{2}{\sqrt{\log N}}}\right)$. (2) We show that any $(e,d)$reducible DAG has reversible spacetime complexity at most $\mathcal{O}(Ne+dN2^d)$. In particular, this implies that the reversible spacetime complexity of Argon2iA and Argon2iB are at most $\mathcal{O}(N^2 \log \log N/\sqrt{\log N})$ and $\mathcal{O}(N^2/\sqrt[3]{\log N})$, respectively. (3) We show that the reversible spacetime complexity of DRSample is at most $\mathcal{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.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 A major revision of an IACR publication in TCC 2022
 Keywords
 Parallel Reversible Pebbling Argon2i DRSample DataIndependent MemoryHard Function
 Contact author(s)

jblocki @ purdue edu
holman14 @ purdue edu
lee2856 @ purdue edu  History
 20221106: approved
 20221106: received
 See all versions
 Short URL
 https://ia.cr/2022/1503
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1503, author = {Jeremiah Blocki and Blake Holman and Seunghoon Lee}, title = {The Parallel Reversible Pebbling Game: Analyzing the PostQuantum Security of iMHFs}, howpublished = {Cryptology ePrint Archive, Paper 2022/1503}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1503}}, url = {https://eprint.iacr.org/2022/1503} }