- A three-message protocol (two-message if only one party receives output) in the common random string (CRS) model assuming classical two-message oblivious transfer (OT) with post-quantum malicious security. This round complexity is optimal for the sequential communication setting. Under the additional assumption of reusable malicious designated-verifier non-interactive zero-knowledge (MDV-NIZK) arguments for NP, our techniques give an MDV-NIZK for QMA. Each of the assumptions mentioned above is known from the quantum hardness of learning with errors (QLWE).
- A protocol with two simultaneous rounds of communication, in a quantum preprocessing model, assuming sub-exponential QLWE. In fact, we construct a three-round protocol in the CRS model with only two rounds of online communication, which implies the above result. Along the way, we develop a new delayed simulation technique that we call "simulation via teleportation," which may be useful in other settings.
In addition, we perform a preliminary investigation into barriers and possible approaches for two-round 2PQC in the CRS model. We provide evidence that protocols admitting a natural class of simulators do not exist, and also give a proof-of-concept construction from a strong form of quantum virtual black-box (VBB) obfuscation.
Prior to our work, maliciously-secure 2PQC required round complexity linear in the size of the quantum circuit.
Category / Keywords: cryptographic protocols / secure quantum computation Date: received 22 Nov 2020, last revised 11 Dec 2020 Contact author: bartusek james at gmail com,andrea coladangelo@gmail com,dakshita@illinois edu,fermima@alum mit edu Available format(s): PDF | BibTeX Citation Note: updated acknowledgments Version: 20201212:040151 (All versions of this report) Short URL: ia.cr/2020/1471