Skip to main content

Research Repository

Advanced Search

Closure Solvability for Network Coding and Secret Sharing

Gadouleau, Maximilien

Closure Solvability for Network Coding and Secret Sharing Thumbnail



Network coding is a new technique to transmit data through a network by letting the intermediate nodes combine the packets they receive. Given a network, the network coding solvability problem decides whether all the packets requested by the destinations can be transmitted. In this paper, we introduce a new approach to this problem. We define a closure operator on a digraph closely related to the network coding instance and we show that the constraints for network coding can all be expressed according to that closure operator. Thus, a solution for the network coding problem is equivalent to a so-called solution of the closure operator. We can then define the closure solvability problem in general, which surprisingly reduces to finding secret-sharing matroids when the closure operator is a matroid. Based on this reformulation, we can easily prove that any multiple unicast where each node receives at least as many arcs as there are sources solvable by linear functions. We also give an alternative proof that any nontrivial multiple unicast with two source-receiver pairs is always solvable over all sufficiently large alphabets. Based on singular properties of the closure operator, we are able to generalize the way in which networks can be split into two distinct parts; we also provide a new way of identifying and removing useless nodes in a network. We also introduce the concept of network sharing, where one solvable network can be used to accommodate another solvable network coding instance. Finally, the guessing graph approach to network coding solvability is generalized to any closure operator, which yields bounds on the amount of information that can be transmitted through a network.


Gadouleau, M. (2013). Closure Solvability for Network Coding and Secret Sharing. IEEE Transactions on Information Theory, 59(12), 7858-7869.

Journal Article Type Article
Acceptance Date Sep 11, 2013
Publication Date Dec 1, 2013
Deposit Date Jan 31, 2014
Publicly Available Date Oct 21, 2015
Journal IEEE Transactions on Information Theory
Print ISSN 0018-9448
Publisher Institute of Electrical and Electronics Engineers
Peer Reviewed Peer Reviewed
Volume 59
Issue 12
Pages 7858-7869
Keywords Closure operators, Guessing games, Matroids, Network coding, Secret sharing.


Accepted Journal Article (319 Kb)

Copyright Statement
© 2013 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

You might also like

Downloadable Citations