Improving device-independent weak coin flipping protocols

• URL: http://arxiv.org/abs/2404.17079v1
• Date: Thu, 25 Apr 2024 23:17:37 GMT
• Title: Improving device-independent weak coin flipping protocols
• Authors: Atul Singh Arora, Jamie Sikora, Thomas Van Himbeeck,
• Abstract summary: Weak coin flipping is the cryptographic task where Alice and Bob remotely flip a coin but want opposite outcomes. Best protocol was devised over a decade ago by Silman, Chailloux, Aharon, Kerenidis, Pironio, and Massar. We show how one can test $n-1$ out of $n$ devices, and estimate the performance of the remaining device, for later use in the protocol.
• Score: 0.08192907805418585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Weak coin flipping is the cryptographic task where Alice and Bob remotely flip a coin but want opposite outcomes. This work studies this task in the device-independent regime where Alice and Bob neither trust each other, nor their quantum devices. The best protocol was devised over a decade ago by Silman, Chailloux, Aharon, Kerenidis, Pironio, and Massar with bias $\varepsilon \approx 0.33664$, where the bias is a commonly adopted security measure for coin flipping protocols. This work presents two techniques to lower the bias of such protocols, namely self-testing and abort-phobic compositions. We apply these techniques to the SCAKPM '11 protocol above and, assuming a continuity conjecture, lower the bias to $\varepsilon \approx 0.29104$. We believe that these techniques could be useful in the design of device-independent protocols for a variety of other tasks. Independently of weak coin flipping, en route to our results, we show how one can test $n-1$ out of $n$ devices, and estimate the performance of the remaining device, for later use in the protocol. The proof uses linear programming and, due to its generality, may find applications elsewhere.

Related papers

• IT$^3$: Idempotent Test-Time Training [95.78053599609044]
  This paper introduces Idempotent Test-Time Training (IT$3$), a novel approach to addressing the challenge of distribution shift. IT$3$ is based on the universal property of idempotence. We demonstrate the versatility of our approach across various tasks, including corrupted image classification.
  arXiv  Detail & Related papers  (2024-10-05T15:39:51Z)
• Perfect cheating is impossible for single-qubit position verification [0.9208007322096533]
  In quantum position verification, a prover certifies her location by performing a quantum computation and returning the results to a set of trusted verifiers. One of the very first protocols for quantum position verification was proposed in (Kent, Munro, Spiller 2011) We show that there is no perfect finite-dimensional cheating strategy for the original KMS measurement protocol.
  arXiv  Detail & Related papers  (2024-06-28T16:13:38Z)
• Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
  We study the problem of private vector mean estimation in the shuffle model of privacy where $n$ users each have a unit vector $v(i) inmathbbRd$. We propose a new multi-message protocol that achieves the optimal error using $tildemathcalOleft(min(nvarepsilon2,d)right)$ messages per user.
  arXiv  Detail & Related papers  (2024-04-16T00:56:36Z)
• Scalable 3D Registration via Truncated Entry-wise Absolute Residuals [65.04922801371363]
  A $3$D registration approach can process more than ten million ($107$) point pairs with over $99%$ random outliers. We call our method TEAR, as it involves minimizing an outlier-robust loss that computes Truncated Entry-wise Absolute Residuals.
  arXiv  Detail & Related papers  (2024-04-01T04:43:39Z)
• Lattice-Based Quantum Advantage from Rotated Measurements [2.0249250133493195]
  We show a new technique that uses the entire range of qubit measurements from the $XY$-plane. We construct a one-round protocol for blind remote preparation of an arbitrary state on the $XY$-plane up to a Pauli-$Z$ correction.
  arXiv  Detail & Related papers  (2022-10-18T20:18:15Z)
• Unconditionally secure relativistic multi-party biased coin flipping and die rolling [0.0]
  We introduce relativistic multi-party biased die rolling protocols, generalizing coin flipping to $M geq 2$ parties and to $N geq 2$ outcomes. Our results prove that the most general random secure multi-party computation, where all parties receive the output and there is no secret input by any party, can be implemented with unconditional security.
  arXiv  Detail & Related papers  (2021-07-19T23:28:32Z)
• Transferable Sparse Adversarial Attack [62.134905824604104]
  We introduce a generator architecture to alleviate the overfitting issue and thus efficiently craft transferable sparse adversarial examples. Our method achieves superior inference speed, 700$times$ faster than other optimization-based methods.
  arXiv  Detail & Related papers  (2021-05-31T06:44:58Z)
• 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)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)
• A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip [2.469280630208887]
  In a coin-flipping protocol, a computationally adversary can choose which parties to corrupt along the protocol execution. We prove that no $n$-party protocol (of any round complexity) is resilient to $omega(sqrtn)$ corruptions.
  arXiv  Detail & Related papers  (2020-05-04T15:29:11Z)
• Quantum weak coin flipping with a single photon [3.0969191504482247]
  Weak coin flipping is among the fundamental cryptographic primitives which ensure the security of modern communication networks. We present a practical protocol that requires a single photon and linear optics only. We show that it is fair and balanced even when threshold single-photon detectors are used, and reaches a bias as low as $epsilon=1/sqrt2-1/2approx 0.207$.
  arXiv  Detail & Related papers  (2020-02-20T20:30:16Z)

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.