We propose a new approach to the construction of 1-round $\delta$-RMT and (0, $\delta$)-SMT for all connectivities $N \ge 2t+1$, using list decodable codes and message authentication codes. Our concrete constructions use folded Reed-Solomon codes and multireceiver message authentication codes. The protocols have optimal transmission rates and provide the highest reliability among all known comparable protocols. Important advantages of these constructions are, (i) they can be adapted to all connectivities, and (ii) have simple and direct security (privacy and reliability) proofs using properties of the underlying codes, and $\delta$ can be calculated from parameters of the underlying codes.
We discuss our results in relation to previous work in this area and propose directions for future research.
Category / Keywords: cryptographic protocols / Publication Info: This is a full version of the paper accepted for publication in the Proceedings of 10th International Conference on Applied Cryptography and Network Security (ACNS '12) Date: received 25 Apr 2012, last revised 2 May 2012 Contact author: maatuhin at ucalgary ca Available format(s): PDF | BibTeX Citation Version: 20120502:193415 (All versions of this report) Short URL: ia.cr/2012/231 Discussion forum: Show discussion | Start new discussion