We investigate the round complexity of maliciously-secure two-party quantum computation (2PQC) with setup, and obtain the following results: - 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, including an impossibility result for a natural class of simulators, and 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.
翻译:我们用设置来调查恶意保密的双方量子计算(2PQC)的全方位复杂性,并获得以下结果: - 通用随机字符串模式的三条消息协议(如果只有一方收到输出,则两条消息),假设典型的两条消息隐含的转移(OT),带有分子后恶性恶意安全。这一回合的复杂性对于顺序通信环境来说是最佳的。根据为NP提供的可重复使用的恶意指定非互动性零知识(MDV-NIZK)参数的额外假设,我们的技术为QMA提供了MDV-NIZK。上述每个假设都是从错误学习的量性硬度(QLWE)中知道的。 - 在量级预处理模型中,假定子爆炸后QWE。 事实上,我们在 CRS模型中建立一个三轮协议协议,只有两轮在线通信(MDV-NIZK),这意味着以上结果。我们开发了一个新的延迟模拟模拟技术,我们称之为“透性Q,通过初始测试进行一种直方标准,可能是一种自然结果。