International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Joseph Jaeger , Georgia Institute of Technology
Akshaya Kumar , Georgia Institute of Technology
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
Abstract: 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.
Video from ASIACRYPT 2022
  title={Memory-Tight Multi-Challenge Security of Public-Key Encryption},
  author={Joseph Jaeger and Akshaya Kumar},