Top

Published in:

2025 | OriginalPaper | Chapter

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

Authors : Prabhanjan Ananth, Aditya Gulati, Yao-Ting Lin

Published in: Theory of Cryptography

Publisher: Springer Nature Switzerland

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

search-config

AI-assisted search

Off

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.

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 Split-State Non-malleable Codes and Secret Sharing Schemes for Quantum Messages

next chapter Robust Combiners and Universal Constructions for Quantum Cryptography

We note that [Kre21] made similar use of infinitely many oracles to prove a separation between pseudorandom states and one-way functions.

We encourage readers unfamiliar with type states to refer to Definition 7.

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 \}\).

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}\).

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.

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.

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.

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.

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.

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.

We identify \([0:t]^N\) as \([0:t]^A\).

Here we allow the subsets to contain duplicate elements.

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.

Since T is collision-free, we will treat it as a set.

Since T might have collisions, \(T_1\) is allowed to contain duplicate elements.

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.

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.

[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]

Ananth, P., Gulati, A., Kaleoglu, F., Lin, Y.- T.: Pseudorandom Isometries. arXiv preprint arXiv:2311.02901 [quant-ph] (2023)

[AGL24]

Ananth, P., Gulati, A., Lin, Y.-T.: Cryptography in the common Haar state model: feasibility results and separations. Cryptology ePrint Archive, Paper 2024/1043 (2024). https://eprint.iacr.org/2024/1043

[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]

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_17CrossRef

[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]

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

[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]

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_18CrossRef

[GS22]

Garg, S., Srinivasan, A.: Two-round multiparty secure computation from minimal assumptions. J. ACM 69(5), 1–30 (2022)

[Har13]

Harrow, A.W.: The church of the symmetric subspace. arXiv preprint arXiv:1308.6595 (2013)

[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]

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

[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]

Li, L., Li, Q., Li, X., Liu, Q.: How (not) to build quantum PKE in Minicrypt. arXiv preprint arXiv:2405.20295 (2024)

[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]

Morimae, T., Yamakawa, T.: Quantum commitments and signatures without one-way functions. arXiv preprint arXiv:2112.06369 (2021)

[MY23]

Morimae, T., Yamakawa, T.: One-wayness in quantum cryptography. arXiv preprint arXiv:2210.03394 [quant-ph] (2023)

[NC10]

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press (2010). https://doi.org/10.1017/CBO9780511976667

[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)

Title: Cryptography in the Common Haar State Model: Feasibility Results and Separations
Authors: Prabhanjan Ananth
Aditya Gulati
Yao-Ting Lin
Publisher: Springer Nature Switzerland
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_4

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"