Pseudo-Entanglement is Necessary for EFI Pairs
- URL: http://arxiv.org/abs/2406.06881v1
- Date: Tue, 11 Jun 2024 01:44:16 GMT
- Title: Pseudo-Entanglement is Necessary for EFI Pairs
- Authors: Manuel Goulão, David Elkouss,
- Abstract summary: We consider a new quantum resource, pseudo-entanglement, and show that the existence of EFI pairs implies the existence of pseudo-entanglement.
Our result has important implications for the field of computational cryptography.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Regarding minimal assumptions, most of classical cryptography is known to depend on the existence of One-Way Functions (OWFs). However, recent evidence has shown that this is not the case when considering quantum resources. Besides the well known unconditional security of Quantum Key Distribution, it is now known that computational cryptography may be built on weaker primitives than OWFs, e.g., pseudo-random states [JLS18], one-way state generators [MY23], or EFI pairs of states [BCQ23]. We consider a new quantum resource, pseudo-entanglement, and show that the existence of EFI pairs, one of the current main candidates for the weakest computational assumption for cryptography (necessary for commitments, oblivious transfer, secure multi-party computation, computational zero-knowledge proofs), implies the existence of pseudo-entanglement, as defined by [ABF+24, ABV23] under some reasonable adaptations. We prove this by constructing a new family of pseudo-entangled quantum states given only EFI pairs. Our result has important implications for the field of computational cryptography. It shows that if pseudo-entanglement does not exist, then most of cryptography cannot exist either. Moreover, it establishes pseudo-entanglement as a new minimal assumption for most of computational cryptography, which may pave the way for the unification of other assumptions into a single primitive. Finally, pseudo-entanglement connects physical phenomena and efficient computation, thus, our result strengthens the connection between cryptography and the physical world.
Related papers
- Exponential Quantum One-Wayness and EFI Pairs [18.481934628015004]
In classical cryptography, one-way functions are widely considered to be the minimal computational assumption.
There are currently two major candidates for the minimal assumption: the search quantum generalization of one-way functions are one-way state generators (OWSG)
We show that IV-OWSGs are precisely equivalent to EFI pairs, with an exponential loss in the reduction.
arXiv Detail & Related papers (2024-04-21T15:55:00Z) - Public-Key Encryption with Quantum Keys [11.069434965621683]
We study the notion of quantum public-key encryption (qPKE) where keys are allowed to be quantum states.
We show that computational assumptions are necessary to build quantum public-key encryption.
arXiv Detail & Related papers (2023-06-13T11:32:28Z) - Encryption with Quantum Public Keys [1.7725414095035827]
We study the question of building quantum public-key encryption schemes from one-way functions and even weaker assumptions.
We propose three schemes for quantum public-key encryption from one-way functions, pseudorandom function-like states with proof of deletion and pseudorandom function-like states, respectively.
arXiv Detail & Related papers (2023-03-09T16:17:19Z) - 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) - One-Wayness in Quantum Cryptography [9.09597656634436]
We study properties of one-way state generators (OWSGs), which are a quantum analogue of one-way functions.
We show that Quantum digital signatures are equivalent to OWSGs.
We introduce an variant of OWSGs, which we call secretly-verifiable and statistically-invertible OWSGs.
arXiv Detail & Related papers (2022-10-07T08:21:21Z) - On the computational hardness needed for quantum cryptography [10.760579667794476]
We show that EFI pairs are necessary for a large class of quantum-cryptographic applications.
We construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty proofs.
This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting.
arXiv Detail & Related papers (2022-09-09T03:22:05Z) - A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography.
In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
arXiv Detail & Related papers (2022-05-07T03:15:15Z) - Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
We construct the first fully homomorphic encryption scheme with certified deletion.
Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
arXiv Detail & Related papers (2022-03-03T10:07:32Z) - Depth-efficient proofs of quantumness [77.34726150561087]
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover.
In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
arXiv Detail & Related papers (2021-07-05T17:45:41Z) - 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) - Efficient simulatability of continuous-variable circuits with large
Wigner negativity [62.997667081978825]
Wigner negativity is known to be a necessary resource for computational advantage in several quantum-computing architectures.
We identify vast families of circuits that display large, possibly unbounded, Wigner negativity, and yet are classically efficiently simulatable.
We derive our results by establishing a link between the simulatability of high-dimensional discrete-variable quantum circuits and bosonic codes.
arXiv Detail & Related papers (2020-05-25T11:03:42Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.