Abstract
Quantum mechanical effects have enabled the construction of cryptographic primitives that are impossible classically. For example, quantum copyprotection 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 twoparty 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, copyprotection, computing on encrypted data, and verifiable blind delegated computation.
The key technical ingredient for our result is a protocol for classicallyinstructed parallel remote state preparation of BB84 states. This is a multiround protocol between (classical) Alice and (quantum polynomialtime) 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 twoqubit states, our protocol allows for the certification of an nfold 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 remotestate 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 CopyProtection, Verification, and More}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {67:167:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772785},
ISSN = {18688969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18119},
URN = {urn:nbn:de:0030drops181197},
doi = {10.4230/LIPIcs.ICALP.2023.67},
annote = {Keywords: Quantum cryptography, Remote state preparation, Selftesting, Learning with errors, Quantum copyprotection, Unclonable encryption, Quantum verification}
}
Keywords: 

Quantum cryptography, Remote state preparation, Selftesting, Learning with errors, Quantum copyprotection, Unclonable encryption, Quantum verification 
Collection: 

50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) 
Issue Date: 

2023 
Date of publication: 

05.07.2023 