nach oben

Erschienen in:

2022 | OriginalPaper | Buchkapitel

Certified Everlasting Zero-Knowledge Proof for QMA

verfasst von : Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, Takashi Yamakawa

Erschienen in: Advances in Cryptology – CRYPTO 2022

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

In known constructions of classical zero-knowledge protocols for \({\textbf {NP}}\), either zero-knowledge or soundness holds only against computationally bounded adversaries. Indeed, achieving both statistical zero-knowledge and statistical soundness at the same time with classical verifier is impossible for \({\textbf {NP}}\) unless the polynomial-time hierarchy collapses, and it is also believed to be impossible even with a quantum verifier. In this work, we introduce a novel compromise, which we call the certified everlasting zero-knowledge proof for \({\textbf {QMA}}\). It is a computational zero-knowledge proof for \({\textbf {QMA}}\), but the verifier issues a classical certificate that shows that the verifier has deleted its quantum information. If the certificate is valid, even an unbounded malicious verifier can no longer learn anything beyond the validity of the statement.

We construct a certified everlasting zero-knowledge proof for \({\textbf {QMA}}\). For the construction, we introduce a new quantum cryptographic primitive, which we call commitment with statistical binding and certified everlasting hiding, where the hiding property becomes statistical once the receiver has issued a valid certificate that shows that the receiver has deleted the committed information. We construct commitment with statistical binding and certified everlasting hiding from quantum encryption with certified deletion by Broadbent and Islam [TCC 2020] (in a black-box way), and then combine it with the quantum sigma-protocol for \({\textbf {QMA}}\) by Broadbent and Grilo [FOCS 2020] to construct the certified everlasting zero-knowledge proof for \({\textbf {QMA}}\). Our constructions are secure in the quantum random oracle model. Commitment with statistical binding and certified everlasting hiding itself is of independent interest, and there will be many other useful applications beyond zero-knowledge.

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 from Pseudorandom Quantum States

Nächstes Kapitel Quantum Commitments and Signatures Without One-Way Functions

We mention that everlasting zero-knowledge arguments, which only satisfy computational soundness, can exist. Indeed, any statistical zero-knowledge argument is an everlasting zero-knowledge argument. One may think that the computational soundness is fine since that ensures everlasting soundness in the sense of Unruh’s definition [Unr13]. For practical purposes, this may be true. On the other hand, we believe that it is theoretically interesting to pursue (a kind of) everlasting zero-knowledge without compromising the soundness as is done in this paper.

A similar argument does not work for quantum verifiers since the honest-verifier quantum statistical zero-knowledge [Wat02] requires a simulator to simulate honest verifier’s internal state at any point of the protocol execution. This is not implied by certified everlasting zero-knowledge, which only requires security after generating a valid deletion certificate.

One may think that we can just use statistically hiding commitment. However, such a commitment can only satisfy computational binding, which is not sufficient for achieving certified everlasting zero-knowledge proofs rather than arguments.

For this definition to make sense, we need to require that \(\textsf{com}=\textsf{Commit}(R)\) is classical. This can be ensured if the honest receiver measures it as soon as receiving it even if only quantum communication channel is available.

[ACGH20]

Alagic, G., Childs, A.M., Grilo, A.B., Hung, S.-H.: Non-interactive Classical Verification of Quantum Computation. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12552, pp. 153–180. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_6CrossRefMATH

[AHU19]

Ambainis, A., Hamburg, M., Unruh, D.: Quantum security proofs using semi-classical oracles. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 269–295. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_10

[BB21]

Bitansky, N., Brakerski, Z.: Classical binding for quantum commitments. IACR Cryptol. ePrint Arch. 2021, 1001 (2021)

[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, vol. 12825, pp. 406–435. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_15CrossRef

[BDF+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, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_3CrossRefMATH

[BG20]

Broadbent, A., Grilo, A.B.: QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge. In: 61st FOCS, pp. 196–205. IEEE Computer Society Press (2020)

[BI20]

Broadbent, A., Islam, R.: Quantum encryption with certified deletion. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12552, pp. 92–122. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_4CrossRef

[BJSW16]

Broadbent, A., Ji, Z., Song, F., Watrous, J.: Zero-knowledge proof systems for QMA. In: Dinur, I. (ed.) 57th FOCS, pp. 31–40. IEEE Computer Society Press (2016)

[BM21]

Bartusek, J., Malavolta, G.: Candidate obfuscation of null quantum circuits and witness encryption for QMA. IACR Cryptol. ePrint Arch. 2021, 421 (2021)

[BS20]

Bitansky, N., Shmueli, O.: Post-quantum zero knowledge in constant rounds. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. (eds.) 52nd ACM STOC, pp. 269–279. ACM Press (2020)

[BY20]

Brakerski, Z., Yuen, H.: Quantum garbled circuits. arXiv preprint arXiv:2006.01085 (2020)

[CCKV08]

Chailloux, A., Ciocan, D.F., Kerenidis, I., Vadhan, S.: Interactive and noninteractive zero knowledge are equivalent in the help model. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 501–534. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_28CrossRef

[CDMS04]

Crépeau, C., Dumais, P., Mayers, D., Salvail, L.: Computational collapse of quantum state with application to oblivious transfer. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 374–393. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_21CrossRefMATH

[CM21]

Chardouvelis, O., Malavolta, G.: The round complexity of quantum zero-knowledge. IACR Cryptol. ePrint Arch. (2021)

[CVZ20]

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

[DFR+07]

Damgård, I.B., Fehr, S., Renner, R., Salvail, L., Schaffner, C.: A tight high-order entropic quantum uncertainty relation with applications. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 360–378. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_20CrossRef

[DFS04]

Damgård, I., Fehr, S., Salvail, L.: Zero-knowledge proofs and string commitments with standing quantum attacks. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 254–272. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_16CrossRef

[For87]

Fortnow, L.: The complexity of perfect zero-knowledge (extended abstract). In: Aho, A. (ed.) 19th ACM STOC, pp. 204–209. ACM Press (1987)

[FUW+20]

Fang, J., Unruh, D., Weng, J., Yan, J., Zhou, D.: How to base security on the perfect/statistical binding property of quantum bit commitment? IACR Cryptol. ePrint Arch. 2020, 621 (2020)

[GMR89]

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)MathSciNetCrossRef

[GSV98]

Goldreich, O., Sahai, A., Vadhan, S.P.: Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In: 30th ACM STOC, pp. 399–408. ACM Press (1998)

[GSY19]

Grilo, A.B., Slofstra, W., Yuen, H.: Perfect zero knowledge for quantum multiprover interactive proofs. In: Zuckerman, D. (ed.) 60th FOCS, pp. 611–635. IEEE Computer Society Press (2019)

[HMNY21a]

Hiroka, T., Morimae, T., Nishimaki, R., Yamakawa, T.: Certified everlasting zero-knowledge proof for QMA. IACR Cryptol. ePrint Arch. 2021, 1315 (2021)

[HMNY21b]

Hiroka, T., Morimae, T., Nishimaki, R., Yamakawa, T.: Quantum encryption with certified deletion, revisited: public key, attribute-based, and classical communication. IACR Cryptol. ePrint Arch. 2021, 617 (2021)

[Kob03]

Kobayashi, H.: Non-interactive quantum perfect and statistical zero-knowledge. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 178–188. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-24587-2_20CrossRefMATH

[LC97]

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

[LS19]

Lombardi, A., Schaeffer, L.: A note on key agreement and non-interactive commitments. Cryptology ePrint Archive, Report 2019/279 (2019). https://eprint.iacr.org/2019/279

[May97]

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

[MW18]

Menda, S., Watrous, J.: Oracle separations for quantum statistical zero-knowledge. arXiv preprint arXiv:1801.08967 (2018)

[MY21]

Morimae, T., Yamakawa, T.: Classically verifiable (dual-mode) NIZK for QMA with preprocessing. arXiv preprint arXiv:2102.09149 (2021)

[Shm21]

Shmueli, O.: Multi-theorem designated-verifier NIZK for QMA. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12825, pp. 375–405. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_14CrossRef

[Unr13]

Unruh, D.: Everlasting multi-party computation. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 380–397. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_22CrossRef

[Unr15]

Unruh, D.: Revocable quantum timed-release encryption. J. ACM 62(6), 49:1–49:76 (2015)

[Wat02]

Watrous, J.: Limits on the power of quantum statistical zero-knowledge. In: 43rd FOCS, pp. 459–470. IEEE Computer Society Press (2002)

[Wat09]

Watrous, J.: Zero-knowledge against quantum attacks. SIAM J. Comput. 39(1), 25–58 (2009)MathSciNetCrossRef

[Yan20]

Yan, J.: Quantum computationally predicate-binding commitment with application in quantum zero-knowledge argument for NP. IACR Cryptol. ePrint Arch. 2020, 1510 (2020)

[YWLQ15]

Yan, J., Weng, J., Lin, D., Quan, Y.: Quantum bit commitment with application in quantum zero-knowledge proof (extended abstract). In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 555–565. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48971-0_47CrossRef

[Zha19]

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

Titel: Certified Everlasting Zero-Knowledge Proof for QMA
verfasst von: Taiga Hiroka
Tomoyuki Morimae
Ryo Nishimaki
Takashi Yamakawa
Verlag: Springer Nature Switzerland
Buch: Advances in Cryptology – CRYPTO 2022
Print ISBN: 978-3-031-15801-8

Electronic ISBN: 978-3-031-15802-5

Copyright-Jahr: 2022
DOI: https://doi.org/10.1007/978-3-031-15802-5_9

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