International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Akshaya Kumar

Publications

Year
Venue
Title
2022
ASIACRYPT
Memory-Tight Multi-Challenge Security of Public-Key Encryption 📺
Joseph Jaeger Akshaya Kumar
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.

Coauthors

Joseph Jaeger (1)