International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the Memory-Tightness of Hashed ElGamal

Authors:
Ashrujit Ghoshal , Paul G. Allen School of Computer Science & Engineering, University of Washington
Stefano Tessaro , Paul G. Allen School of Computer Science & Engineering, University of Washington
Download:
DOI: 10.1007/978-3-030-45724-2_2 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2020
Abstract: We study the memory-tightness of security reductions in public-key cryptography, focusing in particular on Hashed ElGamal. We prove that any {\em straightline} (i.e., without rewinding) black-box reduction needs memory which grows linearly with the number of queries of the adversary it has access to, as long as this reduction treats the underlying group generically. This makes progress towards proving a conjecture by Auerbach {\em et al.} (CRYPTO 2017), and is also the first lower bound on memory-tightness for a concrete cryptographic scheme (as opposed to generalized reductions across security notions). Our proof relies on compression arguments in the generic group model.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30197,
  title={On the Memory-Tightness of Hashed ElGamal},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={Public-key cryptography;memory tightness;lower bounds;generic group model;foundations;compression arguments},
  volume={12105},
  doi={10.1007/978-3-030-45724-2_2},
  author={Ashrujit Ghoshal and Stefano Tessaro},
  year=2020
}