Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Classical Proofs of Quantum Knowledge
 
conference paper

Classical Proofs of Quantum Knowledge

Vidick, Thomas  orcid-logo
•
Zhang, Tina
Canteaut, Anne
•
Standaert, François-Xavier
2021
Advances in Cryptology – EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part II
40th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT)

We define the notion of a proof of knowledge in the setting where the verifier is classical, but the prover is quantum, and where the witness that the prover holds is in general a quantum state. We establish simple properties of our definition, including that, if a nondestructive classical proof of quantum knowledge exists for some state, then that state can be cloned by an unbounded adversary, and that, under certain conditions on the parameters in our definition, a proof of knowledge protocol for a hard-to-clone state can be used as a (destructive) quantum money verification protocol. In addition, we provide two examples of protocols (both inspired by private-key classical verification protocols for quantum money schemes) which we can show to be proofs of quantum knowledge under our definition. In so doing, we introduce techniques for the analysis of such protocols which build on results from the literature on nonlocal games. Finally, we show that, under our definition, the verification protocol introduced by Mahadev (FOCS 2018) is a classical argument of quantum knowledge for QMA relations. In all cases, we construct an explicit quantum extractor that is able to produce a quantum witness given black-box quantum (rewinding) access to the prover, the latter of which includes the ability to coherently execute the prover’s black-box circuit controlled on a superposition of messages from the verifier.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-030-77886-6_22
Scopus ID

2-s2.0-85111194526

Author(s)
Vidick, Thomas  orcid-logo

California Institute of Technology

Zhang, Tina

California Institute of Technology

Editors
Canteaut, Anne
•
Standaert, François-Xavier
Date Issued

2021

Publisher

Springer Nature (Switzerland)

Publisher place

Cham

Published in
Advances in Cryptology – EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part II
ISBN of the book

9783030778859

9783030778866

Series title/Series vol.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); LNCS 12697

ISSN (of the series)

1611-3349

0302-9743

Start page

630

End page

660

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
Non-EPFL  
Event nameEvent acronymEvent placeEvent date
40th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT)

Zagreb, CROATIA

2021-10-17 - 2021-10-21

FunderFunding(s)Grant NumberGrant URL

DARPA

HR00112020023

AFOSR

FA9550-16-1-0495

NSF

CCF-1553477

Show more
Available on Infoscience
November 21, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/256176
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés