Statistically Reliable and Secure Message Transmission in Directed Networks.
Arpita Patra, Ashish Choudhury, Chandrasekharan Pandu Rangan · IACR Cryptology ePrint Archive · 2008
Consider the following problem: a sender S and a receiver R are part of a directed synchronous network and connected through intermediate nodes. Specifically, there exists n node disjoint paths, also called as wires, which are directed from S to R and u wires, which are directed from R to S. Moreover, the wires from S to R are disjoint from the wires directed from R to S. There exists a centralized, static adversary A static , who has unbounded computing power and who can control at most t wires between S and R in Byzantine fashion. S has a message m S , which we wants to send to R. The challenge is to design a protocol, such that after interacting in phases 5 as per the protocol, R should correctly output m R = m S , except with error probability 2 −(κ) , where κ is the error parameter. This problem is called as statistically reliable message transmission (SRMT). The problem of statistically secure message transmission (SSMT) has an additional requirement that at the end of the protocol, m S should be information theoretically secure from A static . Desmedt et.al [14, 55] have given the necessary and sufficientcondition for the existence of SRMT and SSMT protocols in the above settings. They also presented an SSMT protocol, satisfying their characterization. The authors in [14, 55] claimed that their protocol is efficientand has polynomial computational and communication complexity. However, we show that it is not so. That is, we specify an adversary strategy, which may cause the protocol to have exponential computational and communication complexity 6 . We then present