Paper 2024/334
The Impact of Reversibility on Parallel Pebbling
Abstract
The (parallel) classical black pebbling game is a helpful abstraction which allows us to analyze the resources (time, space, spacetime, cumulative space) necessary to evaluate a function $f$ with a static datadependency graph $G$ on a (parallel) computer. In particular, the parallel black pebbling game has been used as a tool to quantify the (in)security of DataIndependent MemoryHard Functions (iMHFs). Recently Blocki et al. (TCC 2022) introduced the parallel reversible pebbling game as a tool to analyze resource requirements when we additionally require that computation is reversible. Intuitively, the parallel reversible pebbling game extends the classical parallel black pebbling game by imposing restrictions on when pebbles can be removed. By contrast, the classical black pebbling game imposes no restrictions on when pebbles can be removed to free up space. One of the primary motivations of the parallel reversible pebbling game is to provide a tool to analyze the full cost of quantum preimage attacks against an iMHF. However, while there is an extensive line of work analyzing pebbling complexity in the (parallel) black pebbling game, comparatively little is known about the parallel reversible pebbling game. Our first result is a lower bound of $\Omega\left(N^{1+1/\sqrt{\log N}} \right)$ on the reversible cumulative pebbling cost for a line graph on $N$ nodes. This yields a separation between classical and reversible pebbling costs demonstrating that the reversibility constraint can increase cumulative pebbling costs (and spacetime costs) by a multiplicative factor of $\Omega\left(N^{1/\sqrt{\log N}} \right)$  the classical pebbling cost (spacetime or cumulative) for a line graph is just $\mathcal{O}(N)$. On the positive side, we prove that any classical parallel pebbling can be transformed into a reversible pebbling strategy whilst increasing spacetime (resp. cumulative memory) costs by a multiplicative factor of at most $\mathcal{O}\left(N^{2/\sqrt{\log N}}\right)$ (resp. $\mathcal{O}\left(N^{\mathcal{O}(1)/\sqrt[4]{\log N}}\right)$). We also analyze the impact of the reversibility constraint on the cumulative pebbling cost of depthrobust and depthreducible DAGs exploiting reversibility to improve constant factors in a prior lower bound of Alwen et al. (EUROCRYPT 2017). For depthreducible DAGs we show that the stateoftheart recursive pebbling techniques of Alwen et al. (EUROCRYPT 2017) can be converted into a recursive reversible pebbling attack without any asymptotic increases in pebbling costs. Finally, we extend a result of Blocki et al. (ITCS 2020) to show that it is Unique Games hard to approximate the reversible cumulative pebbling cost of a DAG $G$ to within any constant factor.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Preprint.
 Keywords
 Parallel Reversible PebblingDataIndependent MemoryHard FunctionQuantum Preimage Attacks
 Contact author(s)

jblocki @ purdue edu
holman14 @ purdue edu
lee2856 @ purdue edu  History
 20240227: approved
 20240226: received
 See all versions
 Short URL
 https://ia.cr/2024/334
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/334, author = {Jeremiah Blocki and Blake Holman and Seunghoon Lee}, title = {The Impact of Reversibility on Parallel Pebbling}, howpublished = {Cryptology ePrint Archive, Paper 2024/334}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/334}}, url = {https://eprint.iacr.org/2024/334} }