nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Separate Your Domains: NIST PQC KEMs, Oracle Cloning and Read-Only Indifferentiability

verfasst von : Mihir Bellare, Hannah Davis, Felix Günther

Erschienen in: Advances in Cryptology – EUROCRYPT 2020

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

It is convenient and common for schemes in the random oracle model to assume access to multiple random oracles (ROs), leaving to implementations the task—we call it oracle cloning—of constructing them from a single RO. The first part of the paper is a case study of oracle cloning in KEM submissions to the NIST Post-Quantum Cryptography standardization process. We give key-recovery attacks on some submissions arising from mistakes in oracle cloning, and find other submissions using oracle cloning methods whose validity is unclear. Motivated by this, the second part of the paper gives a theoretical treatment of oracle cloning. We give a definition of what is an “oracle cloning method” and what it means for such a method to “work,” in a framework we call read-only indifferentiability, a simple variant of classical indifferentiability that yields security not only for usage in single-stage games but also in multi-stage ones. We formalize domain separation, and specify and study many oracle cloning methods, including common domain-separating ones, giving some general results to justify (prove read-only indifferentiability of) certain classes of methods. We are not only able to validate the oracle cloning methods used in many of the unbroken NIST PQC KEMs, but also able to specify and validate oracle cloning methods that may be useful beyond that.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Correction to: Optimal Merging in Quantum k-xor and k-sum Algorithms

Nächstes Kapitel On the Memory-Tightness of Hashed ElGamal

Albrecht, M., Cid, C., Paterson, K.G., Tjhai, C.J., Tomlinson, M.: NTS-KEM. NIST PQC Round 2 Submission (2019)

Alkim, E., et al.: NewHope: algorithm specifications and supporting documentation. NIST PQC Round 2 Submission (2019)

Aragon, N., et al.: BIKE: bit flipping key encapsulation. NIST PQC Round 2 Submission (2019)

Aragon, N., et al.: LOCKER: low rank parity check codes encryption. NIST PQC Round 1 Submission (2017)

Avanzi, R., et al.: CRYSTALS-Kyber: algorithm specifications and supporting documentation. NIST PQC Round 2 Submission (2019)

Baan, H., et al.: Round5: KEM and PKE based on (ring) learning with rounding. NIST PQC Round 2 Submission (2019)

Banegas, G., et al.: DAGS: key encapsulation from dyadic GS codes. NIST PQC Round 1 Submission (2017)

Bardet, M., et al.: BIG QUAKE: binary goppa quasi-cyclic key encapsulation. NIST PQC Round 1 Submission (2017)

Bellare, M., Bernstein, D.J., Tessaro, S.: Hash-function based PRFs: AMAC and its multi-user security. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part I. LNCS, vol. 9665, pp. 566–595. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_22CrossRef

10.

Bellare, M., Davis, H., Günther, F.: Separate your domains: NIST PQC KEMs, oracle cloning and read-only indifferentiability. Cryptology ePrint Archive (2020)

11.

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 1993, pp. 62–73. ACM Press, November 1993

12.

Bellare, M., Rogaway, P.: The security of triple encryption and a framework for code-based game-playing proofs. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 409–426. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_25CrossRef

13.

Bernstein, D.J., et al.: Classic McEliece: conservative code-based cryptography. NIST PQC Round 2 Submission (2019)

14.

Bernstein, D.J., Chuengsatiansup, C., Lange, T., van Vredendaal, C.: NTRU Prime. NIST PQC Round 2 Submission (2019)

15.

Chen, M.-S., Hülsing, A., Rijneveld, J., Samardjiska, S., Schwabe, P.: MQDSS specifications. NIST PQC Round 2 Submission (2019)

16.

Cheon, J.H., et al.: Lizard public key encryption. NIST PQC Round 1 Submission (2017)

17.

Coron, J.-S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damgård revisited: how to construct a hash function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430–448. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_26CrossRef

18.

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)MathSciNetCrossRef

19.

D’Anvers, J.-P., Karmakar, A., Roy, S.S., Vercauteren, F.: SABER: Mod-LWR based KEM. NIST PQC Round 2 Submission (2019)

20.

Demay, G., Gaži, P., Hirt, M., Maurer, U.: Resource-restricted indifferentiability. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 664–683. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_39CrossRef

21.

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_12CrossRef

22.

Garcia-Morchon, O., Zhang, Z.: Round2: KEM and PKE based on GLWR. NIST PQC Round 1 Submission (2017)

23.

Hamburg, M.: Post-quantum cryptography proposal: ThreeBears. NIST PQC Round 2 Submission (2019)

24.

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_12CrossRefMATH

25.

Hülsing, A., Rijneveld, J., Schanck, J.M., Schwabe, P.: NTRU-HRSS-KEM: algorithm specifications and supporting documentations. NIST PQC Round 1 Submission (2017)

26.

Jao, D., et al.: Supersingular isogeny key encapsulation. NIST PQC Round 2 Submission (2019)

27.

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_4CrossRef

28.

Lu, X., Liu, Y., Jia, D., Xue, H., He, J., Zhang, Z.: LAC: Lattice-based cryptosystems. NIST PQC Round 2 Submission (2019)

29.

Maurer, U., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_2CrossRef

30.

Melchor, C.A., et al.: ROLLO: rank-ouroboros, LAKE, & LOCKER. NIST PQC Round 2 Submission (2018)

31.

Melchor, C.A., et al.: Rank quasi-cyclic (RQC). NIST PQC Round 2 Submission (2019)

32.

Melchor, C.A., et al.: Hamming quasi-cyclic (HQC). NIST PQC Round 2 Submission (2019)

33.

Mittelbach, A.: Salvaging indifferentiability in a multi-stage setting. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 603–621. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_33CrossRefMATH

34.

Naehrig, M., et al.: FrodoKEM: learning with errors key encapsulation. NIST PQC Round 2 Submission (2019)

35.

NIST. Post-Quantum Cryptography Standardization Process. https://csrc.nist.gov/projects/post-quantum-cryptography

36.

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

37.

NIST. PQC Standardization Process: Second Round Candidate Announcement, January 2019. https://csrc.nist.gov/news/2019/pqc-standardization-process-2nd-round-candidates

38.

Plantard, T.: Odd Manhattan’s algorithm specifications and supporting documentation. NIST PQC Round 1 Submission (2017)

39.

Ristenpart, T., Shacham, H., Shrimpton, T.: Careful with composition: limitations of the indifferentiability framework. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 487–506. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_27CrossRef

40.

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_17CrossRefMATH

41.

Seo, M., Park, J.H., Lee, D.H., Kim, S., Lee, S.-J.: Proposal for NIST post-quantum cryptography standard: EMBLEM and R.EMBLEM. NIST PQC Round 1 Submission (2017)

42.

Smart, N.P., et al.: LIMA: a PQC encryption scheme. NIST PQC Round 1 Submission (2017)

43.

Steinfeld, R., Sakzad, A., Zhao, R.K.: Titanium: proposal for a NIST post-quantum public-key encryption and KEM standard. NIST PQC Round 1 Submission (2017)

44.

Zhao, Y., Jin, Z., Gong, B., Sui, G.: A modular and systematic approach to key establishment and public-key encryption based on LWE and its variants. NIST PQC Round 1 Submission (2017)

Titel: Separate Your Domains: NIST PQC KEMs, Oracle Cloning and Read-Only Indifferentiability
verfasst von: Mihir Bellare
Hannah Davis
Felix Günther
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2020
Print ISBN: 978-3-030-45723-5

Electronic ISBN: 978-3-030-45724-2

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-45724-2_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"