Paper 2020/075

Memory-Tight Reductions for Practical Key Encapsulation Mechanisms

Rishiraj Bhattacharyya


The efficiency of a black-box reduction is an important goal of modern cryptography. Traditionally, the time complexity and the success probability were considered as the main aspects of efficiency measurements. In CRYPTO 2017, Auerbach et al. introduced the notion of memory-tightness in cryptographic reductions and showed a memory-tight reduction of the existential unforgeability of the RSA-FDH signature scheme. Unfortunately, their techniques do not extend directly to the reductions involving intricate RO-programming. The problem seems to be inherent as all the other existing results on memory-tightness are lower bounds and impossibility results. In fact, Auerbach et al. conjectured that a memory-tight reduction for IND-CCA security of Hashed-ElGamal KEM is impossible. -We refute the above conjecture. Using a simple RO simulation technique, we provide memory-tight reductions of IND-CCA  security of the Cramer-Shoup and the ECIES version of Hashed-ElGamal KEM. - We prove memory-tight reductions for different variants of Fujisaki-Okamoto Transformation. We analyze the modular transformations introduced by  Hofheinz,  Hövermanns and Kiltz (TCC 2017). In addition to the constructions involving implicit rejection, we present a memory-tight reduction for the IND-CCA  security of the transformation ${\mbox{QFO}_m^\perp}$. Our techniques can withstand correctness-errors, and applicable to several lattice-based KEM candidates.

Note: Added reference to a concurrent work

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2020
Memory-tight ReductionHashed-ElGamalFO transformation
Contact author(s)
rishiraj bhattacharyya @ gmail com
2020-07-19: revised
2020-01-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rishiraj Bhattacharyya},
      title = {Memory-Tight Reductions for Practical Key Encapsulation Mechanisms},
      howpublished = {Cryptology ePrint Archive, Paper 2020/075},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.