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.