IEEE Transactions on Information Theory · 2011 · 20 citations · 27 references
EngineeringComputer ScienceComputer SystemsComputer SecurityDigital CommunicationInformation TheoryChannel CapacityChannel CodingError-correcting CodesMultiple Access TechniquesNetwork Information TheorySide-channel AttacksCapacity Region AnalysisCode CapacityCode ConstructionsComplexityMultiple-access ChannelsNetwork CapacityPolynomial Time ComplexitySecrecy Capacity
This work considers the multiple-access multicast error-correction scenario over a packetized network with <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">z</i> malicious edge adversaries. The network has min-cut <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</i> and packets of length <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</i> , and each sink demands all information from the set of sources <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</i> . The capacity region is characterized for both a “side-channel” model (where sources and sinks share some random bits that are secret from the adversary) and an “omniscient” adversarial model (where no limitations on the adversary's knowledge are assumed). In the “side-channel” adversarial model, the use of a secret channel allows higher rates to be achieved compared to the “omniscient” adversarial model, and a polynomial-complexity capacity-achieving code is provided. For the “omniscient” adversarial model, two capacity-achieving constructions are given: the first is based on random subspace code design and has complexity exponential in <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">lm</i> , while the second uses a novel multiple-field-extension technique and has O(lm <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">|S|</sup> ) complexity, which is polynomial in the network size. Our code constructions are “end-to-end” in that all nodes except the sources and sinks are oblivious to the adversaries and may simply implement predesigned linear network codes (random or otherwise). Also, the sources act independently without knowledge of the data from other sources.
27
Rudolf Ahlswede, Ning Cai, Shuo Li et al. · IEEE Transactions on Information Theory · 2000 · 7.9K citations
Shuo Li, Raymond W. Yeung, Ning Cai · IEEE Transactions on Information Theory · 2003 · 3.5K citations
A Random Linear Network Coding Approach to Multicast
T. Ho, Muriel Médard, R. Koetter et al. · IEEE Transactions on Information Theory · 2006 · 2.6K citations
An algebraic approach to network coding
R. Koetter, Muriel Médard · IEEE/ACM Transactions on Networking · 2003 · 2.4K citations
How Practical is Network Coding?
Mea Wang, Baochun Li · International Workshop on Quality of Service · 2006 · 1.4K citations