Scalable Composition of Byzantine Agreements under Reorder Attacks

• URL: http://arxiv.org/abs/2609.09623v1
• Date: Wed, 09 Sep 2026 02:35:45 GMT
• Title: Scalable Composition of Byzantine Agreements under Reorder Attacks
• Abstract summary: We present the first adversary model that combines party corruption and channel attacks.<n>Based on this model, we establish new security thresholds for Byzantine agreement under parallel and concurrent compositions.<n>We prove the existence of secure protocols for unauthenticated Byzantine agreement under parallel and concurrent composition.
• Score: 5.485342264567332
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Byzantine agreement (BA) is a foundational building block in distributed systems, and the security analysis of BA protocols under multi-instance executions has attracted increasing attention. However, most existing adversary models focus solely on party corruption and neglect important threats posed by adversarial manipulations of communication channels in the network. Through channel attacks, messages can be reordered across multiple executions and lead to violations of the protocol's security guarantees, In this work, we present the first adversary model that combines party corruption and channel attacks. Based on this model, we establish new security thresholds for Byzantine agreement under parallel and concurrent compositions, supported by complementary impossibility and possibility results that match each other to form a tight bound. For the impossibility result, we show that even authenticated Byzantine agreement protocols cannot be secure under parallel composition when $n \leq 3t$ or $n \leq 2c + 2t + 1$, where $t$ and $c$ denote the number of corrupted parties and communication channels, respectively, and $n$ is the number of parties. For the possibility result, we prove the existence of secure protocols for unauthenticated Byzantine agreement under parallel and concurrent composition, when $n > \max\{3t, 2c+2t+1\}$. We first provide general black-box compilers that transform any single-instance secure BA protocol into one that is secure under parallel and concurrent executions without additional security assumptions. To optimize performance, we further design refined compilers using erasure-correcting codes. These refined versions significantly reduce communication overhead, particularly for long messages, where they achieve a constant multiplicative overhead compared with the original protocol, thus achieving the same asymptotic communication complexity.

Related papers

• TwinGate: Stateful Defense against Decompositional Jailbreaks in Untraceable Traffic via Asymmetric Contrastive Learning [60.68349524623048]
  Decompositional jailbreaks pose a critical threat to large language models.<n>We present TwinGate, a stateful dual-encoder defense framework.<n>We construct a comprehensive dataset of over 3.62 million instructions spanning 8,600 distinct malicious intents.
  arXiv  Detail & Related papers  (2026-04-30T13:44:01Z)
• Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions [89.52532304099522]
  Federated Learning (FL) enables clients to collaboratively train a shared model without centralizing their raw data, offering an inherent level of privacy.<n> gradients and model updates can still leak sensitive information, while malicious servers may mount adversarial attacks such as Byzantine manipulation.<n>These vulnerabilities highlight the need to address differential privacy (DP) and Byzantine robustness within a unified framework.<n>We propose Byz-Clip21-SGD2M, a new algorithm that integrates robust aggregation with double momentum and carefully designed clipping.
  arXiv  Detail & Related papers  (2026-03-24T17:39:09Z)
• Safe Low Bandwidth SPV: A Formal Treatment of Simplified Payment Verification Protocols and Security Bounds [0.0]
  We show that SPV is not only secure under bounded adversarial assumptions but strictly optimal for digital cash systems requiring scalable and verifiable transaction inclusion.<n>This document serves both as a blueprint for secure SPV implementation and a rebuttal of common misconceptions surrounding non-validating clients.
  arXiv  Detail & Related papers  (2025-07-01T13:44:48Z)
• Economic Security of Multiple Shared Security Protocols [5.335834405397044]
  We formalize the Multiple SSP Problem and analyze two architectures.<n>An isolated fragmented model called Model $mathbbM$ and a shared unified model called Model $mathbbS$ are studied.<n>Our results show that while Model $mathbbM$ offers deployment flexibility, it inherits lowest-cost attack vulnerabilities, whereas Model $mathbbS$ achieves tighter security guarantees through single validator sets and aggregated slashing logic.
  arXiv  Detail & Related papers  (2025-05-05T08:40:16Z)
• $\ extit{Agents Under Siege}$: Breaking Pragmatic Multi-Agent LLM Systems with Optimized Prompt Attacks [45.74758377276353]
  Multi-agent Large Language Model (LLM) systems create novel adversarial risks because their behavior depends on communication between agents and decentralized reasoning.<n>In this work, we innovatively focus on attacking pragmatic systems that have constrains such as limited token bandwidth, latency between message delivery, and defense mechanisms.<n>We design a $textitpermutation-invariant adversarial attack$ that optimize prompt distribution across latency and bandwidth-constraint network topologies to bypass distributed safety mechanisms.
  arXiv  Detail & Related papers  (2025-03-31T20:43:56Z)
• 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)
• Quantum Byzantine Agreement Against Full-information Adversary [7.31080473170185]
  It is feasible to construct a quantum agreement protocol that can effectively handle a full-information adversary. In the quantum full-information setting, participating players can exchange qubits, while the adversary possesses comprehensive and accurate visibility into the system's state and messages.
  arXiv  Detail & Related papers  (2024-09-03T08:44:36Z)
• Defending Large Language Models against Jailbreak Attacks via Semantic Smoothing [107.97160023681184]
  Aligned large language models (LLMs) are vulnerable to jailbreaking attacks. We propose SEMANTICSMOOTH, a smoothing-based defense that aggregates predictions of semantically transformed copies of a given input prompt.
  arXiv  Detail & Related papers  (2024-02-25T20:36:03Z)
• Coding-Based Hybrid Post-Quantum Cryptosystem for Non-Uniform Information [53.85237314348328]
  We introduce for non-uniform messages a novel hybrid universal network coding cryptosystem (NU-HUNCC) We show that NU-HUNCC is information-theoretic individually secured against an eavesdropper with access to any subset of the links.
  arXiv  Detail & Related papers  (2024-02-13T12:12:39Z)
• LookAhead: Preventing DeFi Attacks via Unveiling Adversarial Contracts [15.071155232677643]
  Decentralized Finance (DeFi) has resulted in financial losses exceeding 3 billion US dollars.<n>Current detection tools face significant challenges in identifying attack activities effectively.<n>We propose LookAhead, a new framework for detecting DeFi attacks via unveiling adversarial contracts.
  arXiv  Detail & Related papers  (2024-01-14T11:39:33Z)
• Expressive Losses for Verified Robustness via Convex Combinations [67.54357965665676]
  We study the relationship between the over-approximation coefficient and performance profiles across different expressive losses. We show that, while expressivity is essential, better approximations of the worst-case loss are not necessarily linked to superior robustness-accuracy trade-offs.
  arXiv  Detail & Related papers  (2023-05-23T12:20:29Z)
• Towards Variable-Length Textual Adversarial Attacks [68.27995111870712]
  It is non-trivial to conduct textual adversarial attacks on natural language processing tasks due to the discreteness of data. In this paper, we propose variable-length textual adversarial attacks(VL-Attack) Our method can achieve $33.18$ BLEU score on IWSLT14 German-English translation, achieving an improvement of $1.47$ over the baseline model.
  arXiv  Detail & Related papers  (2021-04-16T14:37:27Z)
• Dispelling Myths on Superposition Attacks: Formal Security Model and Attack Analyses [0.0]
  We propose the first computational security model considering superposition attacks for multiparty protocols. We show that our new security model is satisfiable by proving the security of the well-known One-Time-Pad protocol. We use this newly imparted knowledge to construct the first concrete protocol for Secure Two-Party Computation that is resistant to superposition attacks.
  arXiv  Detail & Related papers  (2020-07-01T18:00:54Z)

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.