CS Paper Radar

Rate 1/5 Non-Malleable Codes against Entangled Split-State Tampering

Naresh Goud Boddu

cs.CR quant-ph ·submitted 2026-09-30 12:14 UTC · v1

Abstract

We construct efficient information-theoretic non-malleable codes for classical messages that are secure against two noncommunicating local quantum tampering operations with arbitrary pre-shared entanglement. For every sufficiently small fixed $ξ>0$ and all sufficiently large first-share lengths $n$, the codes have rate at least $1/5-ξ$, perfect correctness, and error $2^{-n^{Ω(1)}}$. Security holds for every message, with a single message-independent simulator for each attack. This resolves the constant-rate question for worst-case classical messages in the entangled two-split-state model. Our construction builds on the permutation-based two-split construction of Batra, Boddu, and Jain, which achieves rate approaching $1/5$ for uniformly random messages. We retain their architecture but replace the uniform message input to the permutation with a prescribed message concatenated with fresh uniform padding. Our main contribution is a worst-case security reduction for this modification.

Closest papers

Nearest neighbours by meaning across the whole index.

From Symmetry to Secrecy: Covariant Classical--Quantum Wiretap Channels

cs.IT quant-ph ·2026-10-02 ·Masahito Hayashi, Farzin Salek
benchmark similarity 0.65
Abstract

For classical--quantum wiretap channels with a transitive covariant input action, both output ensembles admit a description as unitary group orbits of fixed seed states. We use this structure to construct finite-block preprocessing schemes whose private information is an entropy difference evaluated at two distributions related by group convolution. Applying the construction to product groups allows correlations across any fixed number of channel uses. We give a sufficient condition for the associated uniform-input bound to equal the single-use private information. Constant-composition channel codes and universal$_2$ hashing achieve the resulting rates, with trace-distance leakage controlled by sandwiched Rényi information. For uniform outer randomization, the representation structure reduces the comparison-state optimization to Eve's invariant states. For the hybrid binary channel considered by Tikku, Berta and Renes, numerical optimization at three and four uses gives rates above our numerical estimate of the optimized noisy-repetition benchmark wherever that estimate is positive on the tested grid. The improvement comes from noise distributions beyond the family of independent physical flips and a symmetric logical flip. We also prove nonadditivity at an explicit channel parameter using a two-use encoder, an analytic single-use converse, and certified entropy bounds. Finally, we relate the hybrid model to binary phase-shift keying with a fixed receiver measurement.

0.46

Quantum Leakage Resilience of Shamir Secret Sharing

cs.CR quant-ph ·2026-09-29 ·Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
similarity 0.64
Abstract · 38 pages, 2 tables

We initiate the study of quantum leakage resilience of unmodified Shamir secret sharing over prime fields. A well-studied leakage model for Shamir's secret sharing classically is single-bit local leakage from each share. We consider its quantum analogue where, for each party, a local leakage channel takes as input the party's share and outputs a leaked qubit. Without preshared entanglement, we show that the distinguishing advantage is $2^{-Ω(n)}$ when the threshold rate $t/n=τ$ exceeds $τ_\star\approx0.73339$ by a fixed positive margin. More generally, we allow disjoint entangled blocks of any fixed maximum size where there is no entanglement between different blocks or with the adversary, and each block emits at most a fixed number of qubits. Security holds when the threshold rate is high enough (sufficiently close to one). We then allow a specified set of devices to share entanglement with the adversary. We show that security holds even when a linear number of devices ($αn$ for small $α>0$) share entanglement with each other and with the adversary for a large enough threshold rate. As a complementary negative result, we also show that even classical single-bit leakage makes Shamir scheme insecure if we allow arbitrarily large entanglement between the leakage devices. A GHZ state shared by exactly $t$ leakage devices makes even classical one-bit leakage insecure, without any entanglement with the adversary. In this attack, each participating device emits only one classical bit, and their joint parity distinguishes any chosen pair of secrets with a constant advantage. Thus, for fixed threshold rates above $τ_\star$, the maximum number of devices that may share arbitrary entanglement with one another and with the adversary while preserving security is linear in $n$ up to constant factors, although the optimal support fraction remains open.

0.60

Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations

cs.CC quant-phcs.CR ·2026-10-16 ·Harumichi Nishimura
theory similarity 0.64
Abstract · 45 pages

Private simultaneous quantum messages (PSQM) provide a minimal model of noninteractive secure multiparty quantum computation, yet their communication complexity for concrete functions remains poorly understood. We show that familiar total functions already exhibit both genuine quantum advantages and strong structural limitations. For three-party equality on $n$-bit inputs, which determines whether the players' $n$-bit strings are identical, we construct an entanglement-assisted protocol with asymptotic communication $(1.633\ldots)n$ qubits, whereas every perfectly correct protocol without prior entanglement requires at least $3n$ qubits. For three-bit majority, one shared GHZ state and one transmitted qubit per player suffice for perfect correctness and perfect privacy, reducing the communication from the optimal classical cost of six bits to three qubits. Three-bit AND behaves differently. No perfectly correct and perfectly private protocol exists when the players share an arbitrary three-qubit state, apply arbitrary local unitary encodings, and transmit one qubit each. However, increasing the local dimension overcomes this obstruction: one shared three-qutrit GHZ state and one transmitted qutrit per player yield a one-shot protocol with total communication $3\log_2 3$. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every $k\geq 3$, we construct a perfectly correct and perfectly private one-shot protocol for $k$-bit AND using one qudit of dimension at most $k$ per player, and hence at most $k\log_2 k$ qubits in total.

0.11

Robust and leakage-resilient device-independent oblivious transfer in MiniQCrypt

cs.CR quant-ph ·2026-10-01 ·Rishabh Batra, Zhili Chen, Rahul Jain, YaoNan Zhang
theory similarity 0.62
Abstract · v3: Improved robustness and leakage tolerance, now allowing constant rates of noise and leakage

Assuming post-quantum one-way functions, we construct device-independent oblivious transfer and bit commitment that tolerate independent honest faults at a constant rate and adaptive, bidirectional quantum leakage between the laboratories at a constant rate. Honest parties use trusted classical computation to operate untrusted quantum devices, which may share arbitrary entanglement and perform joint measurements without assumptions of independence or identical distribution. Security is simulation-based against quantum polynomial-time adversaries and composes sequentially with efficient simulators. For security parameter $λ$ and a prescribed total leakage budget $\ell$, one complete one-bit oblivious transfer uses $Θ(\ell+\log^2λ)$ device coordinates in at most three single-use device windows, including preprocessing, and polynomial classical computation and communication. The leakage budget is shared across these windows. The commitment has efficient simulators against both parties and yields device-independent coin tossing with abort; each uses one window. Completeness of oblivious transfer gives device-independent secure computation with abort for every efficiently computable classical functionality on a fixed number of parties, against static corruption of any proper subset, provided each reached call to oblivious transfer satisfies the device and budget conditions. The construction combines short selectors with code-based choice masking, a global audit, and error correction across field symbols. The commitment extractor changes a classical code coset while leaving the device execution and its leakage unchanged. Sender security uses a global Fourier analysis and a selector-aware Magic Square repetition bound derived from the two-round threshold theorem of Kundu and Tan (2023).

0.25

An exponential strong converse for private communication over degradable quantum channels

cs.IT quant-ph ·2026-09-26 ·Mark M. Wilde
theory similarity 0.62
Abstract · 49 pages, 8 figures

We prove an exponential strong converse for the unassisted private capacity of every finite-dimensional degradable quantum channel. We use a single error criterion: the infidelity between the actual message-estimate-environment state and an ideal state consisting of uniformly distributed, perfectly correlated messages that are independent of the environment. At every rate strictly above the channel's maximum coherent information, the optimized fidelity to this ideal state decays exponentially in the number of channel uses. The same bound holds when the ideal environment state is fixed to the actual environment marginal. The proof applies to arbitrary mixed-state encoders and arbitrary collective decoders. Its main operator ingredient is an overlap bound for privacy tests: two receiver placements with a common subsystem of dimension $d_C$ have overlap at most $d_C/M$, where $M$ is the key size, independently of both shield dimensions. We combine this bound with the signed averaging construction presented in arXiv:2608.01308 and a single-filter reduction to symmetric states. A Gaussian filter replaces the common receiver subsystem by a system of controlled dimension from which the original correlations can be approximately recovered using quantum side information. The filter preserves exact exchange symmetry, and a uniform smooth-entropy estimate bounds its output dimension for arbitrary correlated channel inputs. We also obtain an exponential strong converse at zero for antidegradable channels under the same joint criterion and, consequently, for the private capacity of the quantum erasure channel throughout its parameter range.

0.32

From Claws to Conferences: Device-Independent Key Agreement Beyond Non-Signaling

cs.CR quant-ph ·2026-11-03 ·Suvradip Chakraborty
theory similarity 0.61
Abstract

Device-independent conference key agreement (DI-CKA) allows a group of users to establish a common secret key without trusting the internal operation of their quantum devices. Existing DI-CKA protocols derive their security from multipartite Bell tests and therefore require the device components not to communicate during each round. We present, to the best of our knowledge, the first DI-CKA protocol that removes this non-signaling assumption: all interfaces and their mutual communication are treated as one untrusted device, which only has to be quantum polynomial-time while the protocol runs. Assuming that the Learning With Errors (LWE) problem is hard for quantum algorithms with quantum advice during the execution, we prove finite-size security against coherent attacks, in which the device may keep quantum memory and correlate and adapt its behavior across rounds. For two parties the protocol is a computational DI-QKD protocol with an explicit finite-size proof against coherent attacks. Technically, we lift the claw state underlying the classical-verifier test of Brakerski et al.\ (FOCS 2018) to multipartite entanglement, obtaining a \emph{GHZ-correlated claw state}. %that is prepared with one coherent claw-free function evaluation and $N-1$ CNOT gates. We then introduce the \emph{collective adaptive hardcore bit}, a multiparty generalization of the adaptive hardcore bit of Brakerski et al.\ and show that it follows from the original property by a tight reduction. Combined with Jordan's lemma, an entropic uncertainty relation, and entropy accumulation, this certifies smooth min-entropy of the key against an external quantum adversary. Our protocol achieves \emph{everlasting security}: LWE needs to hold only during the execution, because the final key is statistically secure and its secrecy persists even if LWE is broken after the protocol ends.

0.29

On the Limits of Quantum Multiparty Simultaneous Communication

cs.CC quant-ph ·2026-09-09 ·Pedro Montealegre, Ivan Rapaport, Jorge Valenzuela
theory similarity 0.61
Abstract · 27 pages, 1 figure

We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement. We first introduce XOR Equality, a total Boolean function in which each of $k$ players receives an unrestricted string $x_j\in\{0,1\}^n$, and the referee must decide whether $x_1\oplus\cdots\oplus x_k=0^n$. For $k\ge8$ and worst-case error at most $1/3$, we prove quantum lower bounds of $Ω(\min\{n,k^2\})$ on total communication and $Ω(\min\{n/k,k\})$ on maximum message length. A classical public-coin protocol uses two bits per player with error at most $1/4$. For $n=k^2$ and worst-case error at most $1/3$, we prove that quantum protocols require maximum message length $Ω(\sqrt n)$ qubits, whereas two public-coin bits per player suffice. We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a $k$-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of $Ω(n^{1-1/k})$ on maximum message length, matched by a classical private-coin protocol. For any fixed error $\varepsilon\in(0,1/8)$, we also prove a bounded-error quantum lower bound of $Ω(n^{(k-1)/(k+1)})$ while we show that public-coin protocols solve the relation unambiguously with maximum message length $O(\log n)$, giving exponential separations in both regimes. The implicit constants are independent of $k$, and both quantum lower bounds become linear when $k\ge c\log n$ for any fixed $c>0$.

0.25

When lies look like noise: certifying untrusted entanglement swapping

cs.DC quant-ph ·2026-11-19 ·Maria Gragera Garces, Chris Heunen, Mahesh K. Marina
similarity 0.61
Abstract · 30 pages, 3 figure, 5 tables

Entanglement swapping lets quantum repeaters distribute entanglement over long distances, a prerequisite for the quantum internet. We study its security in a noisy network whose intermediate nodes perform the quantum operations faithfully but may misreport the classical outcome that end users rely on. We show that the ideal functionality of entanglement swapping cannot be realised, because it gives the adversary no influence over the delivered state, whereas a node that relabels its report does have such influence. Including honest noise in the ideal setting does not help unless it also concedes a bounded fraction of misreported pairs. We therefore propose a cut-and-choose protocol that tests a random subset of pairs to certify the rest. Since no test can distinguish a misreport from readout noise, the protocol certifies the error above a pre-agreed minimum noise level, which is the misreport rate under our threat model. This yields a quality-of-service guarantee, in which a failure witnesses that the node did not deliver as agreed. Unlike verification schemes that consume the state they certify, the untested pairs remain available for use, with a finite-size guarantee. Certifying a 1% misreport rate on 10^6 pairs costs 10^4 to 1.7x10^5 test pairs, for minimum noise levels ranging from 0 to 5%. The main cost is memory, since 1% requires holding 10^5 to 10^6 pairs at once, far beyond the capacity of today's quantum memories. Verifying and releasing in blocks ties the memory to the block size at the cost of a weaker rate: a (10^4)-qubit memory certifies 14% on 4.7x10^5 delivered pairs.

0.08