Paper 2026/2920

Processor-Aware Quantum Time-Memory-Data Trade-Offs

Aniket Ghara, TCG CREST, The Academy of Scientific and Innovative Research
Suman Pal, TCG CREST, The Academy of Scientific and Innovative Research
Prokash Kumar Kundu, TCG CREST, The Academy of Scientific and Innovative Research
Arpita Maitra, TCG CREST, The Academy of Scientific and Innovative Research
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.