Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Topic Page
Marketing
Events
Start single access now
Access for companies
12th International Engine Congress 2025 | 25. + 26. February 2025

Meeting Place for the Powertrain and Sustainable Fuels Community

The congress will examine the future role of the internal combustion engine and its non-fossil fuels from a global perspective with leading experts. Be part of it! More information and booking options are available on our website.
EXTENDED SEARCH
Log in
Top
Published in:
Read chapter Read first chapter

2025 | OriginalPaper | Chapter

Robust Combiners and Universal Constructions for Quantum Cryptography

Authors : Taiga Hiroka, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa

Published in: Theory of Cryptography

Publisher: Springer Nature Switzerland

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Cryptography in the Common Haar State Model: Feasibility Results and Separations
next chapter Unbounded Leakage-Resilience and Intrusion-Detection in a Quantum World
Footnotes
1
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.
 
2
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.
 
3
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.
 
4
[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).
 
Literature
[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]
[DH76]
[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]
[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]
[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]
[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]
[Zha23b]
Zhandry, M.: Quantum money from abelian group actions. IACR Cryptol. ePrint Arch. 2023, 1097 (2023)
Metadata
Title
Robust Combiners and Universal Constructions for Quantum Cryptography
Authors
Taiga Hiroka
Fuyuki Kitagawa
Ryo Nishimaki
Takashi Yamakawa
Copyright Year
2025
Book
Theory of Cryptography

Print ISBN: 978-3-031-78016-5

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

Copyright Year: 2025

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

Premium Partner

    Image Credits