A note on IND-qCCA security in the ROM and its applications.

Zhenyu Hu, JianChun Jiang, Fuchun Sun

Marc Fischlin, Tobias Schmalz

Common authenticated encryption schemes are generally believed to remain secure in the post-quantum setting where adversaries with local quantum power interact classically with the users. This is apart from a square root loss in the security bound due to Grover's algorithm. This changes dramatically when one switches to a fully quantum setting where the adversary is allowed to interact with the users in superposition, called IND-qCCA security. Here, many well-known schemes become completely insecure, including the widely deplyoed Galois/Counter mode (GCM). Here we propose a modification to GCM and to its counterpart GCM-SIV that resurrects IND-qCCA security in the quantum setting for nonce-respecting adversaries. The key observation is to replace the universal hash functions GHASH and PolyVal in GCM and GCM-SIV by pairwise-independent versions.

Silvio M. Micali, Phillip Rogaway

Anna Jokiniemi

This thesis is an in-depth introduction to NIST's post-quantum Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM). We begin by introducing the problem at the core of ML-KEM, known as the Module Learning With Errors (MLWE) problem. In this problem, an adversary attempts to distinguish between samples selected from a specific distribution and samples from uniformly random samples. We also discuss the hardness of the MLWE problem, under the conjecture that certain lattice problems over modules are hard. ML-KEM utilizes a variant of the Fujisaki-Okamoto transformation, which employs a weakly secure Public-Key Encryption (PKE) scheme to construct a strongly secure key-encapsulation mechanism in the Random Oracle Model (ROM). We explain the working principle of the MLWE-based public-key encryption scheme and demonstrate how ML-KEM is constructed from it. Finally, we analyze the security of ML-KEM. We provide a tight security bound for IND-CCA security of ML-KEM in ROM, under the assumption that the underlying PKE is IND-CPA secure. Additionally, we present two security theorems in the Quantum Random Oracle Model (QROM). The first theorem establishes non-tightly IND-CCA security of ML-KEM in QROM if the MLWE problem is hard to solve. The second theorem assumes that the deterministic PKE is ciphertext-indistinguishable. Under this assumption, we derive a tighter bound for the IND-CCA security of ML-KEM in QROM.

Seung Geol Choi, Jonathan I. Katz, Ranjit Kumaresan +1 more

Lewis Glabush, Kathrin Hövelmanns, Douglas Stebila

Practical deployments of key encapsulation mechanisms (KEMs) may entail large servers each using their public keys to communicate with potentially millions of clients simultaneously. While the standard IND-CCA security definition for KEMs considers only a single challenge public key and single challenge ciphertext, it can be relevant to consider multi-target scenarios where the adversary aims to break one of many challenge ciphertexts, for one of many challenge public keys. Many post-quantum KEMs have been built by applying the Fujisaki-Okamoto (FO) transform to a public key encryption (PKE) scheme. Although the FO transform incurs only a few bits of security loss for the standard, single-challenge IND-CCA property, this does not hold in the multi-target setting. Attacks have been identified against standards-track FO-based KEMs with 128-bit message spaces (FrodoKEM-640 and HQC-128) which become feasible if the adversary is given many challenge ciphertexts (say, 2^64). These attacks exploit the deterministic encryption induced by the FO transform which allows the IND-CCA experiment to be reduced to a search problem on the message space, which in some cases may not be large enough to avoid collisions between pre-computation and challenge values. A cost effective way to amplify the hardness of this search problem is to add a random but public salt during encapsulation. While revised versions of FrodoKEM and HQC have used salts, there has been no proof showing that salting provides multi-ciphertext security. In this work, we formally analyze a salted variant of the Fujisaki-Okamoto transform, in the classical and quantum random oracle model (ROM); for the classical ROM, we show that multi-target IND-CCA security of the resulting KEM tightly reduces to the multi-target IND-CPA security of the underlying PKE. Our results imply that, for FrodoKEM and HQC at the 128-bit security level, replacing the FO transform with the salted variant can recover 62 bits of multi-target security, at the cost of a very small overhead increase.