Paper 2012/231

A General Construction for 1-round $\delta$-RMT and (0, $\delta$)-SMT

Reihaneh Safavi-Naini, Mohammed Ashraful Alam Tuhin, and Pengwei Wang


In Secure Message Transmission (SMT) problem, a sender $\cal S$ is connected to a receiver $\cal R$ through $N$ node disjoint bidirectional paths in the network, $t$ of which are controlled by an adversary with \textit{unlimited computational power}. $\cal{S}$ wants to send a message $m$ to $\cal{R}$ in a \textit{reliable} and \textit{private} way. It is proved that SMT is possible if and only if $N\ge2t+1$. In Reliable Message Transmission (RMT) problem, the network setting is the same and the goal is to provide reliability for communication, only. In this paper we focus on 1-round $\delta$-RMT and $(0,\delta)$-SMT where the chance of protocol failure (receiver cannot decode the sent message) is at most $\delta$, and in the case of SMT, privacy is perfect. 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. 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)
Contact author(s)
maatuhin @ ucalgary ca
2012-05-02: last of 2 revisions
2012-04-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Reihaneh Safavi-Naini and Mohammed Ashraful Alam Tuhin and Pengwei Wang},
      title = {A General Construction for 1-round $\delta$-RMT and (0, $\delta$)-SMT},
      howpublished = {Cryptology ePrint Archive, Paper 2012/231},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.