Paper 2022/916

Post-Quantum Authenticated Encryption against Chosen-Ciphertext Side-Channel Attacks

Melissa Azouaoui, NXP (Germany)
Yulia Kuzovkova, NXP (Germany)
Tobias Schneider, NXP (Austria)
Christine van Vredendaal, NXP (Netherlands)

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 some 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. To sufficiently protect PQC KEMs on embedded devices against such a powerful CC-SCA, masking at increasingly higher order is required, which induces a considerable overhead. In this work, we propose to use a conceptually simple construction, the $\mathcal{E}t\mathcal{S}$ KEM, that alleviates the impact of CC-SCA. It uses the Encrypt-then-Sign ($\mathcal{E}t\mathcal{S}$) paradigm introduced by Zheng at ISW ’97 and further analyzed by An, Dodis and Rabin at EUROCRYPT ’02, and instantiates a postquantum authenticated KEM in the outsider-security model. While the construction is generic, we apply it to the CRYSTALS-Kyber KEM, relying on the CRYSTALS-Dilithium and Falcon signature schemes. We show that a CC-SCA-protected $\mathcal{E}t\mathcal{S}$ KEM version of CRYSTALS-Kyber requires less than 10% of the cycles required for the CC-SCA-protected FO-based KEM, at the cost of additional data/communication overhead. We additionally show that the cost of protecting the $\mathcal{E}t\mathcal{S}$ KEM against fault injection attacks, necessarily due to the added signature verification, remains negligible compared to the large cost of masking the FO transform at higher orders. Lastly, we discuss relevant embedded use cases for our $\mathcal{E}t\mathcal{S}$ KEM construction.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in TCHES 2022
Post-Quantum Cryptography Side-Channel Attacks Chosen-Ciphertext Attacks Authenticated Key Exchange
Contact author(s)
melissa azouaoui @ nxp com
yulia kuzovkova_2 @ nxp com
tobias schneider @ nxp com
christine cloostermans @ nxp com
2022-07-25: revised
2022-07-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Melissa Azouaoui and Yulia Kuzovkova and Tobias Schneider and Christine van Vredendaal},
      title = {Post-Quantum Authenticated Encryption against Chosen-Ciphertext Side-Channel Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2022/916},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.