nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Quantum Indistinguishability for Public Key Encryption

verfasst von : Tommaso Gagliardoni, Juliane Krämer, Patrick Struck

Erschienen in: Post-Quantum Cryptography

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

In this work we study the quantum security of public key encryption schemes (PKE). Boneh and Zhandry (CRYPTO’13) initiated this research area for PKE and symmetric key encryption (SKE), albeit restricted to a classical indistinguishability phase. Gagliardoni et al. (CRYPTO’16) advanced the study of quantum security by giving, for SKE, the first definition with a quantum indistinguishability phase. For PKE, on the other hand, no notion of quantum security with a quantum indistinguishability phase exists.

Our main result is a novel quantum security notion (

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-81293-5_24/MediaObjects/513547_1_En_24_Figa_HTML.gif

for PKE with a quantum indistinguishability phase, which closes the aforementioned gap. We show a distinguishing attack against code-based schemes and against LWE-based schemes with certain parameters. We also show that the canonical hybrid PKE-SKE encryption construction is

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-81293-5_24/MediaObjects/513547_1_En_24_Figb_HTML.gif

-secure, even if the underlying PKE scheme by itself is not. Finally, we classify quantum-resistant PKE schemes based on the applicability of our security notion.

Our core idea follows the approach of Gagliardoni et al. by using so-called type-2 operators for encrypting the challenge message. At first glance, type-2 operators appear unnatural for PKE, as the canonical way of building them requires both the secret and the public key. However, we identify a class of PKE schemes - which we call recoverable - and show that for this class type-2 operators require merely the public key. Moreover, recoverable schemes allow to realise type-2 operators even if they suffer from decryption failures, which in general thwarts the reversibility mandated by type-2 operators. Our work reveals that many real-world quantum-resistant PKE schemes, including most NIST PQC candidates and the canonical hybrid construction, are indeed recoverable.

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 An Algebraic Approach to the Rank Support Learning Problem

Nächstes Kapitel A Practical Adaptive Key Recovery Attack on the LGM (GSW-like) Cryptosystem

See [19, Appendix C] for concurrent and independent work.

This is implicitly considered in [12] and [18], but not explicitly formalised.

We denote by

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-81293-5_24/MediaObjects/513547_1_En_24_Figaa_HTML.gif

a Hilbert space such that

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-81293-5_24/MediaObjects/513547_1_En_24_Figab_HTML.gif

is isomorphic to \(\mathfrak H _{\mathcal {C}} \). Notice that the opposite case, i.e.,

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-81293-5_24/MediaObjects/513547_1_En_24_Figac_HTML.gif

, cannot happen because it would lead to collisions on the ciphertexts and thus introduce decryption failures. Also notice that, as in [18], the case of adversarially-controlled ancilla qubits is left as an open problem.

Even if considering challengers that use superpositions of randomnesses, we show in the full version [19] that the difference is irrelevant, and that we can always restrict ourselves to the case of a classical randomness register.

As we will see, these cover all the interesting cases in practice, although there might be other classes of schemes which allow an efficient construction of

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-81293-5_24/MediaObjects/513547_1_En_24_Figbh_HTML.gif

; we address the general case in the full version [19].

For example, one could combine a suitable separating SKE scheme with the canonical hybrid construction (cf. Sect. 4.2), so that the separation property is ‘inherited’ by the resulting PKE scheme. We are not aware of an explicit example of such SKE scheme and we leave this as an open problem. We stress that such a counterexample is not found in [13], as the authors there “excluded [...] notations that [...] combine quantum learning queries with quantum challenge queries of different query models.”.

Aguilar Melchor, C., et al.: HQC. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

Aguilar Melchor, C., et al.: RQC. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

Alagic, G., Gagliardoni, T., Majenz, C.: Can you sign a quantum state. IACR Cryptology ePrint Archive, 2018:1164 (2018)

Alagic, G., Gagliardoni, T., Majenz, C.: Unforgeable quantum encryption. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 489–519. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_16CrossRef

Alagic, G., Majenz, C., Russell, A., Song, F.: Quantum-access-secure message authentication via blind-unforgeability. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part III. LNCS, vol. 12107, pp. 788–817. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_27CrossRef

Alagic, G., Russell, A.: Quantum-secure symmetric-key cryptography based on hidden shifts. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part III. LNCS, vol. 10212, pp. 65–93. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_3CrossRef

Anand, M.V., Targhi, E.E., Tabia, G.N., Unruh, D.: Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 44–63. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29360-8_4CrossRefMATH

Aragon, N., et al.: ROLLO. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

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

10.

Bernstein, D.J., Buchmann, J., Dahmen, E.: Post-quantum cryptography (2009)

11.

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_3CrossRefMATH

12.

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_21CrossRefMATH

13.

Carstens, T.V., Ebrahimi, E., Tabia, G., Unruh, D.: On quantum indistinguishability under chosen plaintext attack. Cryptology ePrint Archive, Report 2020/596 (2020). https://eprint.iacr.org/2020/596

14.

Chevalier, C., Ebrahimi, E., Vu, Q.-H.: On the security notions for encryption in a quantum world. IACR Cryptology ePrint Archive, 2020/237 (2020)

15.

Couvreur, A., et al.: BIG QUAKE. Technical report, National Institute of Standards and Technology (2017). https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions

16.

Damgård, I., Funder, J., Nielsen, J.B., Salvail, L.: Superposition attacks on cryptographic protocols. In: Padró, C. (ed.) ICITS 2013. LNCS, vol. 8317, pp. 142–161. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-04268-8_9CrossRef

17.

Gagliardoni, T.: Quantum security of cryptographic primitives. Ph.D. thesis, Darmstadt University of Technology, Germany (2017)

18.

Gagliardoni, T., Hülsing, A., Schaffner, C.: Semantic security and indistinguishability in the quantum world. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part III. LNCS, vol. 9816, pp. 60–89. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_3CrossRefMATH

19.

Gagliardoni, T., Krämer, J., Struck, P.: Quantum indistinguishability for public key encryption. Cryptology ePrint Archive, Report 2020/266 (2020). https://eprint.iacr.org/2020/266

20.

Grover, L.K.: A fast quantum mechanical algorithm for database search. In: 28th ACM STOC, pp. 212–219. ACM Press, May 1996

21.

Ito, G., Hosoyamada, A., Matsumoto, R., Sasaki, Yu., Iwata, T.: Quantum chosen-ciphertext attacks against feistel ciphers. In: Matsui, M. (ed.) CT-RSA 2019. LNCS, vol. 11405, pp. 391–411. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12612-4_20CrossRef

22.

Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part II. LNCS, vol. 9815, pp. 207–237. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_8CrossRef

23.

Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Quantum differential and linear cryptanalysis. IACR Trans. Symm. Cryptol. 2016(1), 71–94 (2016). http://tosc.iacr.org/index.php/ToSC/article/view/536)

24.

Kashefi, E., Kent, A., Vedral, V., Banaszek, K.: Comparison of quantum oracles. Phys. Rev. A 65(5), 050304 (2002)CrossRef

25.

Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round feistel cipher and the random permutation. In: Proceedings of IEEE International Symposium on Information Theory, ISIT 2010, Austin, Texas, USA, 13–18 June 2010, pp. 2682–2685 (2010)

26.

Kuwakado, H., Morii, M.: Security on the quantum-type even-mansour cipher. In: Proceedings of the International Symposium on Information Theory and its Applications, ISITA 2012, Honolulu, HI, USA, 28–31 October 2012, pp. 312–316 (2012)

27.

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition, 10th edn. Cambridge University Press, New York (2011)

28.

National Institute of Standards and Technology. Post-quantum cryptography standardization process (2017)

29.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press, May 2005

30.

Rötteler, M., Steinwandt, R.: A note on quantum related-key attacks. Inf. Process. Lett. 115(1), 40–44 (2015)CrossRef

31.

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th FOCS, pp. 124–134. IEEE Computer Society Press, November 1994

32.

Shoup, V.: Sequences of games: a tool for taming complexity in security proofs. Cryptology ePrint Archive, Report 2004/332 (2004). http://eprint.iacr.org/2004/332

33.

Watrous, J.: Zero-knowledge against quantum attacks. SIAM J. Comput. 39(1), 25–58 (2009)MathSciNetCrossRef

34.

Zhandry, M.: How to construct quantum random functions. In: 53rd FOCS, pp. 679–687. IEEE Computer Society Press, October 2012

Titel: Quantum Indistinguishability for Public Key Encryption
verfasst von: Tommaso Gagliardoni
Juliane Krämer
Patrick Struck
Verlag: Springer International Publishing
Buch: Post-Quantum Cryptography
Print ISBN: 978-3-030-81292-8

Electronic ISBN: 978-3-030-81293-5

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-81293-5_24

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"