A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip

• URL: http://arxiv.org/abs/2005.01565v3
• Date: Sun, 27 Oct 2024 07:52:14 GMT
• Title: A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip
• Authors: Iftach Haitner, Yonatan Karidi-Heller,
• Abstract summary: 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.
• Score: 2.469280630208887
• License:
• Abstract: In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems '83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS '85], the parties communicate over a broadcast channel, and a computationally unbounded adversary can choose which parties to corrupt along the protocol execution. Ben-Or and Linial proved that the $n$-party majority protocol is resilient to $O(\sqrt{n})$ corruptions (ignoring poly-logarithmic factors), and conjectured this is a tight upper bound for any $n$-party protocol (of any round complexity). Their conjecture was proved to be correct for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein, Linial and Saks [Combinatorica '89], symmetric protocols Goldwasser, Tauman Kalai and Park [ICALP '15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai, Komargodski and Raz [DISC '18]. Yet, the question of many-turn protocols was left entirely open. In this work, we close the above gap, proving that no $n$-party protocol (of any round complexity) is resilient to $\omega(\sqrt{n})$ (adaptive) corruptions.

Related papers

• 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)
• Tyche: Collateral-Free Coalition-Resistant Multiparty Lotteries with Arbitrary Payouts [23.27199615640474]
  We propose Tyche, a family of protocols for performing efficient multiparty lotteries. Our protocols are based on a commit-and-reveal approach, requiring only a collision-resistant hash function. We show that our protocols are secure, fair, and some preserve the participants' privacy.
  arXiv  Detail & Related papers  (2024-09-05T12:19:37Z)
• 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)
• 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)
• Communication Lower Bounds for Cryptographic Broadcast Protocols [7.233482131020069]
  Broadcast protocols enable a set of $n$ parties to agree on the input of a designated sender, even facing attacks by malicious parties. We show that any broadcast protocol within this setting can be attacked to force an arbitrary party to send messages to $k$ other parties.
  arXiv  Detail & Related papers  (2023-09-04T09:24:39Z)
• Compression for Qubit Clocks [55.38708484314286]
  We propose a compression protocol for $n$ identically prepared states of qubit clocks. The protocol faithfully encodes the states into $(1/2)log n$ qubits and $(1/2)log n$ classical bits.
  arXiv  Detail & Related papers  (2022-09-14T09:45:53Z)
• Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost [48.288452411283444]
  We study distributed contextual linear bandits with contexts, where $N$ agents act cooperatively to solve a linear bandit-optimization problem with $d$-dimensional features. We propose a distributed batch elimination version of the LinUCB algorithm, DisBE-LUCB, where the agents share information among each other through a central server. We prove that over $T$ rounds ($NT$ actions in total) the communication cost of DisBE-LUCB is only $tildemathcalO(dN)$ and its regret is at most $tildemathcalO
  arXiv  Detail & Related papers  (2022-05-26T05:56:23Z)
• 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)
• 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)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)
• Moniqua: Modulo Quantized Communication in Decentralized SGD [45.468216452357375]
  Moniqua is a technique that allows decentralized algorithms to use quantized communication. We show that Moniqua converges faster with respect to wall clock time than other quantized decentralized algorithms.
  arXiv  Detail & Related papers  (2020-02-26T20:58:57Z)

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.