## CryptoDB

### Paper: Memory-Tight Multi-Challenge Security of Public-Key Encryption

Authors: Joseph Jaeger , Georgia Institute of Technology Akshaya Kumar , Georgia Institute of Technology Search ePrint Search Google Slides ASIACRYPT 2022 We give the first examples of public-key encryption schemes which can be proven to achieve multi-challenge, multi-user CCA security via reductions that are tight in time, advantage, and memory. Our constructions are obtained by applying the KEM-DEM paradigm to variants of Hashed ElGamal and the Fujisaki-Okamoto transformation that are augmented by adding uniformly random strings to their ciphertexts. The reductions carefully combine recent proof techniques introduced by Bhattacharyya'20 and Ghoshal-Ghosal-Jaeger-Tessaro'22. Our proofs for the augmented ECIES version of Hashed-ElGamal make use of a new computational Diffie-Hellman assumption wherein the adversary is given access to a pairing to a random group, which we believe may be of independent interest.
##### BibTeX
@inproceedings{asiacrypt-2022-32639,
title={Memory-Tight Multi-Challenge Security of Public-Key Encryption},
publisher={Springer-Verlag},
author={Joseph Jaeger and Akshaya Kumar},
year=2022
}