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

ePrint Report: 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 and/or keys.


The reductions carefully combine recent proof techniques introduced …

cca challenge encryption eprint report key keys memory paradigm public random report security strings transformation