On minimal connectivity requirements for secure message transmission in directed networks
| Autor: | Chiranjeevi Vanarasa, Ravi Kishore, Srinathan Kannan |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Secure message transmission
Theoretical computer science Computer science 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Directed graph Characterization (mathematics) Topology 01 natural sciences Computer Science Applications Theoretical Computer Science 010201 computation theory & mathematics Signal Processing 0202 electrical engineering electronic engineering information engineering Communication source Protocol (object-oriented programming) Information Systems |
| Zdroj: | Information Processing Letters. 131:1-6 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2017.11.001 |
| Popis: | In a synchronous distributed network of n nodes, the goal of a Secure Message Transmission (SMT) protocol is to securely deliver the sender's message at the receiver's end in the presence of a computationally unbounded adversary that can partially control the network by corrupting some of its nodes (except the sender and the receiver). In a network modelled as a directed graph, to achieve unconditional security tolerating t b Byzantine faults, it is known that: (1) if all the paths are one-way connected from the sender to the receiver – called as forward channels – then 2 t b + 1 vertex-disjoint forward channels are necessary and sufficient (2) for 1 ≤ u ≤ t b , if there exist 2 t b + 1 − u vertex-disjoint forward channels then u vertex-disjoint paths from the receiver to the sender – known as feedback channels – are necessary and sufficient. Moreover, similar characterization exists for tolerating mixed faults – up to t f fail-stop faults in addition to t p passive faults. We notice that these results characterized the networks by studying the required number of extra vertex-disjoint feedback channels, conditioned on the existence of a certain number of forward channels. In this work, we give a generic characterization without attaching any such if condition. Specifically, we answer the following questions. In a given directed graph, that is abstracted as a collection of strong paths from S to R and R to S , under what conditions is SMT (im)possible tolerating: (1) up to t p passive faults?, (2) mixed faults – up to t f fail-stop faults in addition to t p passive faults?, and (3) up to t b Byzantine faults? Also, for each of these three problems, we explicitly show that there are networks in which SMT protocols exist whereas the existing results do not characterize such networks. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect