Memory-Tight Reductions for Practical Key Encapsulation Mechanisms

Rishiraj Bhattacharyya*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 security of Hashed-ElGamal KEM is impossible. We refute the above conjecture. Using a simple RO simulation technique, we provide memory-tight reductions of 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 security of the transformation. Our techniques can withstand correctness-errors, and applicable to several lattice-based KEM candidates.

Original languageEnglish
Title of host publicationPublic-Key Cryptography – PKC 2020 - 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
EditorsAggelos Kiayias, Markulf Kohlweiss, Petros Wallden, Vassilis Zikas
PublisherSpringer Vieweg
Number of pages30
ISBN (Print)9783030453732
Publication statusPublished - 2020
Event23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, PKC 2020 - Edinburgh, United Kingdom
Duration: 4 May 20207 May 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12110 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, PKC 2020
Country/TerritoryUnited Kingdom

Bibliographical note

Funding Information:
We thank Eike Kiltz for encouraging us to write up and submit the work. We are thankful to the reviewers for their comments on this and the previous versions of the paper. The author is supported by SERB ECR/2017/001974.

Publisher Copyright:
© 2020, International Association for Cryptologic Research.


  • FO transformation
  • Hashed-ElGamal
  • Memory-tight reduction

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Memory-Tight Reductions for Practical Key Encapsulation Mechanisms'. Together they form a unique fingerprint.

Cite this