Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement

• URL: http://arxiv.org/abs/2410.12121v1
• Date: Tue, 15 Oct 2024 23:44:29 GMT
• Title: Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement
• Authors: Daniel Collins, Yuval Efron, Jovan Komatovic,
• Abstract summary: 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)
• Score: 1.77513002450736
• License:
• Abstract: It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of $t<n/2$ corruptions, bypassing the setup-free $t<n/3$ barrier. Alas, the overwhelming majority of protocols in the literature have the caveat that their security crucially hinges on the security of the cryptography and setup, to the point where if the cryptography is broken, even a single corrupted party can violate the security of the protocol. Thus these protocols provide higher corruption resilience ($n/2$ instead of $n/3$) for the price of increased assumptions. Is this trade-off necessary? We further the study of crypto-agnostic Byzantine agreement among $n$ parties that answers this question in the negative. Specifically, let $t_s$ and $t_i$ denote two parameters such that (1) $2t_i + t_s < n$, and (2) $t_i \leq t_s < n/2$. Crypto-agnostic Byzantine agreement ensures agreement among honest parties if (1) the adversary is computationally bounded and corrupts up to $t_s$ parties, or (2) the adversary is computationally unbounded and corrupts up to $t_i$ parties, and is moreover given all secrets of all parties established during the setup. We propose a compiler that transforms any pair of resilience-optimal Byzantine agreement protocols in the authenticated and information-theoretic setting into one that is crypto-agnostic. Our compiler has several attractive qualities, including using only $O(\lambda n^2)$ bits over the two underlying Byzantine agreement protocols, and preserving round and communication complexity in the authenticated setting. In particular, 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). We therefore provide fallback security for authenticated Byzantine agreement for free for $t_i \leq n/4$.

Related papers

• Towards Unconditional Uncloneable Encryption [1.18749525824656]
  Uncloneable encryption is a cryptographic primitive which encrypts a classical message into a quantum ciphertext. We show that the adversary's success probability in the related security game converges quadratically as $1/2+1/ (2sqrtK)$, where $K$ represents the number of keys and $1/2$ is trivially achievable.
  arXiv  Detail & Related papers  (2024-10-30T14:40:06Z)
• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  The threshold secret sharing scheme allows the dealer to distribute the share to every participant that the secret is correctly recovered from a certain amount of shares. We propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $ell$-bit secret over a ring, with correctness and perfect security.
  arXiv  Detail & Related papers  (2024-02-02T05:04:01Z)
• 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)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• Beating the fault-tolerance bound and security loopholes for Byzantine agreement with a quantum solution [12.059343107638188]
  We propose a Byzantine agreement framework with unconditional security to break the $1/3$ fault-tolerance bound. Our work strictly obeys two Byzantine conditions and can be extended to any number of players without requirements for multiparticle entanglement. Our work indicates the quantum advantage in terms of consensus problems and suggests an important avenue for quantum blockchain and quantum consensus networks.
  arXiv  Detail & Related papers  (2022-06-18T09:46:58Z)
• 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)
• An Efficient Simulation of Quantum Secret Sharing [7.195824023358536]
  We propose a secure $d$-level $QSS$ protocol for sharing a secret with efficient simulation. It does not disclose any information about the secret to players. Its security analysis shows that the intercept-resend, intercept, entangle-measure, forgery, collision and collusion attacks are not possible in this protocol.
  arXiv  Detail & Related papers  (2021-03-20T16:42:02Z)
• 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)
• 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)

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.