[Resource Topic] 2021/448: On the Memory-Tightness of Hashed ElGamal

Welcome to the resource topic for 2021/448

On the Memory-Tightness of Hashed ElGamal

Authors: Ashrujit Ghoshal, Stefano Tessaro


We study the memory-tightness of security reductions in public-key cryptography, focusing in particular on Hashed ElGamal. We prove that any 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 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.

ePrint: https://eprint.iacr.org/2021/448

Talk: https://www.youtube.com/watch?v=K-BiKHXPoF4

Slides: https://iacr.org/submit/files/slides/2020/eurocrypt/ec2020/226/slides.pdf

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .