Related papers: Quantum Advantage from Any Non-Local Game

Quantum Advantage from Any Non-Local Game

URL: http://arxiv.org/abs/2203.15877v1
Date: Tue, 29 Mar 2022 19:45:44 GMT
Title: Quantum Advantage from Any Non-Local Game
Authors: Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, Lisa Yang
Abstract summary: We show a general method of compiling any $k$-prover non-local game into a single-prover interactive game. Our compiler uses any quantum homomorphic encryption scheme.
Score: 14.903809621145893
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We show a general method of compiling any $k$-prover non-local game into a single-prover interactive game maintaining the same (quantum) completeness and (classical) soundness guarantees (up to negligible additive factors in a security parameter). Our compiler uses any quantum homomorphic encryption scheme (Mahadev, FOCS 2018; Brakerski, CRYPTO 2018) satisfying a natural form of correctness with respect to auxiliary (quantum) input. The homomorphic encryption scheme is used as a cryptographic mechanism to simulate the effect of spatial separation, and is required to evaluate $k-1$ prover strategies (out of $k$) on encrypted queries. In conjunction with the rich literature on (entangled) multi-prover non-local games starting from the celebrated CHSH game (Clauser, Horne, Shimonyi and Holt, Physical Review Letters 1969), our compiler gives a broad framework for constructing mechanisms to classically verify quantum advantage.

Related papers

(Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
Indifferentiability is a cryptographic paradigm for analyzing the security of ideal objects. Despite its strength, indifferentiability is not known to offer security against pre-processing attacks. We propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account.
arXiv Detail & Related papers (2024-10-22T00:41:47Z)
A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover. We establish a quantum soundness result for all compiled two-player nonlocal games.
arXiv Detail & Related papers (2024-08-13T08:11:56Z)
Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification [2.298932494750101]
Kalai et al. defined a black-box cryptographic compilation procedure that applies to any nonlocal game. We make progress towards a full understanding of the quantum value of the single-prover protocols. We give a single-prover cryptographically sound classical verification protocol for BQP, and we prove its soundness using our CHSH rigidity analysis.
arXiv Detail & Related papers (2023-03-02T19:20:59Z)
Revocable Cryptography from Learning with Errors [61.470151825577034]
We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
arXiv Detail & Related papers (2023-02-28T18:58:11Z)
Obfuscation of Pseudo-Deterministic Quantum Circuits [14.026980555435841]
We show how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model. Our obfuscator outputs a quantum state $ketwidetildeQ$ repeatedly on arbitrary inputs.
arXiv Detail & Related papers (2023-02-22T01:14:20Z)
From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments [8.834776091974218]
We show the first public key encryption scheme from cryptographic emphnon-abelian group actions. We construct the scheme through a new abstraction called swap-trapdoor function pairs. We give a simple and efficient compiler that converts the flavor of quantum bit commitments.
arXiv Detail & Related papers (2022-10-12T07:40:05Z)
Succinct Classical Verification of Quantum Computation [30.91621630752802]
We construct a classically succinct interactive argument for quantum computation (BQP) Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning Errors (LWE)
arXiv Detail & Related papers (2022-06-29T22:19:12Z)
Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z)
Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
arXiv Detail & Related papers (2020-10-15T17:55:31Z)
Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
arXiv Detail & Related papers (2020-09-29T08:41:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.