nach oben

Erschienen in:

2025 | OriginalPaper | Buchkapitel

Robust Combiners and Universal Constructions for Quantum Cryptography

verfasst von : Taiga Hiroka, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa

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

A robust combiner combines many candidates for a cryptographic primitive and generates a new candidate for the same primitive. Its correctness and security hold as long as one of the original candidates satisfies correctness and security. A universal construction is a closely related notion to a robust combiner. A universal construction for a primitive is an explicit construction of the primitive that is correct and secure as long as the primitive exists. It is known that a universal construction for a primitive can be constructed from a robust combiner for the primitive in many cases.

Although robust combiners and universal constructions for classical cryptography are widely studied, robust combiners and universal constructions for quantum cryptography have not been explored so far. In this work, we define robust combiners and universal constructions for several quantum cryptographic primitives including one-way state generators, public-key quantum money, quantum bit commitments, and unclonable encryption, and provide constructions of them.

On a different note, it was an open problem how to expand the plaintext length of unclonable encryption. In one of our universal constructions for unclonable encryption, we can expand the plaintext length, which resolves the open problem.

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 Cryptography in the Common Haar State Model: Feasibility Results and Separations

Nächstes Kapitel Unbounded Leakage-Resilience and Intrusion-Detection in a Quantum World

As discussed in the previous works [AQY22, BCQ23], it is a folklore that a random quantum circuit is PRSGs although there exists no theoretical evidence so far. Since we can construct OWSGs from PRSGs [MY22b, MY22a], we can also construct OWSGs based on random quantum circuits if a random quantum circuit is PRSGs.

It is a folklore that a random quantum circuit is PRSGs although there exists no theoretical evidence so far. Since we can construct quantum bit commitments from PRSGs [MY22b, AQY22], we can also construct quantum bit commitments based on random quantum circuits if a random quantum circuit is PRSGs.

The technique we introduce here cannot be applied to public-key quantum money. For public-key quantum money, we apply the technique introduced by [HKN+05] in order to transform an incorrect candidate into a correct one. The idea of transformation is first checking the correctness of a public-key quantum money candidate \(\varSigma =(\textsf{Mint},\textsf{Vrfy})\). If the candidate \(\varSigma \) satisfies the correctness, then we amplify the correctness by parallel repetition. Otherwise, we use the scheme \(\varSigma ^*=(\textsf{Mint}^*,\textsf{Vrfy}^*)\), where \(\textsf{Vrfy}^*\) algorithm always outputs \(\top \). For details, please see the full version.

[AK21] shows that unclonable PKE can be constructed from one-time unclonable SKE and PKE with classical ciphertexts. Note that it is unclear whether we can construct unclonable PKE from one-time SKE and PKE with “quantum” ciphertexts in the same way as [AK21]. This is because they use the existence of OWFs in their proof although it is unclear whether PKE with quantum ciphertexts implies OWFs. Therefore, we use the technique of [HMNY21] instead. (For the detail, please see the full version).

[Aar18]

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

[ABJ+19]

Ananth, P., Badrinarayanan, S., Jain, A., Manohar, N., Sahai, A.: From FE combiners to secure MPC and back. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019. Part I, volume 11891 of LNCS, pp. 199–228. Springer, Heidelberg (2019)

[AC12]

Aaronson, S., Christiano, P.: Quantum money from hidden subspaces. In: STOC, pp. 41–60. ACM (2012)

[AGQY22]

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, pp. 237–265. Springer, Cham (2022)

[AJN+16]

Ananth, P., Jain, A., Naor, M., Sahai, A., Yogev, E.: Universal constructions and robust combiners for indistinguishability obfuscation and witness encryption. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, Part II, vol. 9815, pp. 491–520. Springer, Heidelberg (2016)

[AJS17]

Ananth, P., Jain, A., Sahai, A.: Robust transforming combiners from indistinguishability obfuscation to functional encryption. In: EUROCRYPT (1), pp. 91–121. Springer (2017)

[AK21]

Ananth, P., Kaleoglu, F.: Unclonable encryption, revisited. In: Nissim, K., Waters, B. (eds.) Theory of Cryptography, pp. 299–329. Springer, Cham (2021)

[AKL+22]

Ananth, P., Kaleoglu, F., Li, X., Liu, Q., Zhandry, M.: On the feasibility of unclonable encryption, and more. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology – CRYPTO 2022, pp. 212–241. Springer, Cham (2022)

[AQY22]

Ananth, P., Qian, L., Yuen, H.: Cryptography from pseudorandom quantum states. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology – CRYPTO 2022, pp. 208–236. Springer, Cham (2022)

[BB84]

Bennett, C.H., Brassard, G.: Quantum cryptography: public key distribution and coin tossing. In: Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, p. 175 (1984)

[BCKM21]

Bartusek, J., Coladangelo, A., Khurana, D., Ma, F.: On the round complexity of secure quantum computation. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, Part I, vol. 12825, pp. 406–435. Springer, Heidelberg (2021)

[BCQ23]

Brakerski, Z., Canetti, R., Qian, L.: On the computational hardness needed for quantum cryptography. In: Kalai, Y.T. (ed.) 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, 10–13 January 2023, MIT, Cambridge. LIPIcs, vol. 251, pp. 24:1–24:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

[BL20]

Broadbent, A., Lord, S.: Uncloneable quantum encryption via oracles. In: Flammia, S.T. (ed.) 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2020, 9–12 June 2020, Riga. LIPIcs, vol. 158, pp. 4:1–4:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

[BY22]

Brakerski, Z., Yuen, H.: Quantum garbled circuits. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pp. 804–817. Association for Computing Machinery, New York (2022)

[CHK05]

Canetti, R., Halevi, S., Katz, J.: Adaptively-secure, non-interactive public-key encryption. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 150–168. Springer, Heidelberg (2005)

[CLS01]

Crépeau, C., Légaré, F., Salvail, L.: How to convert the flavor of a quantum bit commitment. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 60–77. Springer, Heidelberg (2001)CrossRef

[CX22]

Cao, S., Xue, R.: On constructing one-way quantum state generators, and more. Cryptology ePrint Archive, Paper 2022/1323 (2022). https://eprint.iacr.org/2022/1323

[DH76]

Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (1976)MathSciNetCrossRef

[DMS00]

Dumais, P., Mayers, D., Salvail, L.: Perfectly concealing quantum bit commitment from any quantum one-way permutation. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 300–315. Springer, Heidelberg (2000)CrossRef

[ElG85]

ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31, 469–472 (1985)MathSciNetCrossRef

[FGH+12]

Farhi, E., Gosset, D., Hassidim, A., Lutomirski, A., Shor, P.W.: Quantum money from knots. In: Goldwasser, S. (ed.) ITCS 2012, pp. 276–289. ACM (2012)

[GLSV21]

Grilo, A.B., Lin, H., Song, F., Vaikuntanathan, V.: Oblivious transfer is in MiniQCrypt. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, Part II, vol. 12697, pp. 531–561. Springer, Heidelberg (2021)

[GTK16]

Goldwasser, S., Tauman Kalai, Y.: Cryptographic assumptions: a position paper. In: Kushilevitz, E., Malkin, T. (eds.) Theory of Cryptography, pp. 505–522. Springer, Heidelberg (2016)

[Her05]

Herzberg, A.: On tolerant cryptographic constructions. In: Menezes, A. (ed.) Topics in Cryptology – CT-RSA 2005, pp. 172–190. Springer, Heidelberg (2005)

[HKN+05]

Harnik, D., Kilian, J., Naor, M., Reingold, O., Rosen, A.: On robust combiners for oblivious transfer and other primitives. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 96–113. Springer, Heidelberg (2005)CrossRef

[HMNY21]

Hiroka, T., Morimae, T., Nishimaki, R., Yamakawa, T.: Quantum encryption with certified deletion, revisited: public key, attribute-based, and classical communication. In: Tibouchi, M., Wang, H. (eds.) Advances in Cryptology – ASIACRYPT 2021, pp. 606–636. Springer, Cham (2021)

[HMY23]

Hhan, M., Morimae, T., Yamakawa, T.: From the hardness of detecting superpositions to cryptography: quantum public key encryption and commitments. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology – EUROCRYPT 2023, pp. 639–667. Springer, Cham (2023)

[JLS18]

Ji, Z., Liu, Y.-K., Song, F.: Pseudorandom quantum states. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, Part III, vol. 10993, pp. 126–152. Springer, Heidelberg (2018)

[JMS20]

Jain, A., Manohar, N., Sahai, A.: Combiners for functional encryption, unconditionally. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, Part I, vol. 12105, pp. 141–168. Springer, Heidelberg (2020)

[Kan18]

Kane, D.M.: Quantum money from modular forms. arXiv preprint arXiv:1809.05925 (2018)

[KNTY19]

Kitagawa, F., Nishimaki, R., Tanaka, K., Yamakawa, T.: Adaptively secure and succinct functional encryption: improving security and efficiency, simultaneously. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, Part III, vol. 11694, pp. 521–551. Springer, Heidelberg (2019)

[KQST23]

Kretschmer, W., Qian, L., Sinha, M., Tal, A.: Quantum cryptography in algorithmica. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pp. 1589–1602. Association for Computing Machinery, New York (2023)

[Kre21]

Kretschmer, W.: Quantum pseudorandomness and classical complexity. In: Hsieh, M.-H. (ed.) 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 197, pp. 2:1–2:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl (2021)

[KSS22]

Kane, D.M., Sharif, S., Silverberg, A.: Quantum money from quaternion algebras (2022)

[KT23]

Khurana, D., Tomer, K.: Commitments from quantum one-wayness (2023)

[LC97]

Lo, H.-K., Chau, H.F.: Is quantum bit commitment really possible? Phys. Rev. Lett. 78, 3410–3413 (1997)

[Lev85]

Levin, L.A.: One-way functions and pseudorandom generators. In: 17th ACM STOC, pp. 363–365. ACM Press (1985)

[LMZ23]

Liu, J., Montgomery, H., Zhandry, M.: Another round of breaking and making quantum money: In: Hazay, C., Stam, M. (eds.) Advances in Cryptology – EUROCRYPT 2023, pp. 611–638. Springer, , Cham (2023)

[May97]

Mayers, D.: Unconditionally secure quantum bit commitment is impossible. Phys. Rev. Lett. 78, 3414–3417 (1997)CrossRef

[MY22a]

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

[MY22b]

Morimae, T., Yamakawa, T.: Quantum commitments and signatures without one-way functions. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology – CRYPTO 2022, pp. 269–295. Springer, Cham (2022)

[Reg05]

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 (2005)

[WW23]

Waters, B., Wichs, D.: Universal amplification of KDM security: from 1-key circular to multi-key KDM. Cryptology ePrint Archive, Paper 2023/1058 (2023). https://eprint.iacr.org/2023/1058

[Yan22]

Yan, J.: General properties of quantum bit commitments (extended abstract). In: Agrawal, S., Lin, D. (eds.) Advances in Cryptology – ASIACRYPT 2022, pp. 628–657. Springer, Cham (2022)

[Zha19]

Zhandry, M.: Quantum lightning never strikes the same state twice. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. Part III, volume 11478 of LNCS, pp. 408–438. Springer, Heidelberg (2019)

[Zha23a]

Zhandry, M.: Quantum minimalism (talk) (2023). https://www.youtube.com/watch?v=7cqnrASfjco&ab_channel=SimonsInstitute

[Zha23b]

Zhandry, M.: Quantum money from abelian group actions. IACR Cryptol. ePrint Arch. 2023, 1097 (2023)

Titel: Robust Combiners and Universal Constructions for Quantum Cryptography
verfasst von: Taiga Hiroka
Fuyuki Kitagawa
Ryo Nishimaki
Takashi Yamakawa
Verlag: Springer Nature Switzerland
Buch: Theory of Cryptography
Print ISBN: 978-3-031-78016-5

Electronic ISBN: 978-3-031-78017-2

Copyright-Jahr: 2025
DOI: https://doi.org/10.1007/978-3-031-78017-2_5

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"