Publications: Abstract

Simple and Efficient Single Round almost Perfectly Secure Message Transmission Tolerating Generalized Adversary.

Ashish Choudhury, Kaoru Kurosawa, Arpita Patra

 Patra et al. (IJACT '09) gave a necessary and sufficient condition for the possibility of {\it almost perfectly secure message transmission} protocols\footnote{Patra et al. \cite{PatraIJACTProbabilistic09} called this problem as {\it unconditionally secure message transmission} (USMT).} tolerating {\it general, non-threshold} ${\cal Q}^2$ adversary structure. However, their protocol requires {\it at least three} rounds and performs {\it exponential} (exponential in the size of the adversary structure) computation and communication. They have left it as an open problem to design efficient protocol for almost perfectly secure message transmission, tolerating ${\cal Q}^2$ adversary structure. In this paper, we show the first {\it single} round almost perfectly secure message transmission protocol tolerating ${\cal Q}^2$ adversary structure. The computation and communication complexities of the protocol are both {\it polynomial} in the size of underlying {\it linear secret sharing scheme} ({\sf LSSS}). This solves the open problem posed by Patra et al. When we restrict our general protocol to a {\it threshold adversary}, we obtain a single round, {\it communication optimal} almost secure message transmission protocol tolerating threshold adversary, which is much more {\it computationally efficient} and {\it relatively simpler} than the previous single round, communication optimal protocol of Srinathan et al. (PODC '08).