(Un)breakable Curses - Re-encryption in the Fujisaki-Okamoto Transform

Kathrin Hövelmanns, Andreas Hülsing, Christian Majenz, Fabrizio Sisinni (Corresponding author-nrf)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

The Fujisaki-Okamoto transform (FO) is the go-to method for achieving chosen-ciphertext (CCA) security for post-quantum key encapsulation mechanisms (KEMs). An important step in FO is augmenting the decryption/decapsulation algorithm with a re-encryption step – the decrypted message is re-encrypted to check whether the correct encryption randomness was used. While solving a security problem (ciphertext-malleability), re-encryption has turned out to introduce side-channel vulnerabilities and is computationally expensive, which has lead designers to searching for alternatives. In this work, we perform a comprehensive study of such alternatives. We formalize a central security property, computational rigidity, and show that it is sufficient for obtaining CCA security. We present a framework for analyzing algorithms that can replace re-encryption and still achieve rigidity, and analyze existing proposals in this framework. Along the way, we pick up a novel QROM security statement for explicitly rejecting KEMs based on deterministic PKE schemes, something that so far only was possible when requiring a hard-to-ensure quantum property for the base PKE scheme.

Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2025
Subtitle of host publication44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4–8, 2025, Proceedings, Part II
EditorsSerge Fehr, Pierre-Alain Fouque
Place of PublicationCham
PublisherSpringer
Pages245-274
Number of pages30
ISBN (Electronic)978-3-031-91124-8
ISBN (Print)978-3-031-91123-1
DOIs
Publication statusPublished - 28 Apr 2025
Event44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025 - Madrid, Spain
Duration: 4 May 20258 May 2025

Publication series

NameLecture Notes in Computer Science (LNCS)
Volume15602
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025
Country/TerritorySpain
CityMadrid
Period4/05/258/05/25

Keywords

  • Fujisaki-Okamoto transformation
  • NIST
  • post-quantum security
  • Public-key encryption
  • QROM
  • re-encryption
  • side-channel attacks

Fingerprint

Dive into the research topics of '(Un)breakable Curses - Re-encryption in the Fujisaki-Okamoto Transform'. Together they form a unique fingerprint.

Cite this