TY - GEN
T1 - (Un)breakable Curses - Re-encryption in the Fujisaki-Okamoto Transform
AU - Hövelmanns, Kathrin
AU - Hülsing, Andreas
AU - Majenz, Christian
A2 - Sisinni, Fabrizio
A2 - Fehr, Serge
A2 - Fouque, Pierre-Alain
PY - 2025/4/28
Y1 - 2025/4/28
N2 - 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.
AB - 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.
KW - Fujisaki-Okamoto transformation
KW - NIST
KW - post-quantum security
KW - Public-key encryption
KW - QROM
KW - re-encryption
KW - side-channel attacks
UR - http://www.scopus.com/inward/record.url?scp=105004793604&partnerID=8YFLogxK
UR - https://eprint.iacr.org/2025/299.pdf
U2 - 10.1007/978-3-031-91124-8_9
DO - 10.1007/978-3-031-91124-8_9
M3 - Conference contribution
AN - SCOPUS:105004793604
SN - 978-3-031-91123-1
T3 - Lecture Notes in Computer Science (LNCS)
SP - 245
EP - 274
BT - Advances in Cryptology – EUROCRYPT 2025
PB - Springer
CY - Cham
T2 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025
Y2 - 4 May 2025 through 8 May 2025
ER -