Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Kongresse
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Veranstaltungskalender Awards MyNewsletter Firmensuche
Kunden Login
Über Einzelzugang informieren
Über Unternehmenszugang informieren
Referenzkunden
12. Internationaler Motorenkongress 2025 | 25. + 26. Februar 2025

Treffpunkt der Community für Antriebe und nachhaltige Kraftstoffe

Der Kongress beleuchtet die zukünftige Rolle des Verbrennungsmotors und seiner nichtfossilen Kraftstoffe aus globaler Sicht mit führenden Experten. Seien Sie dabei! Weitere Informationen und Buchungsmöglichkeiten finden Sie auf unserer Website.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Kapitel lesen Erstes Kapitel lesen

2025 | OriginalPaper | Buchkapitel

Cryptography in the Common Haar State Model: Feasibility Results and Separations

verfasst von : Prabhanjan Ananth, Aditya Gulati, Yao-Ting Lin

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

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

search-config
loading …

Abstract

Common random string model is a popular model in classical cryptography. We study a quantum analogue of this model called the common Haar state (CHS) model. In this model, every party participating in the cryptographic system receives many copies of one or more i.i.d Haar random states.
We study feasibility and limitations of cryptographic primitives in this model and its variants:
  • We present a construction of pseudorandom function-like states with security against computationally unbounded adversaries, as long as the adversaries only receive (a priori) bounded number of copies. By suitably instantiating the CHS model, we obtain a new approach to construct pseudorandom function-like states in the plain model.
  • We present separations between pseudorandom function-like states (with super-logarithmic length) and quantum cryptographic primitives, such as interactive key agreement and bit commitment, with classical communication. To show these separations, we prove new results on the indistinguishability of identical versus independent Haar states against LOCC (local operations, classical communication) adversaries.

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 Split-State Non-malleable Codes and Secret Sharing Schemes for Quantum Messages
Nächstes Kapitel Robust Combiners and Universal Constructions for Quantum Cryptography
Fußnoten
1
We note that [Kre21] made similar use of infinitely many oracles to prove a separation between pseudorandom states and one-way functions.
 
2
We encourage readers unfamiliar with type states to refer to Definition 7.
 
3
Since \(T\in \{0,1\}^{N}\), we can treat it as a set, in particular the set associated to T is \(\{ i: T[i]=1 \}\).
 
4
Here, by dense-enough, we mean when picking a random type from \(\lambda \)-prefix collision-free, it lies in this subset with probability \(1-\textsf{negl}\).
 
5
Later, in the impossibility result, we show that this is in fact the best we can hope for as a larger subset would bypass the impossibility result.
 
6
Note that this still needs multi-key security which is not trivial in the CHS model, since all the PRS generators share the same Haar state for randomness. But we prove that our construction satisfies multikey security.
 
7
Since the Haar indistinguishability has a factor of \(O(t^2/d)\), as long as \(t^2/d\) is inverse-polynomial, we do not incur a lot of loss.
 
8
Note that since the adversary does not need to be efficient, as long as they have the description of this oracle, they can post-select on the transcript.
 
9
Note that the (partial) transpose operation needs to be defined with respect to to an orthogonal basis. Throughout this work, it is always defined with respect to to the computational basis.
 
10
More generally, the generation algorithm could take multiple copies of the common Haar state as input or output a state of different size compared to the common Haar state. Here, we focus on a restricted class of generators that only require a single copy of the common Haar state as input, and the output of the generator matches the size of the common Haar states.
 
11
We identify \([0:t]^N\) as \([0:t]^A\).
 
12
Here we allow the subsets to contain duplicate elements.
 
13
We say that this is a “classical” probabilistic process because we can write the resulting density matrix as direct sum of matrices with classical descriptions with weights chosen by a completely classical process. This means that we can simualte this process by first doing a completely classical sampling process followed by a state preparation.
 
14
Since T is collision-free, we will treat it as a set.
 
15
Since T might have collisions, \(T_1\) is allowed to contain duplicate elements.
 
16
Formally, let \(G_{PRS}\) is a \(({\lambda },n,\ell )\)-PRS and \(G(k,x,|\phi \rangle )\) is \(({\lambda },m,n,\ell )\)-statistical selectively secure PRFS generator in the CHS model with \(n>{\lambda }\), \(\ell = O({\lambda }^{1-c}/\log ({\lambda })^{1+\varepsilon })\) and \(m({\lambda }) = {\lambda }^c\), then for \(K = (k_1,k_2)\in \{0,1\}^{{\lambda }}\times \{0,1\}^{{\lambda }}\) we can define \(G_{PRFS}(k,x):= G(k_1,x,G_{PRS}(k_2))\) as the \((2{\lambda },m,n,\ell )\)-PRFS generator.
 
17
Since \((A,B)\) are allowed to communicate and we do not care about communication complexity, it is without loss of generality to assume that \(B\) outputs the bit.
 
Literatur
[ACC+22]
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: Annual International Cryptology Conference, pp. 165–194. Springer, Cham (2022)
[ACH+23]
Afshar, A., Chung, K.-M., Hsieh, Y.-C., Lin, Y.-T., Mahmoody, M.: On the (im) possibility of time- lock puzzles in the quantum random oracle model. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 339–368. Springer, Singapore (2023). (cit. on p. 6)
[AGKL23]
[AGL24]
[AGQY22]
Ananth, P., Gulati, A., Qian, L., Yuen, H.: Pseudorandom (function-like) quantum state generators: new definitions and applications. In: Theory of Cryptography Conference, pp. 237–265. Springer, Cham (2022)
[AHY23]
Ananth, P., Hu, Z., Yuen, H.: On the (im) plausibility of public-key quantum money from collision-resistant hash functions. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 39–72. Springer, Singapore (2023)
[AKY24]
Ananth, P., Kaleoglu, F., Yuen, H.: Simultaneous Haar Indistinguishability with applications to unclonable cryptography. In: arXiv preprint arXiv:​2405.​10274 (2024)
[AQY22]
Ananth, P., Qian, L., Yuen, H.: Cryptography from pseudorandom quantum states. In: CRYPTO (2022)
[BBF13]
Baecher, P., Brzuska, C., Fischlin, M.: Notions of black-box reductions, revisited. In: Advances in Cryptology- ASIACRYPT 2013: 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, 1–5 December 2013, Proceedings, Part I, 19, pp. 296–315. Springer, Heidelberg (2013)
[BCKM21]
[BCQ23]
Brakerski, Z., Canetti, R., Qian, L.: On the computational hardness needed for quantum cryptography. In: 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, p. 24. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing (2023)
[BDF+99]
Bennett, C.H., et al.: Quantum nonlocality without entanglement. Phys. Rev. A 59(2), 1070 (1999)
[BFM19]
Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pp. 329–349 (2019)
[BGVV+23]
Bouaziz, S., Grilo, A.B., Vergnaud, D., Vu, Q.-H., et al.: Towards the impossibility of quantum public key encryption with classical keys from one-way functions. In: Cryptology ePrint Archive (2023)
[BL18]
Benhamouda, F., Lin, H.: k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits. In: Advances in Cryptology–EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, 29 April–3 May 2018, Part II 37, pp. 500–532. Springer, Cham (2018)
[BM+24]
Bouaziz, S., Muguruza, G., et al.: Quantum Pseudorandomness Cannot be Shrunk in a Black-Box Way. In: Cryptology ePrint Archive (2024)
[Bra23]
Brakerski, Z.: Black-hole radiation decoding is quantum cryptography. In: Annual International Cryptology Conference, pp. 37–65. Springer (2023)
[CCHL22]
Chen, S., Cotler, J., Huang, H.-Y., Li, J.: Exponential separations between learning with and without quantum memory. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 574–585. IEEE (2022)
[CCS24]
Chen, B., Coladangelo, A., Sattath, O.: The power of a single Haar random state: constructing and separating quantum pseudorandomness. In: arXiv preprint arXiv:​2404.​03295 (2024)
[CF01]
Canetti, R., Fischlin, M.: Universally composable commitments. In: Advances in Cryptology—CRYPTO 2001: 21st Annual International Cryptology Conference, Santa Barbara, 19–23 August 2001 Proceedings 21, pp. 19–40. Springer, Heidelberg (2001)
[CGG24]
Chung, K.-M., Goldin, E., Gray, M.: On central primitives for quantum cryptography with classical communication. arXiv preprint arXiv:​ 2402.​17715 [cs.CR] (2024)
[CH14]
Chitambar, E., Hsieh, M.-H.: Asymptotic state discrimination and a strict hierarchy in distinguishability norms. J. Math. Phys. 55(11) (2014)
[CLM+14]
Chitambar, E., Leung, D., Mančinska, L., Ozols, M., Winter, A.: Everything you always wanted to know about LOCC (but were afraid to ask). Commun. Math. Phys. 328, 303–326 (2014)
[CLM23]
Chung, K.-M., Lin, Y.-T., Mahmoody, M.: Black-box separations for non-interactive classical commitments in a quantum world. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 144–172. Springer, Cham (2023)
[CLMO13]
Childs, A.M., Leung, D., Mančinska, L., Ozols, M.: A framework for bounding nonlocality of state discrimination. Commun. Math. Phys. 323, 1121–1153 (2013)
[CLOS02]
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 494–503 (2002)
[CM24]
Coladangelo, A., Mutreja, S.: On black-box separations of quantum digital signatures from pseudorandom states. arXiv preprint arXiv:​2402.​08194 (2024)
[Col23]
[DLT02]
DiVincenzo, D.P., Leung, D.W., Terhal, B.M.: Quantum data hiding. IEEE Trans. Inf. Theory 48(3), 580–598 (2002)MathSciNetCrossRef
[EW02]
Eggeling, T., Werner, R.F.: Hiding classical data in multipartite quantum states. Phys. Rev. Lett. 89(9), 097905 (2002)
[Gea02]
Gea-Banacloche, J.: Hiding messages in quantum data. In: J. Math. Phys. 43(9), 4531–4536 (2002)
[GGM86]
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792–807 (1986)
[GLSV21]
[GS22]
Garg, S., Srinivasan, A.: Two-round multiparty secure computation from minimal assumptions. J. ACM 69(5), 1–30 (2022)
[Har13]
[Har23]
Harrow, A.W.: Approximate orthogonality of permutation operators, with application to quantum information. Lett. Math. Phys. 114(1), 1 (2023)
[HBAB19]
Halder, S., Banik, M., Agrawal, S., Bandyopadhyay, S.: Strong quantum nonlocality without entanglement. Phys. Rev. Lett. 122(4), 040403 (2019)
[HLS05]
Hayden, P., Leung, D., Smith, G.: Multiparty data hiding of quantum information. Phys. Rev. A 71(6), 062339 (2005)
[HY20]
Hosoyamada, A., Yamakawa, T.: Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness. In: Advances in Cryptology– ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, 7–11 December 2020, Proceedings, Part I, 26, pp. 3–32. Springer, Cham (2020)
[JLS18]
[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, 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
[LC97]
Lo, H.-K., Chau, H.F.: Is quantum bit commitment really possible? Phys. Rev. Lett. 78(17), 3410 (1997)
[LLLL24]
[May97]
Mayers, D.: Unconditionally secure quantum bit commitment is impossible. Phys. Rev. Lett. 78(17), 3414 (1997)
[MNY23]
Morimae, T., Nehoran, B., Yamakawa, T.: Unconditionally secure commitments with quantum auxiliary inputs. arXiv preprint arXiv:​2311.​18566 [quant-ph] (2023)
[MWW09]
Matthews, W., Wehner, S., Winter, A.: Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding. Commun. Math. Phys. 291, 813–843 (2009)
[MY21]
[MY23]
[NC10]
[PNC14]
Piani, M., Narasimhachar, V., Calsamiglia, J.: Quantumness of correlations, quantumness of ensembles and quantum data hiding. New J. Phys. 16(11), 113001 (2014)
[Qia23]
Qian, L.: Unconditionally secure quantum commitments with preprocessing. In: Cryptology ePrint Archive (2023)
[RTV04]
Reingold, O., Trevisan, L., Vadhan, S.: Notions of reducibility between cryptographic primitives. In: Theory of Cryptography Conference, pp. 1–20. Springer, Heidelberg (2004)
[Yan2]
Yan, J.: General properties of quantum bit commitments. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 628–657. Springer, Cham (2022)
Metadaten
Titel
Cryptography in the Common Haar State Model: Feasibility Results and Separations
verfasst von
Prabhanjan Ananth
Aditya Gulati
Yao-Ting Lin
Copyright-Jahr
2025
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_4

Premium Partner

    Bildnachweise