nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Interactive Oracle Arguments in the QROM and Applications to Succinct Verification of Quantum Computation

verfasst von : Islam Faisal

Erschienen in: Topics in Cryptology – CT-RSA 2024

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

This work is motivated by the following question: can an untrusted quantum server convince a classical verifier of the answer to an efficient quantum computation using only polylogarithmic communication? We show how to achieve this in the quantum random oracle model (QROM), after a non-succinct instance-independent setup phase.

We introduce and formalize the notion of post-quantum interactive oracle arguments for languages in QMA, a generalization of interactive oracle proofs (Ben-Sasson–Chiesa–Spooner). We then show how to compile any non-adaptive public-coin interactive oracle argument (with private setup) into a succinct argument (with setup) in the QROM.

To conditionally answer our motivating question via this framework under the post-quantum hardness assumption of LWE, we show that the ZX local Hamiltonian problem with at least inverse-polylogarithmic relative promise gap has an interactive oracle argument with instance-independent setup, which we can then compile.

Assuming a variant of the quantum PCP conjecture that we introduce called the weak ZX quantum PCP conjecture, we obtain a succinct argument for QMA (and consequently the verification of quantum computation) in the QROM (with non-succinct instance-independent setup) which makes only black-box use of the underlying cryptographic primitives.

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 Ascon MAC, PRF, and Short-Input PRF

Nächstes Kapitel SoK: Parameterization of Fault Adversary Models Connecting Theory and Practice

The Pauli X, Z matrices are \(X = \begin{pmatrix} 0 &{} 1\\ 1 &{} 0 \end{pmatrix}, Z = \begin{pmatrix} 1 &{} 0\\ 0 &{} -1 \end{pmatrix}\) and they are used frequently in physics and quantum computation.

Consider, for example, the universal gate set \(G = \{H, X, \textsc {CCNOT} \}\). Note that \(H = \frac{1}{\sqrt{2}} (X + Z)\) and \(\textsc {CCNOT} = I - \frac{1}{4}(I - Z_1)(I - Z_2)(I - X_3)\). G is a universal gate set with real matrices and can be used to obtain propagation Hamiltonians whose Pauli decomposition has the real Pauli matrices X and Z.

It is known how to efficiently prepare such history state for an efficient quantum computation, but we do not include the details here.

We conjecture that it is possible to reduce the number of messages to 3 in our work. More details are provided in the extended version of this paper [21].

In this paper we will only work with classical Merkle trees where the data are classical strings and the (honest) algorithms are executed on classical devices. However, their security is established against a cheating quantum device in the quantum random oracle model.

This is equivalent to sending each overlapping intermediate node once instead of sending it multiple times inside possibly overlapping paths for each leaf. However, for easier notation and exposition, we send the authentication paths for each leaf and require this consistency condition when verifying a batch of authentication paths.

It is an open question whether they are equivalent under classical reductions. In fact, the proof checking formulation itself could end up being more specific than that provided in [1] which was the reason why it was not straightforward to prove the equivalence under classical reductions. For the details of the quantum reduction, we refer the reader to the proof of Theorem 5.5. in [24].

Later, we will use the term “public-coin protocols with private setup” to highlight this again.

Please refer to the extended version of this paper [21] for full details on the choice of these thresholds as well as the Test and Hadamard round of the Mahadev protocol.

In most useful interactive oracle arguments including the argument system for the local Hamiltonian problem discussed in this paper, we do not have to know the input length exactly, but it suffices to know an upper bound.

Keeping the randomness used in the setup enables the verifier to store information such as secret keys and/or trapdoors without revealing them to the prover.

or its oracle messages.

Aharonov, D., Arad, I., Landau, Z., Vazirani, U.: The detectability lemma and quantum gap amplification. In: Proceedings of the 41st Annual ACM Symposium on Symposium on Theory of Computing, STOC 2009 (2009). https://doi.org/10.1145/1536414.1536472

Aharonov, D., Arad, I., Vidick, T.: The Quantum PCP Conjecture (2013)

Alagic, G., Childs, A.M., Grilo, A.B., Hung, S.: Non-interactive classical verification of quantum computation. In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part III. LNCS, vol. 12552, pp. 153–180. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_6CrossRef

Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501–555 (1998). https://doi.org/10.1145/278298.278306MathSciNetCrossRef

Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70–122 (1998). https://doi.org/10.1145/273865.273901MathSciNetCrossRef

Bartusek, J., et al.: Succinct classical verification of quantum computation. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part II. LNCS, vol. 13508, pp. 195–211. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_7CrossRef

Bartusek, J., Malavolta, G.: Indistinguishability obfuscation of null quantum circuits and applications. In: Braverman, M. (ed.) 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, Berkeley, CA, USA, 31 January–3 February 2022. LIPIcs, vol. 215, pp. 15:1–15:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.ITCS.2022.15

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, CCS 1993, pp. 62–73. Association for Computing Machinery, New York (1993). https://doi.org/10.1145/168588.168596

Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Hirt, M., Smith, A. (eds.) Theory of Cryptography, pp. 31–60. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53644-5_2CrossRef

10.

Biamonte, J.D., Love, P.J.: Realizable Hamiltonians for universal adiabatic quantum computers. Phys. Rev. A 78(1) (2008). https://doi.org/10.1103/physreva.78.012352

11.

Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Cham (2011). https://doi.org/10.1007/978-3-642-25385-0_3CrossRef

12.

Chen, L., Movassagh, R.: Quantum Merkle trees (2021). https://doi.org/10.48550/ARXIV.2112.14317

13.

Chia, N., Chung, K., Yamakawa, T.: Classical verification of quantum computations with efficient verifier. In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part III. LNCS, vol. 12552, pp. 181–206. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_7CrossRef

14.

Chiesa, A., Ma, F., Spooner, N., Zhandry, M.: Post-quantum succinct arguments: breaking the quantum rewinding barrier. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, 7–10 February 2022, pp. 49–58. IEEE (2021). https://doi.org/10.1109/FOCS52979.2021.00014

15.

Chiesa, A., Manohar, P., Spooner, N.: Succinct arguments in the quantum random oracle model. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019, Part II. LNCS, vol. 11892, pp. 1–29. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36033-7_1CrossRef

16.

Childs, A.M.: Secure assisted quantum computation. Quantum Inf. Comput. 5(6), 456–466 (2005). https://doi.org/10.26421/QIC5.6-4MathSciNetCrossRef

17.

Coladangelo, A., Vidick, T., Zhang, T.: Non-interactive zero-knowledge arguments for QMA, with preprocessing. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part III. LNCS, vol. 12172, pp. 799–828. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_28CrossRef

18.

Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC 1971, pp. 151–158. Association for Computing Machinery, New York (1971). https://doi.org/10.1145/800157.805047

19.

Don, J., Fehr, S., Majenz, C., Schaffner, C.: Efficient NIZKs and signatures from commit-and-open protocols in the QROM. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part II. LNCS, vol. 13508, pp. 729–757. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_25CrossRef

20.

Don, J., Fehr, S., Majenz, C., Schaffner, C.: Online-extractability in the quantum random-oracle model. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part III. LNCS, vol. 13277, pp. 677–706. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-07082-2_24CrossRef

21.

Faisal, I.: Interactive oracle arguments in the QROM and applications to succinct verification of quantum computation. Cryptology ePrint Archive, Paper 2023/421 (2023). https://eprint.iacr.org/2023/421

22.

Fitzsimons, J., Hajdušek, M., Morimae, T.: Post hoc verification of quantum computation. Phys. Rev. Lett. 120(4) (2018)

23.

Gheorghiu, A., Kapourniotis, T., Kashefi, E.: Verification of quantum computation: an overview of existing approaches. Theory Comput. Syst. 63(4), 715–808 (2018). https://doi.org/10.1007/s00224-018-9872-3MathSciNetCrossRef

24.

Grilo, A.B.: Quantum proofs, the local Hamiltonian problem and applications. (Preuves quantiques, le problème des Hamiltoniens locaux et applications). Ph.D. thesis, Sorbonne Paris Cité, France (2018). https://tel.archives-ouvertes.fr/tel-02152364

25.

Gunn, S., Ju, N., Ma, F., Zhandry, M.: Commitments to quantum states. Cryptology ePrint Archive, Paper 2022/1358 (2022). https://eprint.iacr.org/2022/1358

26.

Kempe, J., Kitaev, A., Regev, O.: The complexity of the local Hamiltonian problem. SIAM J. Comput. 35(5), 1070–1097 (2006). https://doi.org/10.1137/s0097539704445226MathSciNetCrossRef

27.

Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC 1992, pp. 723–732. Association for Computing Machinery, New York (1992). https://doi.org/10.1145/129712.129782

28.

Kitaev, A.: Quantum NP (1999). Talk at AQIP’99: Second Workshop on Algorithms in Quantum Information Processing

29.

Levin, L.A.: Universal sequential search problems. Problemy peredachi informatsii 9(3), 115–116 (1973)

30.

Mahadev, U.: Classical homomorphic encryption for quantum circuits. In: Thorup, M. (ed.) 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, 7–9 October 2018, pp. 332–338. IEEE Computer Society (2018). https://doi.org/10.1109/FOCS.2018.00039

31.

Mahadev, U.: Classical verification of quantum computations. In: 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, 7–9 October 2018, pp. 259–267 (2018). https://doi.org/10.1109/FOCS.2018.00033

32.

Merkle, R.C.: A digital signature based on a conventional encryption function. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 369–378. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-48184-2_32CrossRef

33.

Morimae, T., Fitzsimons, J.F.: Post hoc verification with a single prover. arXiv preprint arXiv:1603.06046 (2016)

34.

Morimae, T., Nagaj, D., Schuch, N.: Quantum proofs can be verified using only single-qubit measurements. Phys. Rev. A 93(2) (2016). https://doi.org/10.1103/physreva.93.022326

35.

Takeuchi, Y., Morimae, T., Tani, S.: Sumcheck-based delegation of quantum computing to rational server. Theor. Comput. Sci. 924, 46–67 (2022). https://doi.org/10.1016/j.tcs.2022.04.016. https://www.sciencedirect.com/science/article/pii/S0304397522002250

36.

Unruh, D.: Collapse-binding quantum commitments without random oracles. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 166–195. Springer, Cham (2016). https://doi.org/10.1007/978-3-662-53890-6_6CrossRef

37.

Unruh, D.: Computationally binding quantum commitments. In: Fischlin, M., Coron, J. (eds.) EUROCRYPT 2016, Part II. LNCS, vol. 9666, pp. 497–527. Springer, Cham (2016). https://doi.org/10.1007/978-3-662-49896-5_18CrossRef

38.

Vidick, T., Zhang, T.: Classical zero-knowledge arguments for quantum computations. IACR Cryptology ePrint Archive 2019, 194 (2019). https://eprint.iacr.org/2019/194

39.

Zhandry, M.: How to record quantum queries, and applications to quantum indifferentiability. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part II. LNCS, vol. 11693, pp. 239–268. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_9CrossRef

40.

Zhang, J.: Succinct blind quantum computation using a random oracle. In: Khuller, S., Williams, V.V. (eds.) STOC 2021: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, 21–25 June 2021, pp. 1370–1383. ACM (2021). https://doi.org/10.1145/3406325.3451082

41.

Zhang, J.: Classical verification of quantum computations in linear time. In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, 31 October–3 November 2022, pp. 46–57. IEEE (2022). https://doi.org/10.1109/FOCS54457.2022.00012

Titel: Interactive Oracle Arguments in the QROM and Applications to Succinct Verification of Quantum Computation
verfasst von: Islam Faisal
Verlag: Springer Nature Switzerland
Buch: Topics in Cryptology – CT-RSA 2024
Print ISBN: 978-3-031-58867-9

Electronic ISBN: 978-3-031-58868-6

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-3-031-58868-6_16

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