Lower Bounds for Quantum Secure Function Evaluation Reductions

• URL: http://arxiv.org/abs/2405.12121v4
• Date: Fri, 07 Feb 2025 17:53:02 GMT
• Title: Lower Bounds for Quantum Secure Function Evaluation Reductions
• Authors: Esther Hänggi, Severin Winkler,
• Abstract summary: One-sided output secure function evaluation is a cryptographic primitive where the two mutually distrustful players, Alice and Bob, both have a private input. We show that Bob can extract the function values for all his possible inputs from any implementation of a non-trivial function. We then consider protocols for secure function evaluation in a setup where the two players have access to trusted distributed randomness as a resource.
• Score: 0.0
• License:
• Abstract: One-sided output secure function evaluation is a cryptographic primitive where the two mutually distrustful players, Alice and Bob, both have a private input to a bivariate function. Bob obtains the value of the function for the given inputs, while Alice receives no output. It is known that this primitive cannot be securely implemented if the two players only have access to noiseless classical and quantum communication. In this work, we first show that Bob can extract the function values for all his possible inputs from any implementation of a non-trivial function that is correct and preserves the privacy of Bob's input. Our result holds in the non-asymptotic setting where the players have finite resources and the error is a constant. Then we consider protocols for secure function evaluation in a setup where the two players have access to trusted distributed randomness as a resource. Building upon the first result, we prove a bound on the efficiency of such cryptographic reductions for any non-trivial function in terms of the conditional entropies of the trusted randomness. From this result, we can derive lower bounds on the number of instances of different variants of OT needed to securely implement a given function.

Related papers

• Simplifying debiased inference via automatic differentiation and probabilistic programming [1.0152838128195467]
  'Dimple' takes as input computer code representing a parameter of interest and outputs an efficient estimator. We provide a proof-of-concept Python implementation and showcase through examples how it allows users to go from parameter specification to efficient estimation with just a few lines of code.
  arXiv  Detail & Related papers  (2024-05-14T14:56:54Z)
• OPAF: Optimized Secure Two-Party Computation Protocols for Nonlinear Activation Functions in Recurrent Neural Network [8.825150825838769]
  This paper pays special attention to the implementation of non-linear functions in semi-honest model with two-party settings. We propose a novel and efficient protocol for exponential function by using a divide-and-conquer strategy. Next, we take advantage of the symmetry of sigmoid and Tanh, and fine-tune the inputs to reduce the 2PC building blocks.
  arXiv  Detail & Related papers  (2024-03-01T02:49:40Z)
• Quantum advantage in a unified scenario and secure detection of resources [55.2480439325792]
  We consider a single task to study different approaches of having quantum advantage. We show that the optimal success probability in the overall process for a qubit communication might be higher than that for a cbit communication.
  arXiv  Detail & Related papers  (2023-09-22T23:06:20Z)
• Efficient uniform approximation using Random Vector Functional Link networks [0.0]
  A Random Vector Functional Link (RVFL) network is a depth-2 neural network with random inner nodes and biases. We show that an RVFL with ReLU activation can approximate the Lipschitz target function. Our method of proof is rooted in theory and harmonic analysis.
  arXiv  Detail & Related papers  (2023-06-30T09:25:03Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• A constant lower bound for any quantum protocol for secure function evaluation [0.0]
  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.
  arXiv  Detail & Related papers  (2022-03-15T21:40:48Z)
• Causal Inference Under Unmeasured Confounding With Negative Controls: A Minimax Learning Approach [84.29777236590674]
  We study the estimation of causal parameters when not all confounders are observed and instead negative controls are available. Recent work has shown how these can enable identification and efficient estimation via two so-called bridge functions.
  arXiv  Detail & Related papers  (2021-03-25T17:59:19Z)
• 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)
• Bayesian Optimization with Missing Inputs [53.476096769837724]
  We develop a new acquisition function based on the well-known Upper Confidence Bound (UCB) acquisition function. We conduct comprehensive experiments on both synthetic and real-world applications to show the usefulness of our method.
  arXiv  Detail & Related papers  (2020-06-19T03:56:27Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  We study the Safe Reinforcement Learning (SRL) problem using the Constrained Markov Decision Process (CMDP) formulation. We present an provably efficient online policy optimization algorithm for CMDP with safe exploration in the function approximation setting.
  arXiv  Detail & Related papers  (2020-03-01T17:47:03Z)

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.