nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

Public-Key Encryption with Quantum Keys

verfasst von : Khashayar Barooti, Alex B. Grilo, Loïs Huguenin-Dumittan, Giulio Malavolta, Or Sattath, Quoc-Huy Vu, Michael Walter

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In the framework of Impagliazzo’s five worlds, a distinction is often made between two worlds, one where public-key encryption exists (Cryptomania), and one in which only one-way functions exist (MiniCrypt). However, the boundaries between these worlds can change when quantum information is taken into account. Recent work has shown that quantum variants of oblivious transfer and multi-party computation, both primitives that are classically in Cryptomania, can be constructed from one-way functions, placing them in the realm of quantum MiniCrypt (the so-called MiniQCrypt). This naturally raises the following question: Is it possible to construct a quantum variant of public-key encryption, which is at the heart of Cryptomania, from one-way functions or potentially weaker assumptions?

In this work, we initiate the formal study of the notion of quantum public-key encryption (qPKE), i.e., public-key encryption where keys are allowed to be quantum states. We propose new definitions of security and several constructions of qPKE based on the existence of one-way functions (OWF), or even weaker assumptions, such as pseudorandom function-like states (PRFS) and pseudorandom function-like states with proof of destruction (PRFSPD). Finally, to give a tight characterization of this primitive, we show that computational assumptions are necessary to build quantum public-key encryption. That is, we give a self-contained proof that no quantum public-key encryption scheme can provide information-theoretic security.

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 Weakening Assumptions for Publicly-Verifiable Deletion

Nächstes Kapitel Publicly Verifiable Deletion from Minimal Assumptions

Throughout this paper, unless explicitly specified, by IND-CCA we refer to the notion of adaptive IND-CCA2 security.

Note that PRS implies PRFS with logarithmic size inputs, but no such implication is known for super-logarithmic inputs.

Meaning that one can only encrypt once using a

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-031-48624-1_8/MediaObjects/557553_1_En_8_Figo_HTML.gif

Because of this stronger security definition, here the notion of public-keys with mixed states is meaningful since there is an alternative procedure to ensure that the key is well-formed (e.g., signing the classical component).

This observation was pointed out to us by Takashi Yamakawa.

This is due to \(\varPi ^1_\textsf{dk} \) operators being rank-1 projections.

Aaronson, S.: Shadow tomography of quantum states. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) 50th ACM STOC, pp. 325–338. ACM Press (2018). https://doi.org/10.1145/3188745.3188802

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

Ananth, P., Gulati, A., Qian, L., Yuen, H.: Pseudorandom (function-like) quantum state generators: New definitions and applications. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC 2022, Part I. LNCS, vol. 13747, pp. 237–265. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-22318-1_9

Ananth, P., Qian, L., Yuen, H.: Cryptography from pseudorandom quantum states. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part I. LNCS, vol. 13507, pp. 208–236. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-15802-5_8

Austrin, P., Chung, H., Chung, K.M., Fu, S., Lin, Y.T., Mahmoody, M.: On the impossibility of key agreements from quantum random oracles. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part II. LNCS, vol. 13508, pp. 165–194. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-15979-4_6

Barhoush, M., Salvail, L.: How to sign quantum messages. arXiv preprint arXiv:2304.06325 (2023)

Barooti, K., et al.: Public-key encryption with quantum keys. Cryptology ePrint Archive, Paper 2023/877 (2023). https://eprint.iacr.org/2023/877

Barooti, K., Malavolta, G., Walter, M.: A simple construction of quantum public-key encryption from quantum-secure one-way functions. Cryptology ePrint Archive, Paper 2023/306 (2023). https://eprint.iacr.org/2023/306

Bartusek, J., Coladangelo, A., Khurana, D., Ma, F.: One-way functions imply secure computation in a quantum world. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12825, pp. 467–496. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_17CrossRefMATH

10.

Behera, A., Brakerski, Z., Sattath, O., Shmueli, O.: Pseudorandomness with proof of destruction and applications. Cryptology ePrint Archive, Paper 2023/543 (2023). https://eprint.iacr.org/2023/543

11.

Bennett, C.H., Brassard, G.: An update on quantum cryptography (impromptu talk). In: Blakley, G.R., Chaum, D. (eds.) CRYPTO’84. LNCS, vol. 196, pp. 475–480. Springer, Heidelberg (1984)

12.

Boneh, D., Zhandry, M.: Quantum-secure message authentication codes. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 592–608. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_35CrossRef

13.

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

14.

Chevalier, C., Ebrahimi, E., Vu, Q.H.: On security notions for encryption in a quantum world. In: Isobe, T., Sarkar, S. (eds.) Progress in Cryptology - INDOCRYPT 2022–23rd International Conference on Cryptology in India, Kolkata, India, 11–14 December 2022, Proceedings. Lecture Notes in Computer Science, vol. 13774, pp. 592–613. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-22912-1_26

15.

Choi, S.G., Dachman-Soled, D., Malkin, T., Wee, H.: A black-box construction of non-malleable encryption from semantically secure encryption. J. Cryptol. 31(1), 172–201 (2018). https://doi.org/10.1007/s00145-017-9254-zMathSciNetCrossRefMATH

16.

Coladangelo, A.: Quantum trapdoor functions from classical one-way functions. Cryptology ePrint Archive, Paper 2023/282 (2023). https://eprint.iacr.org/2023/282

17.

Doliskani, J.: Efficient quantum public-key encryption from learning with errors. Cryptology ePrint Archive, Paper 2020/1557 (2020). https://eprint.iacr.org/2020/1557

18.

Gottesman, D.: Quantum public key cryptography with information-theoretic security (2005). https://www2.perimeterinstitute.ca/personal/dgottesman/Public-key.ppt

19.

Grilo, A.B., Lin, H., Song, F., Vaikuntanathan, V.: Oblivious transfer is in MiniQCrypt. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 531–561. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_18CrossRefMATH

20.

Grilo, A.B., Sattath, O., Vu, Q.H.: Encryption with quantum public keys. Cryptology ePrint Archive, Paper 2023/345 (2023). https://eprint.iacr.org/2023/345

21.

Huang, H.Y., Kueng, R., Preskill, J.: Predicting many properties of a quantum system from very few measurements. Nat. Phys. 16(10), 1050–1057 (2020)CrossRef

22.

Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 8–26. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_2CrossRef

23.

Ji, Z., Liu, Y.-K., Song, F.: Pseudorandom quantum states. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 126–152. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_5CrossRef

24.

Kawachi, A., Koshiba, T., Nishimura, H., Yamakami, T.: Computational indistinguishability between quantum states and its cryptographic application. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 268–284. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_16CrossRef

25.

Kitagawa, F., Morimae, T., Nishimaki, R., Yamakawa, T.: Quantum public-key encryption with tamper-resilient public keys from one-way functions. Cryptology ePrint Archive, Paper 2023/490 (2023). https://eprint.iacr.org/2023/490

26.

Kretschmer, W.: Quantum pseudorandomness and classical complexity. In: Hsieh, M. (ed.) 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2021, 5–8 July 2021, Virtual Conference. LIPIcs, vol. 197, pp. 2:1–2:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPIcs.TQC.2021.2

27.

Kretschmer, W., Qian, L., Sinha, M., Tal, A.: Quantum cryptography in algorithmica. arXiv preprint arXiv:2212.00879 (2022)

28.

Malavolta, G., Walter, M.: Non-interactive quantum key distribution. Cryptology ePrint Archive, Paper 2023/500 (2023). https://eprint.iacr.org/2023/500

29.

Morimae, T., Yamakawa, T.: One-wayness in quantum cryptography. Cryptology ePrint Archive, Paper 2022/1336 (2022). https://eprint.iacr.org/2022/1336

30.

Morimae, T., Yamakawa, T.: Quantum commitments and signatures without one-way functions. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part I. LNCS, vol. 13507, pp. 269–295. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-15802-5_10

31.

Myers, S., Shelat, A.: Bit encryption is complete. In: 50th FOCS, pp. 607–616. IEEE Computer Society Press (2009). https://doi.org/10.1109/FOCS.2009.65

32.

Nikolopoulos, G.M., Ioannou, L.M.: Deterministic quantum-public-key encryption: forward search attack and randomization. Phys. Rev. A 79, 042327 (2009). https://doi.org/10.1103/PhysRevA.79.042327

33.

Okamoto, T., Tanaka, K., Uchiyama, S.: Quantum public-key cryptosystems. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 147–165. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44598-6_9CrossRef

34.

Wiesner, S.: Conjugate coding. SIGACT News 15(1), 78–88 (1983). https://doi.org/10.1145/1008908.1008920CrossRefMATH

35.

Zhandry, M.: How to construct quantum random functions. In: 53rd FOCS, pp. 679–687. IEEE Computer Society Press (2012). https://doi.org/10.1109/FOCS.2012.37

Titel: Public-Key Encryption with Quantum Keys
verfasst von: Khashayar Barooti
Alex B. Grilo
Loïs Huguenin-Dumittan
Giulio Malavolta
Or Sattath
Quoc-Huy Vu
Michael Walter
Verlag: Springer Nature Switzerland
Buch: Theory of Cryptography
Print ISBN: 978-3-031-48623-4

Electronic ISBN: 978-3-031-48624-1

Copyright-Jahr: 2023
DOI: https://doi.org/10.1007/978-3-031-48624-1_8

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"

Premium Partner