CS Paper Radar

Communication with Adversarial Users: Byzantine Models in Multi-User Information Theory

Minglai Cai, Christian Deppe, Neha Sangwan

cs.IT ·submitted 2026-11-01 07:55 UTC · v1
survey

Abstract

We consider communication systems operating in environments where some participating users cannot be trusted. This motivates the study of Byzantine communication models, in which users may behave adversarially. In this survey, we provide a unified information-theoretic perspective on communication with adversarial users in multi-user settings. We review recent advances in Byzantine multiple access channels, including reliable communication, adversary identification, and distributed function computation. Furthermore, we discuss extensions to classical-quantum channels and highlight fundamental differences between classical and quantum models. Finally, we outline key open problems and future research directions at the intersection of communication, computation, and security.

Closest papers

Nearest neighbours by meaning across the whole index.

Quantum-State Oblivious Transfer over Quantum Erasure Channels

cs.IT quant-ph ·2026-10-03 ·Remi A. Chou
hot direction similarity 0.64
Abstract

We study quantum-state oblivious transfer over the quantum erasure channel under information-theoretic security guarantees. Specifically, Alice holds two quantum systems, Bob wishes to recover one of them, and the parties have access to independent channel uses and authenticated public classical communication, with no initial shared entanglement. We consider both honest-but-curious and malicious behavior. We establish finite-blocklength converse and achievability bounds, which match in the honest-but-curious setting. The malicious setting construction combines interactive hashing with tests of whether Bob received selected channel outputs, and distributes each input across several qubits so that erasures conceal an entire input from a dishonest receiver, even when the inputs are entangled with an external reference. We also derive fixed-error asymptotic expansions and show that both malicious and honest-but-curious settings have the same capacity.

0.24

Collusion-Secure Semi-Quantum Secret Sharing Scheme using a Quantum Third Party

cs.CR quant-ph ·2026-10-07 ·Santanu Majhi, Nirupam Basak
similarity 0.63
Abstract

The security of a secret sharing protocol is compromised if one or more dishonest participants can reconstruct the secret by deviating from the prescribed protocol, particularly when such malicious behavior remains undetected. Semi-Quantum Secret Sharing (SQSS) is a variant of secret sharing in which the participants possess only classical capabilities, such as preparing and measuring qubits in the computational ($Z$) basis, while a quantum-capable third party assists the dealer in generating and distributing quantum shares of a classical secret. The limited quantum capabilities of the participants in SQSS protocols may introduce vulnerabilities to collusion attacks, enabling an assisting quantum third party, in collaboration with a dishonest classical participant, to jointly recover the secret even without detection. In this work, we propose a novel SQSS protocol that eliminates this vulnerability and achieves information-theoretic security against collusion attacks. We further prove that the proposed protocol is secure against a broad class of external and internal attacks. Finally, a comparative analysis demonstrates that our construction advances existing SQSS protocols by simultaneously optimizing qubit efficiency, involves a classical dealer, and resilience against DCNA attacks using basic Bell states.

0.36

Secure Quantum Handshakes: Quantum Network Verification Via Simon's Algorithm

cs.NI quant-ph ·2026-10-08 ·Reece Robertson, Sejal Patil, Sebastian Deffner
similarity 0.63
Abstract

Quantum networking represents the future of secure communication, enabling fundamentally new capabilities through quantum information exchange. However, these networks require secure, high-fidelity quantum communication channels, and they require every participating node to be a genuine quantum device. Currently, there is no reliable method to verify whether clients entering a quantum network truly possess quantum computational capability and are connecting over robust channels. In this work, we introduce a client-validation protocol that functions as a proof-of-quantum-capability handshake. Our protocol secures a quantum network against classical spoofers, noisy quantum computers, and genuine quantum devices connecting with the network over noisy or insecure channels. We validate the efficacy of this protocol through numerical simulations under erasure, dephasing, and depolarizing noise models.

0.10

The Entire Quantum Computer on a Classical Leash

cs.CR quant-ph ·2026-10-22 ·Yael Tauman Kalai, Dakshita Khurana, Justin Raizes
similarity 0.62
Abstract

We show that a classical client with no quantum hardware can use a single untrusted and potentially malicious quantum server as if it were its own trusted quantum computer. Through the server, the client can privately choose and run quantum computations, prepare quantum states, and process quantum states supplied by other parties. It can also keep quantum memory on the server, hidden from the server itself, and use that memory in later computations so its quantum state persists across rounds of interaction. Together, these capabilities let a purely classical party act as a quantum party in a variety of interactive protocols. We expect this virtual quantum computer to be a broadly useful tool. As immediate applications, we resolve two known open problems: (1) classical verification of quantum sampling with negligible computational soundness error, and (2) remote state preparation of arbitrary efficiently preparable quantum states. Underlying all of these results is a general-purpose, maliciously secure two-party computation protocol between a classical client and a quantum server, which we construct assuming only the post-quantum hardness of learning with errors.

0.15

Fast Quantum Byzantine Agreement with Nearly Linear Quantum Communication

cs.DS ·2026-11-03 ·Jan Olkowski
theory similarity 0.60
Abstract

We consider synchronous binary Byzantine agreement among $n$ processes connected by authenticated point-to-point classical and quantum channels. The adversary is computationally unbounded, sees all classical information, adaptively corrupts up to $t\le(1/3-\varepsilon)n$ processes, and may suppress messages sent by a process in the round in which it is corrupted. We give a quantum algorithm that solves Byzantine agreement in this model with probability $1$. It uses $O(\log^4 n)$ rounds, $O(n\log^8 n)$ qubits, and $O(n^2\log^8 n)$ classical bits in expectation, with constants depending on $\varepsilon$. This reduces the quantum communication of the protocol of Ben-Or and Hassidim (STOC~2005), which achieves $O(1)$ expected rounds but whose Byzantine coin implementation requires $Ω(n^4\log n)$ qubits and classical bits. We also extend the quadratic message lower bound of Abraham et al.\ (PODC~2019) to quantum channels, obtaining an $Ω(t^2)$ lower bound on worst-case expected total communication. For $t=Θ(n)$, the communication and round complexity of our algorithm are therefore optimal up to polylogarithmic factors.

0.24

Characterizing Privacy Risks of Quantum Machine Learning with Emergent Quantum-Native Access

cs.LG quant-ph ·2026-09-04 ·Liou Tang, James Joshi, Ashish Kundu
similarity 0.60
Abstract

Quantum Machine Learning (QML) has shown rapid advances by utilizing quantum computing for machine learning tasks. Meanwhile, the privacy risks accompanying QML is also starting to be studied, which inherit privacy leakage channels from "classical" ML and also quantum-unique risks. Existing work on privacy-preserving QML largely focuses on a QML-as-a-service scenario, which generally assumes that the QML model owner provides only classical bit outputs to queries, while users (and adversaries) have only classical computing abilities. However, this view is increasingly challenged in a quantum-native world of quantum-capable users/adversaries, which may have access to both quantum computing abilities and access to quantum information output from service providers. In this paper, we aim to bridge this gap by examining membership inference attacks against QML models by demonstrating that increasing quantum access and quantum computing abilities provides provable theoretical privacy leakage and empirical adversarial gain. However, the probabilistic nature of QML introduces a gap between theoretical and empirical adversarial advantage. These results show that existing research on privacy leakage in QML models underestimates privacy leakage in emergent quantum-native access regimes, and we hope to establish a first step in examining potential privacy leakages for QML in the quantum-native world.

0.06

Finality Before Disclosure for Ledger Authenticators in the Quantum Random Oracle Model

cs.CR ·2026-08-19 ·Maja Lie, Benjamin Marsh
theoryhot direction similarity 0.60
Abstract

Public ledgers increasingly authorize state transitions using prior transactions, finalized state, timing, and ordering rather than only a public key, message, and portable signature. We introduce ledger authenticators and $\LAEUF$, an unforgeability experiment for reactive authorization protocols whose public judgment algorithm reads a finalized transcript. The model separates authentication safety from ledger liveness and captures canonical transition freshness, adaptive corruption, exposure before inclusion, censorship, and adversarial ordering. We identify two conditional resource boundaries. An authenticator satisfying our single event conditions yields a contextual one-time signature. Within our rebindable reveal class, safety requires computational post-disclosure non-admissibility. When precursor admission uses only public computation and ledger scheduling, this condition is enforced by closing the evidence eligible to use a disclosed credential. If newly constructed evidence remains admissible after disclosure, censoring the honest reveal gives a forgery. We then define a joint ledger and quantum random oracle execution model in which quantum state persists across classical finalization cuts and oracle evaluations made through the ledger are charged. For a closed finalized target set of size at most $K$, we prove the bound $3β_{\mathsf{cut}}^2+3c_{\mathsf{co}}KQ^2/2^λ+6\ell/2^λ$, where $β_{\mathsf{cut}}$ accounts for fresh openings already present at the cut. A commit, close, reveal authenticator instantiates the framework and obtains a multi-user lifetime QROM bound.

0.31

Zero Knowledge Proofs in Quantum Networks

cs.CR quant-phcs.SImath-ph ·2026-09-28 ·Tuhin Paul, Srijani Das, Manasi Patra, Ramij Rahaman
similarity 0.59
Abstract · 18 pages, 1 figure

Zero-knowledge proofs (ZKPs) enable the verification of a statement without revealing any information beyond its validity and constitute a fundamental primitive in cryptography and information theory. However, existing constructions rely on computational assumptions and are predominantly confined to bipartite settings, leaving their information-theoretic realization in bipartite or network scenarios largely unexplored. Here we develop a framework for zero-knowledge verification based on the indistinguishability of quantum states under operational constraints. Exploiting the fundamental limitations imposed by local operations, we show that a verifier is inherently restricted from extracting information about the underlying state while retaining the ability to verify correctness. We construct explicit protocols for multiparty quantum networks that achieve information-theoretic security, ensuring that no subset of collaborating parties can gain knowledge beyond the validity of the statement, independent of their joint computational power.

0.36