Paper 2020/150

On the Security of NTS-KEM in the Quantum Random Oracle Model

Varun Maram

Abstract

NTS-KEM is one of the 17 post-quantum public-key encryption (PKE) and key establishment schemes remaining in contention for standardization by NIST. It is a code-based cryptosystem that starts with a combination of the (weakly secure) McEliece and Niederreiter PKE schemes and applies a variant of the Fujisaki-Okamoto (Journal of Cryptology 2013) or Dent (IMACC 2003) transforms to build an IND-CCA secure key encapsulation mechanism (KEM) in the classical random oracle model (ROM). Such generic KEM transformations were also proven to be secure in the quantum ROM (QROM) by Hofheinz et. al. (TCC 2017), Jiang et. al. (Crypto 2018) and Saito et. al. (Eurocrypt 2018). However, the NTS-KEM specification has some peculiarities which means that these security proofs do not directly apply to it. This paper identifies a subtle issue in the IND-CCA security proof of NTS-KEM in the classical ROM, as detailed in its initial NIST second round submission, and proposes some slight modifications to its specification which not only fixes this issue but also makes it IND-CCA secure in the QROM. We use the techniques of Jiang et. al. (Crypto 2018) and Saito et. al. (Eurocrypt 2018) to establish our IND-CCA security reduction for the modified version of NTS-KEM, achieving a loss in tightness of degree 2; a quadratic loss of this type is believed to be generally unavoidable for reductions in the QROM (Jiang at. al., ePrint 2019/494). Following our results, the NTS-KEM team has accepted our proposed changes by including them in an update to their second round submission to the NIST process.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. CBCrypto 2020
DOI
10.1007/978-3-030-54074-6_1
Keywords
code-basedKEMquantum random oracle modelIND-CCA securityNIST standardization
Contact author(s)
vmaram @ inf ethz ch
History
2020-07-30: revised
2020-02-13: received
See all versions
Short URL
https://ia.cr/2020/150
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/150,
      author = {Varun Maram},
      title = {On the Security of NTS-KEM in the Quantum Random Oracle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2020/150},
      year = {2020},
      doi = {10.1007/978-3-030-54074-6_1},
      note = {\url{https://eprint.iacr.org/2020/150}},
      url = {https://eprint.iacr.org/2020/150}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.