Paper 2023/856

The Query-Complexity of Preprocessing Attacks

Ashrujit Ghoshal, University of Washington
Stefano Tessaro, University of Washington

A large number of works prove lower bounds on space-time trade-offs in preprocessing attacks, i.e., trade-offs between the size of the advice and the time needed to break a scheme given such advice. We contend that the question of how much {\em time} is needed to produce this advice is equally important, and often highly non-trivial. However, this question has received significantly less attention. In this paper, we present lower bounds on the complexity of preprocessing attacks that depend on both offline and online time. As in the case of space-time trade-offs, we focus in particular on settings with ideal primitives, where both the offline and online time-complexities are approximated by the number of queries to the given primitive. We give generic results that highlight the benefits of salting to generically increase the offline costs of preprocessing attacks. The majority of our paper presents several results focusing on {\em salted} hash functions. In particular, we provide a fairly involved analysis of the pre-image-and collision-resistance security of the (two-block) Merkle-Damgård construction in our model.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2023
offline-online tradeoffstime-space tradeoffsideal modelsrandom oraclesMerkle-Damgård
Contact author(s)
ashrujit @ cs washington edu
tessaro @ cs washington edu
2023-06-07: revised
2023-06-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ashrujit Ghoshal and Stefano Tessaro},
      title = {The Query-Complexity of Preprocessing Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2023/856},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.