Post-Quantum Authenticated Encryption Against Chosen-Ciphertext Side-Channel Attacks Avoiding the FO-calypse



Over the last years, the side-channel analysis of Post-Quantum Cryptography (PQC) candidates in the NIST standardization initiative has received increased attention. In particular, it has been shown that most of the post-quantum Key Encapsulation Mechanisms (KEMs) are vulnerable to Chosen-Ciphertext Side-Channel Attacks (CC-SCA). These powerful attacks target the re-encryption step in the Fujisaki-Okamoto (FO) transform, which is commonly used to achieve CCA security in such schemes. In the first part of this talk, we demonstrate on the case study of CRYSTALS-Kyber that realizing sufficiently protected PQC KEMs on embedded devices against powerful CC-SCA is challenging and masking at increasingly higher order is required, which induces a considerable overhead. In the second part, we describe a conceptually simple construction, the Encrypt-then-Sign (EtS) KEM, that alleviates the impact of CC-SCA. It uses the EtS paradigm introduced by An, Dodis and Rabin at EUROCRYPT ’02, and instantiates a post-quantum authenticated KEM in the outsider-security model, in which we discuss relevant embedded use cases. While the construction is generic, we apply it to the CRYSTALS-Kyber KEM, relying on the CRYSTALS-Dilithium or the Falcon signature schemes,and show that a CC-SCA-protected EtS KEM version of CRYSTALS-Kyber requires less than 10% of the cycles required for the CC-SCA-protected FO-based KEM.


Paper: https://eprint.iacr.org/2022/916.pdf



Dr. Melissa Azouaoui

Security Engineer
NXP Semiconductors



Melissa Azouaoui is a cryptographer and security engineer at the Competence Center Crypto & Security of NXP Semiconductors. After receiving in 2017 her master’s degree from Universit´e Paris-Saclay, France, she completed her PhD in 2021 at Universit´e Catholique de Louvain, Belgium, and NXP Semiconductors, Germany, under the supervision of Pr. Fran,cois-Xavier Standaert and Dr. Vincent Verneuil, on the topic of side-channel countermeasures and security evaluations. Since 2021, her work at NXP Hamburg covers various topics of embedded PQC, including side-channel and fault injection attacks and countermeasures, with a particular focus on lattice and hash-based cryptography.