International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Jeremiah Blocki , Purdue University
Blake Holman , Purdue University
Seunghoon Lee , Purdue University
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2022
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 fG,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 fG,H multiple times as well as the total cost to run a brute-force preimage attack over a fixed domain X, i.e., given y∈{0,1}∗ find x∈X such that fG,H(x)=y. While a classical attacker will need to evaluate the function fG,H at least m=|X| times a quantum attacker running Grover's algorithm only requires O(m) blackbox calls to a quantum circuit CG,H evaluating the function fG,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 CG,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 fG,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 O(N1+2log⁡N). (2) We show that any (e,d)-reducible DAG has reversible space-time complexity at most O(Ne+dN2d). In particular, this implies that the reversible space-time complexity of Argon2i-A and Argon2i-B are at most O(N2log⁡log⁡N/log⁡N) and O(N2/log⁡N3), respectively. (3) We show that the reversible space-time complexity of DRSample is at most O(N2log⁡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.
BibTeX
@inproceedings{tcc-2022-32581,
  title={The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs},
  publisher={Springer-Verlag},
  author={Jeremiah Blocki and Blake Holman and Seunghoon Lee},
  year=2022
}