## CryptoDB

### Paper: 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 DOI: 10.1007/978-3-030-45724-2_2 (login may be required) Search ePrint Search Google Slides EUROCRYPT 2020 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.
##### 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
}