You are looking at a specific version 20210408:122227 of this paper. See the latest version.

Paper 2021/448

On the Memory-Tightness of Hashed ElGamal

Ashrujit Ghoshal and Stefano Tessaro

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
DOI
10.1007/978-3-030-45724-2_2
Keywords
Public-key cryptographymemory-tightnesslower boundsgeneric group modelfoundationscompression arguments
Contact author(s)
ashrujit @ cs washington edu
History
2021-04-08: received
Short URL
https://ia.cr/2021/448
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.