Correction of adversarial errors in networks
- 1 January 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3 (21578095) , 1455-1459
- https://doi.org/10.1109/isit.2005.1523584
Abstract
We design codes to transmit information over a network, some subset of which is controlled by a malicious adversary. The computationally unbounded, hidden adversary knows the message to be transmitted, and can observe and change information over the part of the network being controlled. The network nodes do not share resources such as shared randomness or a private key. We first consider a unicast problem in a network with |epsiv parallel, unit-capacity, directed edges. The rate-region has two parts. If the adversary controls a fraction p < 0.5 of the |epsiv edges, the maximal throughput equals (1 - p) |epsiv|. We describe low-complexity codes that achieve this rate-region. We then extend these results to investigate more general multicast problems in directed, acyclic networksKeywords
This publication has 8 references indexed in Scilit:
- Polynomial Time Algorithms for Multicast Network Code ConstructionIEEE Transactions on Information Theory, 2005
- Byzantine modification detection in multicast networks using randomized network codingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- An algebraic approach to network codingIEEE/ACM Transactions on Networking, 2003
- Low complexity algebraic multicast network codesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On the Cost of Reconstructing a Secret, or VSS with Optimal Reconstruction PhasePublished by Springer Nature ,2001
- Codes for Interactive AuthenticationPublished by Springer Nature ,2001
- Network information flowIEEE Transactions on Information Theory, 2000
- Verifiable secret sharing and multiparty protocols with honest majorityPublished by Association for Computing Machinery (ACM) ,1989