License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.67
URN: urn:nbn:de:0030-drops-181197
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18119/
Gheorghiu, Alexandru ;
Metger, Tony ;
Poremba, Alexander
Quantum Cryptography with Classical Communication: Parallel Remote State Preparation for Copy-Protection, Verification, and More
Abstract
Quantum mechanical effects have enabled the construction of cryptographic primitives that are impossible classically. For example, quantum copy-protection allows for a program to be encoded in a quantum state in such a way that the program can be evaluated, but not copied. Many of these cryptographic primitives are two-party protocols, where one party, Bob, has full quantum computational capabilities, and the other party, Alice, is only required to send random BB84 states to Bob. In this work, we show how such protocols can generically be converted to ones where Alice is fully classical, assuming that Bob cannot efficiently solve the LWE problem. In particular, this means that all communication between (classical) Alice and (quantum) Bob is classical, yet they can still make use of cryptographic primitives that would be impossible if both parties were classical. We apply this conversion procedure to obtain quantum cryptographic protocols with classical communication for unclonable encryption, copy-protection, computing on encrypted data, and verifiable blind delegated computation.
The key technical ingredient for our result is a protocol for classically-instructed parallel remote state preparation of BB84 states. This is a multi-round protocol between (classical) Alice and (quantum polynomial-time) Bob that allows Alice to certify that Bob must have prepared n uniformly random BB84 states (up to a change of basis on his space). While previous approaches could only certify one- or two-qubit states, our protocol allows for the certification of an n-fold tensor product of BB84 states. Furthermore, Alice knows which specific BB84 states Bob has prepared, while Bob himself does not. Hence, the situation at the end of this protocol is (almost) equivalent to one where Alice sent n random BB84 states to Bob. This allows us to replace the step of preparing and sending BB84 states in existing protocols by our remote-state preparation protocol in a generic and modular way.
BibTeX - Entry
@InProceedings{gheorghiu_et_al:LIPIcs.ICALP.2023.67,
author = {Gheorghiu, Alexandru and Metger, Tony and Poremba, Alexander},
title = {{Quantum Cryptography with Classical Communication: Parallel Remote State Preparation for Copy-Protection, Verification, and More}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {67:1--67:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18119},
URN = {urn:nbn:de:0030-drops-181197},
doi = {10.4230/LIPIcs.ICALP.2023.67},
annote = {Keywords: Quantum cryptography, Remote state preparation, Self-testing, Learning with errors, Quantum copy-protection, Unclonable encryption, Quantum verification}
}
Keywords: |
|
Quantum cryptography, Remote state preparation, Self-testing, Learning with errors, Quantum copy-protection, Unclonable encryption, Quantum verification |
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
Issue Date: |
|
2023 |
Date of publication: |
|
05.07.2023 |