Abstract
The problem of perfectly secure message transmission concerns two synchronized non-faulty processors sender (\({\mathcal{S}}\)) and receiver (\({\mathcal{R}}\)) that are connected by a synchronous network of n≥2t+1 noiseless 2-way communication channels. Their goal is to communicate privately and reliably, despite the presence of an adversary that may actively corrupt at most t of those channels. These properties should hold information theoretically and without error.
We propose an asymptotically optimal solution for this problem. The proposed protocol consists of two communication rounds, and a total of O(ℓn) bits are exchanged in order to transmit a message of ℓ bits. Earlier, at CRYPTO 2004, an equally optimal solution has been claimed. However, we give a counter-example showing that their result is not perfectly reliable. The flaw seems to be fundamental and non-trivial to repair. Our approach is overall entirely different, yet it also makes essential use of their neat communication efficient technique for reliably transmitting conflict graphs.
What distinguishes our approach from previous ones is a technique that allows to identify all actively corrupted channels, initially trading it off against privacy. A perfectly secure and reliable secret key is then distilled by privacy amplification.
Chapter PDF
Similar content being viewed by others
Keywords
References
Desmedt, Y.G., Wang, Y.: Perfectly Secure Message Transmission Revisited. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 502–517. Springer, Heidelberg (2002)
Dolev, D., Dwork, C., Waarts, O., Yung, M.: Perfectly Secure Message Transmission. JACM 40(1), 17–47 (1993)
Sayeed, H., Abu-Amara, H.: Efficient Perfectly Secure Message Transmission in Synchronous Networks. Information and Computation 126(1), 53–61 (1996)
Shamir, A.: How to Share a Secret. Communications of the ACM 22, 612–613 (1979)
Srinathan, S., Narayanan, A., Pandu Rangan, C.: Optimal Perfectly Secure Message Transmission. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 545–561. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Agarwal, S., Cramer, R., de Haan, R. (2006). Asymptotically Optimal Two-Round Perfectly Secure Message Transmission. In: Dwork, C. (eds) Advances in Cryptology - CRYPTO 2006. CRYPTO 2006. Lecture Notes in Computer Science, vol 4117. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11818175_24
Download citation
DOI: https://doi.org/10.1007/11818175_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37432-9
Online ISBN: 978-3-540-37433-6
eBook Packages: Computer ScienceComputer Science (R0)