Paper 2021/1409

Hiding in Plain Sight: Memory-tight Proofs via Randomness Programming

Ashrujit Ghoshal, Riddhi Ghosal, Joseph Jaeger, and Stefano Tessaro


This paper continues the study of memory-tight reductions (Auerbach et al, CRYPTO '17). These are reductions that only incur minimal memory costs over those of the original adversary, allowing precise security statements for memory-bounded adversaries (under appropriate assumptions expressed in terms of adversary time and memory usage). Despite its importance, only a few techniques to achieve memory-tightness are known and impossibility results in prior works show that even basic, textbook reductions cannot be made memory-tight. This paper introduces a new class of memory-tight reductions which leverage random strings in the interaction with the adversary to hide state information, thus shifting the memory costs to the adversary. We exhibit this technique with several examples. We give memory-tight proofs for digital signatures allowing many forgery attempts when considering randomized message distributions or probabilistic RSA-FDH signatures specifically. We prove security of the authenticated encryption scheme Encrypt-then-PRF with a memory-tight reduction to the underlying encryption scheme. By considering specific schemes or restricted definitions we avoid generic impossibility results of Auerbach et al. (CRYPTO '17) and Ghoshal et al. (CRYPTO '20). As a further case study, we consider the textbook equivalence of CCA-security for public-key encryption for one or multiple encryption queries. We show two qualitatively different memory-tight versions of this result, depending on the considered notion of CCA security.

Available format(s)
Publication info
A major revision of an IACR publication in Eurocrypt 2022
Provable securitymemory-tightnesstime-memory trade-offs
Contact author(s)
ashrujit @ cs washington edu
2022-03-02: revised
2021-10-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ashrujit Ghoshal and Riddhi Ghosal and Joseph Jaeger and Stefano Tessaro},
      title = {Hiding in Plain Sight: Memory-tight Proofs via Randomness Programming},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1409},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.