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.

By admin