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 almost perfectly secure message transmission protocols tolerating general, non-threshold ${\mathcal Q}^2$ adversary structure. However, their protocol requires at least three rounds and performs 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 ${\mathcal Q}^2$ adversary structure.
In this paper, we show the first single round almost perfectly secure message transmission protocol tolerating ${\mathcal Q}^2$ adversary structure. The computation and communication complexities of the protocol are both polynomial in the size of underlying linear secret sharing scheme (LSSS). This solves the open problem posed by Patra et al.
When we restrict our general protocol to a threshold adversary, we obtain a single round, communication optimal almost secure message transmission protocol tolerating threshold adversary, which is much more computationally efficient and relatively simpler than the previous single round, communication optimal protocol of Srinathan et al. (PODC '08).
BibTeX Citation
@inproceedings{ChKuPa11a,
author = {Ashish Choudhury, Kaoru Kurosawa, Arpita Patra},
title = {Simple and Efficient Single Round almost Perfectly Secure Message Transmission Tolerating Generalized Adversary.},
editor = {Javier Lopez and Gene Tsudik},
booktitle = {ACNS},
pages = {292-308},
series = {Lecture Notes in Computer Science},
volume = {6715},
year = {2011},
}