Hathifushi Island panorama

Douglas Stebila

Tight multi-challenge security reductions for key encapsulation mechanisms

Summary of security results on the salted Fujiaki–Okamoto (SFO) transform
Summary of security results on the salted Fujiaki–Okamoto (SFO) transform

Abstract

A key encapsulation mechanism (KEM) allows two parties to establish a shared secret key using only public communication. For post-quantum KEMs, the most widespread approach is to design a passively secure public-key encryption (PKE) scheme and then apply the Fujisaki–Okamoto (FO) transform that turns any such PKE scheme into an IND-CCA secure KEM. While the base security requirement for KEMs is typically IND-CCA security, adversaries in practice can sometimes observe and attack many public keys and/or ciphertexts, which is referred to as multi-challenge security. FO does not necessarily guarantee multi-challenge security: for example, FrodoKEM, a Round 3 alternate in NIST’s post-quantum project, used FO to achieve IND-CCA security, but was subsequently shown to be vulnerable to attackers that can target multiple ciphertexts. To avert this multi-ciphertext attack, the FrodoKEM team added a salt to the encapsulation procedure and proved that this does not degrade (single-ciphertext) IND-CCA security. The formal analysis of whether this indeed averts multi-ciphertext attacks, however, was left open, which we address in this work.

Firstly, we formalize FrodoKEM's approach as a new variant of the FO transform, called the salted FO transform. Secondly, we give tight reductions from multi-challenge security of the resulting KEM to multi-challenge security of the underlying public key encryption scheme, in both the random oracle model (ROM) and the quantum-accessible ROM (QROM). Together these results justify the multi-ciphertext security of the salted FrodoKEM scheme, and can also be used generically by other schemes requiring multi-ciphertext security.

Keywords: Fujisaki–Okamoto transform, key exchange, quantum random oracle model, post-quantum, multi-challenge security, FrodoKEM

Reference

Lewis Glabush, Kathrin Hövelmanns, Douglas Stebila. Tight multi-challenge security reductions for key encapsulation mechanisms. Technical report. February 2025.

Download

BibTeX

Funding

This research was supported by:
  • Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2022-03187
  • NSERC Alliance grant ALLRP 578463-22
  • NWO VENI grant (Project No. VI.Veni.222.397)