Round-Optimal Perfectly Secret Message Transmission with Linear Communication Complexity

Consider an arbitrary network of

n

nodes, up to any

t

of which are eavesdropped on by an adversary. A sender

S

wishes to send a message

m

to a receiver

R

such that the adversary learns nothing about

m

(unless it eavesdrops on one among {

S

,

R

}). We prove a necessary and sufficient condition on the (synchronous) network for the existence of

r

-round protocols for perfect communication, for any given

r

 > 0. Our results/protocols are easily adapted to asynchronous networks too and are shown to be optimal in asynchronous “rounds”. Further, we show that round-optimality is achieved without trading-off the communication complexity; specifically, our protocols have an overall message complexity of

O

(

n

) elements of a finite field to perfectly transmit one field element. Interestingly, optimality (of protocols) also implies: (a) when the shortest path between

S

and

R

has Ω(

n

) nodes,

perfect secrecy is achieved for “free”

, because any (insecure routing) protocol would also take

O

(

n

) rounds and send

O

(

n

) messages (one message along each edge in the shortest path) for transmission and (b) it is well-known that (

t

 + 1) vertex disjoint paths from

S

to

R

are necessary for a protocol to exist; a consequent folklore is that the length of the (

t

 + 1)

th

ranked (disjoint shortest) path would dictate the round complexity of protocols; we show that the folklore is false; round-optimal protocols can be substantially faster than the aforementioned length.