A constant lower bound for any quantum protocol for secure function evaluation

• URL: http://arxiv.org/abs/2203.08268v1
• Date: Tue, 15 Mar 2022 21:40:48 GMT
• Title: A constant lower bound for any quantum protocol for secure function evaluation
• Authors: Sarah Osborn and Jamie Sikora
• Abstract summary: We show that perfect (or near perfect) security is impossible, even for quantum protocols. Constant lower bounds are of practical interest since they imply the impossibility to arbitrarily amplify the security of quantum protocols.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Secure function evaluation is a two-party cryptographic primitive where Bob computes a function of Alice's and his respective inputs, and both hope to keep their inputs private from the other party. It has been proven that perfect (or near perfect) security is impossible, even for quantum protocols. We generalize this no-go result by exhibiting a constant lower bound on the cheating probabilities for any quantum protocol for secure function evaluation, and present many applications from oblivious transfer to the millionaire's problem. Constant lower bounds are of practical interest since they imply the impossibility to arbitrarily amplify the security of quantum protocols by any means.

Related papers

• Incomplete quantum oblivious transfer with perfect one-sided security [0.0]
  We consider 1 out of 2 oblivious transfer, where a sender sends two bits of information to a receiver. We aim to find the lowest possible cheating probabilities. We show that non-interactive quantum protocols can outperform non-interactive classical protocols.
  arXiv  Detail & Related papers  (2024-09-26T06:35:36Z)
• Insecurity of Quantum Two-Party Computation with Applications to Cheat-Sensitive Protocols and Oblivious Transfer Reductions [0.0]
  We rigorously establish the impossibility of cheat-sensitive OT, where a dishonest party can cheat, but risks being detected. We provide entropic bounds on primitives needed for secure function evaluation. Our results hold in particular for transformations between a finite number of primitives and for any error.
  arXiv  Detail & Related papers  (2024-05-20T15:39:30Z)
• Probabilistic versions of Quantum Private Queries [0.7252027234425332]
  We define two non-deterministic versions of Quantum Private Queries, a protocol addressing the Symmetric-Private Information Retrieval problem. We show that the strongest variant of such scheme is formally equivalent to Quantum Bit Commitment, Quantum Oblivious Transfer and One-Sided Two Party Computation protocols.
  arXiv  Detail & Related papers  (2024-01-11T09:04:13Z)
• Quantum Universally Composable Oblivious Linear Evaluation [1.1060425537315088]
  We present a quantum protocol for oblivious linear evaluation that does not rely on quantum oblivious transfer. Our protocol uses high-dimensional quantum states to obliviously compute f (x) on Galois Fields of prime and prime-power dimension. We prove the protocols to have static security in the framework of quantum universal composability.
  arXiv  Detail & Related papers  (2022-04-29T15:55:35Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Geometry of Banach spaces: a new route towards Position Based Cryptography [65.51757376525798]
  We study Position Based Quantum Cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. We show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol.
  arXiv  Detail & Related papers  (2021-03-30T13:55:11Z)
• Delegating Multi-Party Quantum Computations vs. Dishonest Majority in Two Quantum Rounds [0.0]
  Multi-Party Quantum Computation (MPQC) has attracted a lot of attention as a potential killer-app for quantum networks. We present a composable protocol achieving blindness and verifiability even in the case of a single honest client.
  arXiv  Detail & Related papers  (2021-02-25T15:58:09Z)
• Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security [67.06003361150228]
  A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
  arXiv  Detail & Related papers  (2020-12-30T18:03:56Z)
• 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)
• Gaussian conversion protocols for cubic phase state generation [104.23865519192793]
  Universal quantum computing with continuous variables requires non-Gaussian resources. The cubic phase state is a non-Gaussian state whose experimental implementation has so far remained elusive. We introduce two protocols that allow for the conversion of a non-Gaussian state to a cubic phase state.
  arXiv  Detail & Related papers  (2020-07-07T09:19:49Z)

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.