Authenticated adversarial routing

DOI10.1007/S00145-013-9157-6zbMATH Open1319.68015arXiv0808.0156OpenAlexW1755465830MaRDI QIDQ484328FDOQ484328

Authors: Yair Amir, Paul Bunn, Rafail Ostrovsky 

Publication date: 7 January 2015

Published in: Journal of Cryptology (Search for Journal in Brave)

Abstract: The aim of this paper is to demonstrate the feasibility of authenticated throughput-efficient routing in an unreliable and dynamically changing synchronous network in which the majority of malicious insiders try to destroy and alter messages or disrupt communication in any way. More specifically, in this paper we seek to answer the following question: Given a network in which the majority of nodes are controlled by a malicious adversary and whose topology is changing every round, is it possible to develop a protocol with polynomially-bounded memory per processor that guarantees throughput-efficient and correct end-to-end communication? We answer the question affirmatively for extremely general corruption patterns: we only request that the topology of the network and the corruption pattern of the adversary leaves at least one path each round connecting the sender and receiver through honest nodes (though this path may change at every round). Out construction works in the public-key setting and enjoys bounded memory per processor (that does not depend on the amount of traffic and is polynomial in the network size.) Our protocol achieves optimal transfer rate with negligible decoding error. We stress that our protocol assumes no knowledge of which nodes are corrupted nor which path is reliable at any round, and is also fully distributed with nodes making decisions locally, so that they need not know the topology of the network at any time.

Full work available at URL: https://arxiv.org/abs/0808.0156

Recommendations

• Authenticated Adversarial Routing
• Asynchronous throughput-optimal routing in malicious networks
• scientific article; zbMATH DE number 1775421
• scientific article; zbMATH DE number 7706041
• Adaptive packet routing for bursty adversarial traffic

zbMATH Keywords

communication complexityfault localizationnetwork routingend-to-end communicationerror-correctionmulti-party computation

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60) Reliability, testing and fault tolerance of networks and computer systems (68M15) Network design and communication in computer systems (68M10) Distributed systems (68M14) Authentication, digital signatures and secret sharing (94A62) Network protocols (68M12)

Cites Work

• Foundations of Cryptography
• On-line/off-line digital signatures
• Title not available (Why is that?)
• Coding for interactive communication
• Log-Space Polynomial End-to-End Communication
• Adaptive packet routing for bursty adversarial traffic
• Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks
• A coding theorem for distributed computation
• Slide—The Key to Polynomial End-to-End Communication
• Asynchronous throughput-optimal routing in malicious networks
• The slide mechanism with applications in dynamic networks (extended abstract)
• Protocols and Lower Bounds for Failure Localization in the Internet
• Theory of Cryptography

Cited In (4)

• Protocols and Lower Bounds for Failure Localization in the Internet
• Interception in distance-vector routing networks
• Asynchronous throughput-optimal routing in malicious networks
• Authenticated Adversarial Routing

This page was built for publication: Authenticated adversarial routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q484328)