International Association for Cryptologic Research

International Association
for Cryptologic Research


The Query-Complexity of Preprocessing Attacks

Ashrujit Ghoshal , University of Washington
Stefano Tessaro , University of Washington
DOI: 10.1007/978-3-031-38545-2_16 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: 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, it 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 bulk 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\aard construction in our model.
  title={The Query-Complexity of Preprocessing Attacks},
  author={Ashrujit Ghoshal and Stefano Tessaro},