arxiv: 2605.12209 · v1 · submitted 2026-05-12 · 💻 cs.IT · math.IT

Recognition: 2 theorem links

· Lean Theorem

Secure (Multiple) Key-Cast over Networks: Multiple Eavesdropping Nodes

Michael Langberg, Reza Sayyari

Pith reviewed 2026-05-13 03:57 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords secure key-castnetwork codingvertex-connectivitynode eavesdroppersinformation-theoretic securitymultiple keysnoiseless networksmulti-source

0 comments

The pith

In d-vertex-connected networks, secure key-cast achieves rate d-ℓ against ℓ node eavesdroppers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that when every node in a noiseless network is d-vertex-connected from the source, a secure rate of d-ℓ is achievable for generating and sharing distinct keys among terminals while an eavesdropper seeing up to ℓ nodes learns nothing. This rate is shown to be optimal by constructing specific d-vertex-connected networks whose capacity cannot exceed d-ℓ. The results extend to networks with some partially-connected nodes, where rates depend on minimum connectivity, and to multi-source cases where the eavesdropper can observe all sources except one. A sympathetic reader cares because the work gives exact, connectivity-based limits on how much secret key material can be distributed securely using network coding, without needing stronger assumptions on the network topology.

Core claim

For single-source networks where every node is d-vertex-connected from the source, a secure key rate of d-ℓ is achievable for all such networks and optimal, as shown by exhibiting d-vertex-connected networks with capacity at most d-ℓ. Secure multiple key-cast remains achievable with partially-connected nodes at rates depending on minimum vertex-connectivity and other properties. These results generalize to the multi-source setting, where secure key-cast is possible even if the eavesdropper observes all but one source node.

What carries the argument

d-vertex-connectivity from the source to all nodes, used in network coding schemes that ensure generated keys remain independent of any set of ℓ observed nodes.

If this is right

Secure key-cast capacity equals d-ℓ exactly in fully d-vertex-connected networks.
The same rate remains achievable when some nodes have lower connectivity, limited by the minimum connectivity value.
In multi-source networks the eavesdropper can observe all but one source without reducing the achievable rate below d-ℓ.
The capacity bound is tight because matching upper bounds are exhibited for certain networks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Network designers could prioritize adding vertex-disjoint paths to raise secure key rates directly.
The results suggest testing whether similar connectivity-based bounds hold when a few nodes are noisy rather than noiseless.
Small explicit graphs with known d and ℓ could be simulated to check if the derived coding schemes reach the predicted rates.
The multi-source extension hints at applicability to distributed systems where not all sources need to be fully trusted.

Load-bearing premise

The networks are noiseless and the eavesdropper is limited to observing up to ℓ nodes while the stated vertex-connectivity conditions hold exactly.

What would settle it

A concrete d-vertex-connected network in which the achievable secure key-cast rate is strictly higher than d-ℓ, or one of the paper's exhibited networks where capacity exceeds d-ℓ, would disprove the optimality claim.

Figures

Figures reproduced from arXiv: 2605.12209 by Michael Langberg, Reza Sayyari.

**Figure 2.** Figure 2: Example network with a source, a terminal, and [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

read the original abstract

We study the secure multiple key-cast problem over noiseless networks under node-based eavesdroppers, where one or more source nodes participate in the generation of distinct secret keys to be shared among designated terminal subsets, while an eavesdropper observing up to $\ell$ nodes, including possibly source nodes, obtains no information about the keys. For the single-source setting, we first consider networks in which every node is $d$-vertex connected from the source. We show that a secure key rate of $d-\ell$ is achievable for all such networks. We further show that this rate is optimal by exhibiting $d$-vertex-connected networks whose secure key-cast capacity is at most $d-\ell$. We next study networks in which only the terminal nodes are $d$-vertex connected from the source, while other network nodes may not satisfy this connectivity condition and may be partially-connected. We show that secure multiple key-cast remains achievable in the presence of such partially-connected nodes, and derive coding schemes whose rate depends on the minimum network vertex-connectivity from the source and certain additional network properties. Finally, we generalize these results, for both $d$-vertex-connected networks and networks containing partially-connected nodes, to the multi-source setting; showing that secure multiple key-cast remains achievable even when the eavesdropper may observe all but one of the source nodes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows a secure key rate of d-ℓ is achievable and tight for single-source key-cast in d-vertex-connected networks against ℓ node eavesdroppers, with workable extensions to partial connectivity and multi-source settings.

read the letter

The central result is that d-vertex-connected networks from the source support a secure key rate of d-ℓ against an eavesdropper who sees up to ℓ nodes. The authors prove this rate is achievable with random linear network coding and show it is optimal by constructing example networks where the capacity cannot exceed d-ℓ. They also treat the case of multiple distinct keys going to different terminal subsets, which is the main extension beyond single-key work.

Referee Report

0 major / 3 minor

Summary. The paper studies the secure multiple key-cast problem over noiseless networks with node eavesdroppers who observe up to ℓ nodes (including sources). For single-source d-vertex-connected networks, it claims a secure key rate of d-ℓ is achievable for all such networks and optimal, shown via specific d-vertex-connected networks with capacity at most d-ℓ. It extends to networks where only terminals are d-vertex-connected (others may be partial), with achievable rates depending on minimum vertex-connectivity and additional properties. Results are generalized to multi-source settings, remaining achievable even if the eavesdropper observes all but one source.

Significance. If the results hold, this work provides tight achievability and converse bounds for secure key distribution under node eavesdropping, extending secure network coding literature via standard cut-set arguments for the converse and random linear network coding with injected randomness for achievability. The multi-source generalization and handling of partial connectivity are notable contributions, with the modeling assumptions (noiseless links, Menger-based vertex-connectivity) stated explicitly and applied consistently.

minor comments (3)

[Abstract] The abstract states that rates 'depend on the minimum network vertex-connectivity from the source and certain additional network properties' but does not define or exemplify these properties, which reduces clarity for readers unfamiliar with the model.
[Single-source d-vertex-connected networks section] In the optimality argument for d-vertex-connected networks, the exhibited examples achieving capacity at most d-ℓ are useful, but a brief discussion of how representative they are of general networks would strengthen the presentation without altering the claim.
[Model section] Notation for the secure key rate (e.g., how it is normalized or defined in terms of keys to multiple terminals) could be introduced more explicitly in the model section to avoid ambiguity when generalizing to multiple keys.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation for minor revision. The referee's summary accurately captures the key contributions of the paper on secure multiple key-cast with node eavesdroppers.

Circularity Check

0 steps flagged

No significant circularity; derivation uses standard cut-set bounds and network coding

full rationale

The paper's central claims rest on explicit modeling of noiseless networks with node eavesdroppers, vertex-connectivity via Menger's theorem, cut-set arguments for the converse (showing capacity at most d-ℓ in specific d-vertex-connected networks), and achievability via random linear network coding with injected randomness. These steps are independent of self-citations or internal redefinitions; the rate d-ℓ emerges directly from connectivity minus eavesdropper observations without fitting parameters to the target result or smuggling ansatzes. No load-bearing self-citation chains or self-definitional reductions appear. The multi-source and partial-connectivity extensions follow similarly from the same primitives. This is a standard, self-contained information-theoretic argument.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Review is abstract-only so ledger entries are limited to explicitly stated modeling assumptions; no free parameters or invented entities are mentioned.

axioms (2)

domain assumption The network is noiseless.
Explicitly stated in the abstract as the setting for the key-cast problem.
domain assumption Eavesdropper observes up to ℓ nodes including possibly sources.
Core modeling choice for the security constraint.

pith-pipeline@v0.9.0 · 5539 in / 1229 out tokens · 92246 ms · 2026-05-13T03:57:16.656277+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
Lemma 3.1 … K = U^T M U … block form with G uniform over S_{d-ℓ}
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear
Theorem 1 … key rate d-ℓ … Vandermonde vectors v_i … M v_Ti

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

[1]

Network coding multicast key- capacity

Michael Langberg and Michelle Effros. Network coding multicast key- capacity. InIEEE Information Theory Workshop (ITW), pages 422–427, 2022

work page 2022
[2]

Key-cast over networks.IEEE Transactions on Information Theory, pages 1–1, 2025

Michael Langberg and Michelle Effros. Key-cast over networks.IEEE Transactions on Information Theory, pages 1–1, 2025

work page 2025
[3]

Characterizing positive-rate key- cast (and multicast network coding) with eavesdropping nodes.Available on arXiv.com, arXiv:2407.01703, 2024

Michael Langberg and Michelle Effros. Characterizing positive-rate key- cast (and multicast network coding) with eavesdropping nodes.Available on arXiv.com, arXiv:2407.01703, 2024

work page arXiv 2024
[4]

Shared randomness in arbitrarily varying channels

Sagnik Bhattacharya, Amitalok J Budkuley, and Sidharth Jaggi. Shared randomness in arbitrarily varying channels. InIEEE International Symposium on Information Theory (ISIT), pages 627–631, 2019

work page 2019
[5]

Geetha, Mauro Conti, and William J Buchanan

Rahul Saha, Gulshan Kumar, G. Geetha, Mauro Conti, and William J Buchanan. Application of randomness for security and privacy in multi-party computation.IEEE Transactions on Dependable and Secure Computing, 21(6):5694–5705, 2024

work page 2024
[6]

Differentially private secure multi-party computation for federated learning in financial applications

David Byrd and Antigoni Polychroniadou. Differentially private secure multi-party computation for federated learning in financial applications. InProceedings of the first ACM International Conference on AI in finance, pages 1–9, 2020

work page 2020
[7]

Practical secure aggregation for privacy-preserving machine learning

Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy-preserving machine learning. Inproceedings of the ACM SIGSAC Conference on Computer and Communications Security, pages 1175–1191, 2017

work page 2017
[8]

Net- work information flow.IEEE Transactions on Information Theory, 46(4):1204–1216, 2000

Rudolf Ahlswede, Ning Cai, S-YR Li, and Raymond W Yeung. Net- work information flow.IEEE Transactions on Information Theory, 46(4):1204–1216, 2000

work page 2000
[9]

Linear network coding

S-YR Li, Raymond W Yeung, and Ning Cai. Linear network coding. IEEE Transactions on Information Theory, 49(2):371–381, 2003

work page 2003
[10]

Information- theoretically secure regenerating codes for distributed storage

Nihar B Shah, KV Rashmi, and P Vijay Kumar. Information- theoretically secure regenerating codes for distributed storage. InIEEE Global Telecommunications Conference-GLOBECOM, pages 1–5, 2011

work page 2011
[11]

U.M. Maurer. Secret key agreement by public discussion from common information.IEEE Transactions on Information Theory, 39(3):733–742, 1993

work page 1993
[12]

Broadcast channels with confidential messages.IEEE Transactions on Information Theory, 24(3):339–348, 2003

Imre Csiszár and Janos Korner. Broadcast channels with confidential messages.IEEE Transactions on Information Theory, 24(3):339–348, 2003

work page 2003
[13]

Converses for secret key agree- ment and secure computing.IEEE Transactions on Information Theory, 61(9):4809–4827, 2015

Himanshu Tyagi and Shun Watanabe. Converses for secret key agree- ment and secure computing.IEEE Transactions on Information Theory, 61(9):4809–4827, 2015

work page 2015
[14]

Secure network coding

Ning Cai and Raymond W Yeung. Secure network coding. In Proceedings IEEE International Symposium on Information Theory, page 323, 2002

work page 2002
[15]

Secure network coding on a wiretap network.IEEE Transactions on Information Theory, 57(1):424–435, 2010

Ning Cai and Raymond W Yeung. Secure network coding on a wiretap network.IEEE Transactions on Information Theory, 57(1):424–435, 2010

work page 2010
[16]

On the capacity of secure network coding

Jon Feldman, Tal Malkin, Cliff Stein, and Rocco A Servedio. On the capacity of secure network coding. InProc. 42nd Annual Allerton Conference on Communication, Control, and Computing, pages 63–68, 2004

work page 2004
[17]

On secure network coding with nonuniform or restricted wiretap sets.IEEE Transactions on Information Theory, 59(1):166–176, 2012

Tao Cui, Tracey Ho, and Joerg Kliewer. On secure network coding with nonuniform or restricted wiretap sets.IEEE Transactions on Information Theory, 59(1):166–176, 2012

work page 2012
[18]

Single- Unicast Secure Network Coding and Network Error Correction are as Hard as Multiple-Unicast Network Coding.IEEE Transactions on Information Theory, 64(6):4496–4512, 2018

Wentao Huang, Tracey Ho, Michael Langberg, and Jörg Kliewer. Single- Unicast Secure Network Coding and Network Error Correction are as Hard as Multiple-Unicast Network Coding.IEEE Transactions on Information Theory, 64(6):4496–4512, 2018

work page 2018
[19]

Insuffi- ciency of linear coding in network information flow.IEEE Transactions on Information Theory, 51(8):2745–2759, 2005

Randall Dougherty, Christopher Freiling, and Kenneth Zeger. Insuffi- ciency of linear coding in network information flow.IEEE Transactions on Information Theory, 51(8):2745–2759, 2005

work page 2005
[20]

The two-unicast problem.IEEE Transactions on Infor- mation Theory, 64(5):3865–3882, 2016

Sudeep Kamath, Venkatachalam Anantharam, David Tse, and Chih- Chun Wang. The two-unicast problem.IEEE Transactions on Infor- mation Theory, 64(5):3865–3882, 2016

work page 2016
[21]

Random linear network coding: A free cipher? InIEEE International Symposium on Information Theory, pages 546–550, 2007

Luisa Lima, Muriel Médard, and Joao Barros. Random linear network coding: A free cipher? InIEEE International Symposium on Information Theory, pages 546–550, 2007

work page 2007
[22]

Routing for security in networks with adversarial nodes

Pak Hou Che, Minghua Chen, Tracey Ho, Sidharth Jaggi, and Michael Langberg. Routing for security in networks with adversarial nodes. InInternational Symposium on Network Coding (NetCod), pages 1–6, 2013

work page 2013
[23]

A lightweight encryption scheme for network-coded mobile ad hoc networks.IEEE Transactions on Parallel and Distributed Systems, 25(9):2211–2221, 2013

Peng Zhang, Chuang Lin, Yixin Jiang, Yanfei Fan, and Xuemin Shen. A lightweight encryption scheme for network-coded mobile ad hoc networks.IEEE Transactions on Parallel and Distributed Systems, 25(9):2211–2221, 2013

work page 2013
[24]

On the op- timal linear network coding design for information theoretically secure unicast streaming.IEEE Transactions on Multimedia, 18(6):1149–1162, 2016

Jin Wang, Jianping Wang, Kejie Lu, Yi Qian, and Naijie Gu. On the op- timal linear network coding design for information theoretically secure unicast streaming.IEEE Transactions on Multimedia, 18(6):1149–1162, 2016

work page 2016
[25]

Network coding for distributed storage systems.IEEE Transactions on Information Theory, 56(9):4539– 4551, 2010

Alexandros G Dimakis, P Brighten Godfrey, Yunnan Wu, Martin J Wainwright, and Kannan Ramchandran. Network coding for distributed storage systems.IEEE Transactions on Information Theory, 56(9):4539– 4551, 2010

work page 2010
[26]

Distributed secret dissemination across a network.IEEE Journal of Selected Topics in Signal Processing, 9(7):1206–1216, 2015

Nihar B Shah, KV Rashmi, and Kannan Ramchandran. Distributed secret dissemination across a network.IEEE Journal of Selected Topics in Signal Processing, 9(7):1206–1216, 2015

work page 2015
[27]

How to share a secret.Communications of the ACM, 22(11):612–613, 1979

Adi Shamir. How to share a secret.Communications of the ACM, 22(11):612–613, 1979

work page 1979