Secret key-distribution over networks with node-based adversarial errors
Source: arXiv:2606.19305 · Published 2026-06-17 · By Reza Sayyari, Michael Langberg
TL;DR
This work addresses the problem of securely distributing multiple independent secret keys over network-coded communication networks in the presence of active node-based adversaries. Unlike prior studies focusing mostly on passive eavesdropping or edge-based adversaries, the authors consider a powerful adversary who can observe and/or corrupt a subset of nodes, injecting either additive or overwrite errors. They develop coding schemes for both single-source and multi-source network settings, achieving perfect secrecy and reliability simultaneously despite adversarial disruptions. Their main result for networks where every node is d-vertex connected from the source is a perfectly secure multiple key-cast scheme achieving key capacity of d - ℓ_o - ℓ_e - 2ℓ_oe under additive and overwrite error models, extending classical secure network coding results to node-based threats. They further relax connectivity assumptions allowing partially connected intermediate nodes and demonstrate that their methods generalize to secure multicast network coding and network secret sharing setups. In addition, they improve prior parallel-edge network schemes from weak to perfect secrecy by refining hash constructions. The analyses include rigorous capacity characterizations, coding constructions, and security proofs under strong adversarial models with full topology knowledge.
Key findings
- For single-source networks where every node is d-vertex connected from the source, the perfectly secure multiple key-cast capacity is d - ℓ_o - ℓ_e - 2ℓ_oe under additive jamming, and d - ℓ_o - 2ℓ_e - 2ℓ_oe under overwrite jamming.
- The proposed coding schemes achieve asymptotically vanishing decoding error and perfect secrecy simultaneously without relying on pre-shared keys.
- A refined polynomial hashing combined with a one-time pad converts prior weakly secure parallel-edge network schemes into perfectly secure ones, revealing zero mutual information leakage.
- Local error correction relying on MDS codes with minimum distance d_min = ℓ_e + ℓ_oe + 1 enables correction of up to ℓ_e + ℓ_oe corrupted edges per node.
- When intermediate nodes have partial connectivity, achievable key rates depend on the source vertex connectivity and additional structural network properties.
- The coding constructions scale to multi-source cases ensuring perfect secrecy even if all but one source node are observed by the adversary.
- The approach extends directly to network secret sharing, providing active security guarantees under the same adversarial model.
- Adversarial injection at a node can depend on observations at nodes not descending from it, strengthening prior causal adversary models.
Threat model
The adversary is computationally unbounded and controls disjoint sets of intermediate network nodes to observe up to ℓ_o nodes passively, inject additive or overwrite errors on up to ℓ_e nodes, and simultaneously observe and corrupt up to ℓ_oe nodes with full knowledge of the network topology and coding scheme. The adversary makes injection decisions causally based on all information observed at nodes not topologically downstream, but cannot corrupt source nodes directly or create non-topological injections. This models a powerful but constrained active node-based adversary.
Methodology — deep read
The authors model the network as a directed acyclic graph with unit-capacity edges, source nodes generating unlimited uniform random symbols, and terminal nodes organized into disjoint decoding sets for multiple keys. The adversary is computationally unbounded and controls disjoint sets of nodes to observe (ℓ_o), corrupt additively or overwrite (ℓ_e), or simultaneously observe and corrupt (ℓ_oe). The adversary knows the entire network topology, coding scheme, and can coordinate corruptions based on all available observations from nodes not topologically downstream. Transmission proceeds in topological order, where each node encodes outgoing edges as functions of the (possibly corrupted) incoming edges using local encoding functions.
Secure key-codes consist of local encoding and decoding functions that achieve perfect secrecy (zero mutual information leakage to adversary observing any node sets disjoint from terminal sets) and reliability (terminal decoding error ≤ ϵ). The key-rate is defined as the minimum per-blocklength entropy of any key recovered at terminals.
Central to the scheme is assigning Vandermonde vectors to each node to construct MDS codes for error detection and correction. Using a pre-distribution phase, the source securely sends random values and polynomial hashes to all nodes via a refined scheme extending [9]. These polynomial hashes ensure perfect secrecy unlike prior linear hash schemes. Corrupted transmissions are detected locally at each node by hash verification, converting corrupted symbols to erasures. The robust MDS codes with minimum distance d_min = ℓ_e + ℓ_oe + 1 enable correcting these erasures reliably.
Algorithm 1 implements multiple key-cast by the source generating symmetric random matrices representing keys, distributing hashes and random masks via secure transmission, and performing local error correction and MDS decoding at each node following topological order. Terminals output shared keys by extracting portions of decoded matrix products.
The scheme is analyzed under additive and overwrite jamming models, with capacity characterizations proved via reduction to equivalent parallel-edge networks. The model is extended to multi-source networks by applying the protocol independently and combining keys. Below full connectivity is relaxed by analyzing vertex connectivity from source to terminals and leveraging structural graph properties to adapt coding schemes.
Reliability and security proofs argue negligible error probabilities using large field sizes and blocklengths, with perfect secrecy ensured by independent random masks and polynomial hashes covering multiple stages. Decoding failure probabilities incorporate both adversarial corruptions and hash verification errors.
All proofs and technical lemmas are detailed in appendices. While some adversary actions consider the most powerful model allowed by topology causality, the schemes remain efficient and explicit. Code or implementation specifics are not provided, and the datasets are abstract network instances; results are theoretical and constructive.
An end-to-end example is outlined where the source generates random symmetric matrices representing keys, pre-distributes random masks and polynomial hashes securely to nodes in a d-vertex connected network, nodes receive corrupted or clean data from parents, verify and mark corrupted edges as erasures, apply MDS decoding on concatenated vectors, and terminals decode their assigned keys perfectly and securely even under worst-case active corruptions limited by ℓ_o, ℓ_e, and ℓ_oe parameters.
The methodology blends advances in network coding, polynomial hash constructions, combinatorial graph properties (vertex-connectivity), and error correction in adversarial settings to yield provable capacity-optimal perfectly secure multiple key-cast schemes.
Technical innovations
- Refined polynomial hashing with one-time pads transforms prior asymptotically secure parallel-edge schemes into perfectly secure ones without information leakage.
- Extension of secure multiple key-cast capacity results to active adversaries controlling nodes (not just edges) under additive and overwrite error models.
- Use of d-vertex connectivity and Vandermonde-based MDS codes to achieve combined error correction and perfect secrecy in node-based adversarial settings.
- Generalization of single-source key-cast schemes to multi-source settings ensuring perfect secrecy even if adversary observes all but one source node.
Baselines vs proposed
- Prior parallel-edge network scheme [9]: asymptotic weak/strong secrecy – refined scheme: perfect secrecy achieved with zero mutual information leakage.
- Capacity under additive jamming model: prior strong secrecy rate unknown vs proposed: key-capacity = d - ℓ_o - ℓ_e - 2ℓ_oe
- Capacity under overwrite jamming model: prior strong secrecy rate unknown vs proposed: key-capacity = d - ℓ_o - 2ℓ_e - 2ℓ_oe
Limitations
- The schemes assume large finite field size for negligible error probabilities; practical performance at small fields not analyzed.
- No experimental implementation or simulation results provided; results are theoretical and asymptotic in nature.
- The adversary model, while topologically causal, is strong and assumes full knowledge of network topology and coding protocols, potentially pessimistic for some applications.
- No direct handling of dynamic or time-varying network topologies or adversaries beyond the one-shot topological order model.
- The pre-distribution phase requires reliable secure transmission to all nodes, which may be challenging in some network deployments.
- Reproducibility is limited as no open-source code or explicit parameter choices (field size, blocklength) are given.
Open questions / follow-ons
- How does the scheme perform in practice with realistic finite field sizes and finite blocklengths?
- Can these coding and hashing methods be adapted for dynamic or time-varying network topologies?
- Is there a practical construction minimizing communication overhead from pre-distribution of hashes and random masks?
- How robust is the approach to partial adversary knowledge or weaker adversaries with limited topology awareness?
Why it matters for bot defense
This paper is highly relevant to bot-defense and CAPTCHA practitioners concerned with maintaining secure and reliable secret key distribution over potentially hostile distributed networks. The methods provide rigorous mechanisms to defend against powerful active node-based adversaries who can corrupt and observe subsets of nodes, a threat model relevant to sophisticated botnets or compromised infrastructure nodes that aim to disrupt CAPTCHA verification or secret sharing. The deployment of coding schemes achieving perfect secrecy and error correction could inspire designs of multi-party authentication protocols or distributed challenge-response systems robust to internal node manipulation. Additionally, the refinement of hashing into perfectly secure variants discourages information leakage during verification, a critical property for defending against subtle adaptive adversarial probing typical in automated bot attacks. Finally, understanding capacity bounds under node-based errors informs tradeoffs of redundancy and connectivity requirements when engineering networked CAPTCHA verification at scale.
Cite
@article{arxiv2606_19305,
title={ Secret key-distribution over networks with node-based adversarial errors },
author={ Reza Sayyari and Michael Langberg },
journal={arXiv preprint arXiv:2606.19305},
year={ 2026 },
url={https://arxiv.org/abs/2606.19305}
}