Paper 2026/2920
Processor-Aware Quantum Time-Memory-Data Trade-Offs
Abstract
Time--memory--data trade-offs (TMDTOs) provide a fundamental framework for cryptanalytic attacks that balance preprocessing,memory, online computation, and available target data. In the quantum setting, Dunkelman et al. introduced quantum TMDTO attacks based on GroverMatch, obtaining the relation $N^2=T^{4/3}M^2D^2$ for multiple-target inversion using a single quantum processor. In this work, we introduce a processor-aware formulation of quantum TMDTOs by incorporating parallel quantum computation into the GroverMatch framework. We partition the flavour space across $K$ parallel quantum processors and use quantum counting to identify a promising local subspace, followed by Grover search within that subspace. Under an idealized parallel wall-clock model, we show that the online complexity becomes $ T_K = \frac{t^{3/2}}{\sqrt{K}} $, and consequently derive the processor-aware trade-off $ N^2 = T_K^{4/3}M^2D^2K^{2/3} $. The relation specializes to the previously known single-processor quantum TMDTO relation when $K=1$. We instantiate the framework for both Quantum Hellman and Quantum Rainbow constructions and show that, for fixed $N$, $M$, and $D$, parallelization reduces the online wall-clock time by a factor $\sqrt{K}$, at the cost of increasing the aggregate quantum work by a factor of $\sqrt{K}$. We further analyze the resulting trade-off against generic Grover search under both single-processor and equal-processor-budget comparisons. Our results provide a processor-aware characterization of quantum TMDTO attacks and clarify the trade-off between quantum hardware parallelism and online cryptanalytic time.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Distinguished PointDistributed GroverHellman AttackRainbow TableTime-Memory-Data trade off.
- Contact author(s)
-
aniketghara201 @ gmail com
contactsumanpal1999 @ gmail com
prokash kumar kundu 180 @ tcgcrest org
arpita maitra @ tcgcrest org - History
- 2026-11-21: approved
- 2026-11-17: received
- See all versions
- Short URL
- https://ia.cr/2026/2920
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2920,
author = {Aniket Ghara and Suman Pal and Prokash Kumar Kundu and Arpita Maitra},
title = {Processor-Aware Quantum Time-Memory-Data Trade-Offs},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2920},
year = {2026},
url = {https://eprint.iacr.org/2026/2920}
}