On the Security of NTS-KEM in the Quantum Random Oracle Model | SpringerLink
Skip to main content
Springer Nature Link
Log in

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

  • Conference paper
  • First Online:
Code-Based Cryptography (CBCrypto 2020)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 12087))

Included in the following conference series:

  • 430 Accesses

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 et 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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    In explicit rejection, the symbol “\(\perp \)” is returned (instead of a pseudorandom key \(H(\mathbf {z} \mid \mathbf {c})\) as is the case in implicit rejection) for the decapsulation of invalid ciphertexts.

  2. 2.

    The one-way to hiding (OW2H) lemma, introduced in [Unr14], provides a generic reduction from a hiding-style property (indistinguishability) to a one-wayness-style property (unpredictability) in the QROM.

  3. 3.

    We are referring to the latest version of [JZC+18] on the Cryptology ePrint Archive – Report 2017/1096, Version 20190703 – which differs from the conference version in that Lemma 3 no longer requires \(\mathcal {O}_1(x)\) to be independent from \(\mathcal {O}_2(.)\). Also we would be working with a condensed version of the lemma where we do not need\(\mathcal {O}_1(x)\) to be uniformly distributed for any fixed \(\mathcal {O}_1(x')\) (\(x' \ne x\)), \(\mathcal {O}_2(.)\), inp and x.

  4. 4.

    Known as a binary Goppa code, as described in   [ACP+19a].

  5. 5.

    Our suggested routine, as adopted in the updated version of NTS-KEM   [ACP+19b].

  6. 6.

    On the contrary, if there exists an error vector \(\mathbf {e} '\) with \({{\,\mathrm{hw}\,}}(\mathbf {e} ') = \tau \) such that \(\text {Encode}(\mathsf {pk}, \mathbf {e} ') = \mathbf {c} \), then because of NTS-KEM correctness, the decoding algorithm should recover error vector \(\mathbf {e} ' (\ne \mathbf {e})\) when given \(\mathbf {c} \) as input.

  7. 7.

    On the contrary, if \(\text {Encode}(\mathsf {pk}, \mathbf {e'}) = \mathbf {c} \), then because of NTS-KEM correctness, we have \(\text {Decode}(\mathsf {sk}', \mathbf {c}) = \mathbf {e'} = \mathbf {e} \). This means that the checks \({{\,\mathrm{hw}\,}}(\mathbf {e}) = \tau \) and \(\text {Encode}(\mathsf {pk}, \mathbf {e}) = \mathbf {c} \) are satisfied, a contradiction.

  8. 8.

    For error vectors \(\mathbf {e} \in \mathbb {F}_2^n\) with \({{\,\mathrm{hw}\,}}(\mathbf {e}) \ne \tau \), the reason we defined \(g(\mathbf {e})\) – even though \(\mathcal {A} \) only has access to \(H_4^n (\mathbf {1_a} \mid .)\) in games G\(_3\) and G\(_4\) – is to have a consistent domain (\(\mathbb {F}_2^n\)) and co-domain (\(\mathbb {F}_2^\ell \)) between the oracles \(H_1^n(.)\) and \(H_4^n \circ g\,(.)\). This would be helpful, for example, when applying Lemma 3 in our setting.

  9. 9.

    For example, if we want to access \(H_1^n(.)\) by making queries to \((H_1^n \times [H_4^n \circ g])(.)\), then we just have to prepare a uniform superposition of all states in the output register corresponding to \(H_4^n \circ g(.)\).

  10. 10.

    The original OW2H lemma of   [Unr14] would have required \(\mathbf {e^*} \) to be sampled uniformly in \(\mathbb {F}_2^n\), the domain of \((H_1^n \times [H_4^n \circ g])(.)\). Therefore we use Lemma 3 which generalizes to arbitrary distributions of \(\mathbf {e^*} \); in particular, .

References

  1. Albrecht, M., Cid, C., Paterson, K.G., Tjhai, C.J., Tomlinson, M.: NTS-KEM: NIST PQC Second Round Submission (2019). https://nts-kem.io/

  2. Albrecht, M., Cid, C., Paterson, K.G., Tjhai, C.J., Tomlinson, M.: NTS-KEM: NIST PQC Updated Second Round Submission (2019). https://nts-kem.io/

  3. Ambainis, A., Hamburg, M., Unruh, D.: Quantum security proofs using semi-classical oracles. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part II. LNCS, vol. 11693, pp. 269–295. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_10

    Chapter  Google Scholar 

  4. Boyd, C., Cliff, Y., Gonzalez Nieto, J., Paterson, K.G.: Efficient one-round key exchange in the standard model. In: Mu, Y., Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol. 5107, pp. 69–83. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70500-0_6

    Chapter  Google Scholar 

  5. Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_3

    Chapter  MATH  Google Scholar 

  6. Bindel, N., Hamburg, M., Hövelmanns, K., Hülsing, A., Persichetti, E.: Tighter proofs of CCA security in the quantum random oracle model. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019, Part II. LNCS, vol. 11892, pp. 61–90. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36033-7_3

    Chapter  MATH  Google Scholar 

  7. Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Denning, D.E., Pyle, R., Ganesan, R., Sandhu, R.S., Ashby, V. (eds.) ACM CCS 93: 1st Conference on Computer and Communications Security, Fairfax, Virginia, pp. 62–73. ACM Press (1993)

    Google Scholar 

  8. Boneh, D., Zhandry, M.: Secure signatures and chosen ciphertext security in a quantum computing world. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 361–379. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_21

    Chapter  MATH  Google Scholar 

  9. Cramer, R., Shoup, V.: Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput. 33(1), 167–226 (2003)

    Article  MathSciNet  Google Scholar 

  10. Dent, A.W.: A designer s guide to KEMs. In: Paterson, K.G. (ed.) Cryptography and Coding 2003. LNCS, vol. 2898, pp. 133–151. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-40974-8_12

    Chapter  Google Scholar 

  11. Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. J. Cryptol. 26(1), 80–101 (2013). https://doi.org/10.1007/s00145-011-9114-1

    Article  MathSciNet  MATH  Google Scholar 

  12. Fujisaki, E., Okamoto, T., Pointcheval, D., Stern, J.: RSA-OAEP is secure under the RSA assumption. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 260–274. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_16

    Chapter  Google Scholar 

  13. Hofheinz, D., Hövelmanns, K., Kiltz, E.: A modular analysis of the Fujisaki-Okamoto transformation. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part I. LNCS, vol. 10677, pp. 341–371. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_12

    Chapter  MATH  Google Scholar 

  14. Jiang, H., Zhang, Z., Chen, L., Wang, H., Ma, Z.: IND-CCA-Secure key encapsulation mechanism in the quantum random oracle model, revisited. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part III. LNCS, vol. 10993, pp. 96–125. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_4

    Chapter  Google Scholar 

  15. Jiang, H., Zhang, Z., Ma, Z.: On the non-tightness of measurement-based reductions for key encapsulation mechanism in the quantum random oracle model. IACR Cryptology ePrint Archive 2019/494 (2019). https://eprint.iacr.org/2019/494

  16. McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Deep Space Netw. Prog. Rep. 44, 114–116 (1978)

    Google Scholar 

  17. Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Probl. Control Inf. Theory 15, 159–166 (1986)

    MathSciNet  MATH  Google Scholar 

  18. NIST. FIPS PUB 202 Federal Information Processing Standards Publication: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, August 2015

    Google Scholar 

  19. NIST. Post-Quantum Cryptography Standardization: Second Round Submissions, January 2019. https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

  20. Saito, T., Xagawa, K., Yamakawa, T.: Tightly-secure key-encapsulation mechanism in the quantum random oracle model. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 520–551. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_17

    Chapter  MATH  Google Scholar 

  21. Song, F., Yun, A.: Quantum security of NMAC and related constructions. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part II. LNCS, vol. 10402, pp. 283–309. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_10

    Chapter  Google Scholar 

  22. Targhi, E.E., Unruh, D.: Post-quantum security of the Fujisaki-Okamoto and OAEP transforms. In: Hirt, M., Smith, A. (eds.) TCC 2016, Part II. LNCS, vol. 9986, pp. 192–216. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53644-5_8

    Chapter  MATH  Google Scholar 

  23. Unruh, D.: Revocable quantum timed-release encryption. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 129–146. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_8

    Chapter  Google Scholar 

  24. Zhandry, M.: Secure identity-based encryption in the quantum random oracle model. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 758–775. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_44

    Chapter  MATH  Google Scholar 

Download references

Acknowledgments

It is my pleasure to thank Kenny Paterson, and the rest of the NTS-KEM team, for helpful discussions. I would also like to thank the anonymous reviewers of CBCrypto 2020 for their comments.

Author information

Authors and Affiliations

  1. Department of Computer Science, ETH Zurich, Zurich, Switzerland

    Varun Maram

Authors
  1. Varun Maram
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Varun Maram .

Editor information

Editors and Affiliations

  1. Department of Information Engineering, Marche Polytechnic University, Ancona, Italy

    Marco Baldi

  2. Department of Mathematical Sciences, Florida Atlantic University, Boca Raton, FL, USA

    Edoardo Persichetti

  3. Department of Information Engineering, Marche Polytechnic University, Ancona, Italy

    Paolo Santini

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Maram, V. (2020). On the Security of NTS-KEM in the Quantum Random Oracle Model. In: Baldi, M., Persichetti, E., Santini, P. (eds) Code-Based Cryptography. CBCrypto 2020. Lecture Notes in Computer Science(), vol 12087. Springer, Cham. https://doi.org/10.1007/978-3-030-54074-6_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-54074-6_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-54073-9

  • Online ISBN: 978-3-030-54074-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation