Cheat-Penalised Quantum Weak Coin-Flipping

• URL: http://arxiv.org/abs/2510.03218v1
• Date: Fri, 03 Oct 2025 17:54:00 GMT
• Title: Cheat-Penalised Quantum Weak Coin-Flipping
• Authors: Atul Singh Arora, Carl A. Miller, Mauro E. S. Morales, Jamie Sikora,
• Abstract summary: We study a variant called cheat-penalised weak coinflipping in which if a party gets caught cheating, they lose $Lambda$ points.<n>For the same space requirements, we demonstrate how one can choose between lowering how much a malicious party can bias the result.<n>Our results open up the possibility of having secure and practical quantum protocols for multiparty computation.
• Score: 0.968297475519304
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Coin-flipping is a fundamental task in two-party cryptography where two remote mistrustful parties wish to generate a shared uniformly random bit. While quantum protocols promising near-perfect security exist for weak coin-flipping -- when the parties want opposing outcomes -- it has been shown that they must be inefficient in terms of their round complexity, and it is an open question of how space efficient they can be. In this work, we consider a variant called cheat-penalised weak coin-flipping in which if a party gets caught cheating, they lose $\Lambda$ points (compared to $0$ in the standard definition). We find that already for a small cheating penalty, the landscape of coin-flipping changes dramatically. For example, with $\Lambda=0.01$, we exhibit a protocol where neither Alice nor Bob can bias the result in their favour beyond $1/2 + 10^{-8}$, which uses $24$ qubits and $10^{16}$ rounds of communication (provably $10^{7}$ times better than any weak coin-flipping protocol with matching security). For the same space requirements, we demonstrate how one can choose between lowering how much a malicious party can bias the result (down to $1/2 + 10^{-10}$) and reducing the rounds of communication (down to $25,180$), depending on what is preferred. To find these protocols, we make two technical contributions. First, we extend the point game-protocol correspondence introduced by Kitaev and Mochon, to incorporate: (i) approximate point games, (ii) the cheat-penalised setting, and (iii) round and space complexity. Second, we give the first (to the best of our knowledge) numerical algorithm for constructing (approximate) point games that correspond to high security and low complexity. Our results open up the possibility of having secure and practical quantum protocols for multiparty computation.

Related papers

• Pseudo-Equilibria, or: How to Stop Worrying About Crypto and Just Analyze the Game [48.93355782581436]
  We consider the problem of a game theorist analyzing a game that uses cryptographic protocols.<n>We propose a new solution concept: the pseudo-Nash equilibrium.
  arXiv  Detail & Related papers  (2025-06-27T10:21:28Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  We introduce a new toolkit for analyzing cloning games.<n>This framework allows us to analyze a new cloning game based on binary phase states.<n>We show that the binary phase variantally optimal bound offers quantitative insights into information scrambling in idealized models of black holes.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement [1.77513002450736]
  It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of $tn/2$ corruptions. We propose a compiler that transforms any pair of resilience-optimal Byzantine agreement protocols into one that is crypto-agnostic. Our results improve the state-of-the-art in bit complexity by at least two factors of $n$ and provide either early stopping (deterministic) or expected constant round complexity (randomized)
  arXiv  Detail & Related papers  (2024-10-15T23:44:29Z)
• Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? [4.465134753953128]
  We study the problem of reaching agreement in a synchronous distributed system by $n$ autonomous parties, when the communication links from/to faulty parties can omit messages. We design a randomized algorithm that works in $O(sqrtnlog2 n)$ rounds and sends $O(n2log3 n)$ communication bits. We prove that no MC algorithm can work in less than $Omega(fracn2maxR,nlog n)$ rounds if it uses less than $O(R)$ calls to
  arXiv  Detail & Related papers  (2024-05-08T02:17:10Z)
• Improving device-independent weak coin flipping protocols [0.08192907805418585]
  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.
  arXiv  Detail & Related papers  (2024-04-25T23:17:37Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• A Quantum Approach For Reducing Communications in Classical Secure Computations with Long Outputs [2.3465488122819123]
  We study the classical cryptographic problem that two parties would like to perform secure computations with long outputs.<n>In this work, we first design a quantum cryptographic protocol that achieves secure function sampling with approximate security.
  arXiv  Detail & Related papers  (2023-10-08T16:07:46Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  We study the linear contextual bandit problem in the presence of adversarial corruption. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
  arXiv  Detail & Related papers  (2021-10-25T02:53:24Z)
• 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)
• Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions [91.8283876874947]
  We consider a best arm identification (BAI) problem for Sequential bandits with adversarial corruptions in the fixed-budget setting of T steps. We design a novel randomized algorithm, Probabilistic Shrinking($u$) (PSS($u$)), which is agnostic to the amount of corruptions. We show that when the CPS is sufficiently large, no algorithm can achieve a BAI probability tending to $1$ as $Trightarrow infty$.
  arXiv  Detail & Related papers  (2020-10-15T17:34:26Z)
• 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.