Public Discussion Must Be Back and Forth in Secure Message Transmission - Information Security and Cryptology-ICISC 2010 - page 325

Public Discussion Must Be Back and Forth in Secure
Message Transmission

Takeshi Koshiba and Shinya Sawada

Division of Mathematics, Electronics and Informatics,
Graduate School of Science and Engineering, Saitama University
255 Shimo-Okubo, Sakura, Saitama 338-8570, Japan
{ koshiba,s09mm320 } @mail.saitama-u.ac.jp

Abstract. Secure message transmission (SMT) is a two-party protocol between
a sender and a receiver over a network in which the sender and the receiver are
connected by n disjoint channels and t out of n channels can be controlled by an
adaptive adversary with unlimited computational resources. If a public discussion
channel is available to the sender and the receiver to communicate with each other
then a secure and reliable communication is possible even when n ≥ t +1 .The
round complexity is one of the important measures for the efficiency for SMT.
In this paper, we revisit the optimality and the impossibility for SMT with public
discussion and discuss the limitation of SMT with the “unidirectional” public
channel, where either the sender or the receiver can invoke the public channel,
and show that the “bidirectional” public channel is necessary for SMT.

Keywords: secure message transmission, public discussion, round complexity.

1 Introduction

Dolev, Dwork, Waarts and Yung [7] introduced Secure Message Transmission protocols
to address the problem of delivering a message from a sender

S R

to a receiver in a

network guaranteeing privacy and reliability . In the network, by

n node-disjoint paths, referred to as wires ,upto t<n of which may be maliciously
controlled by the adversary with unlimited computational resources.
A perfectly secure message transmission (PSMT for short) guarantees that

S is connected to R

R always

receives message sent by S and the adversary A learns nothing about it. It was shown

that PSMT is possible if and only if n ≥ 2 t +1. For the detail and progress of PSMT,

you may see [7,17,19,2,10,14].
Franklin and Wright [11] relaxed the security requirement for PSMT protocols and
considered probabilistic security in which a privacy parameter ε and a reliability pa-
rameter δ upper-bound the advantage of the adversary in violating the privacy and the
probability that , respectively. We refer to secure

message transmission protocols in the relaxed setting as ( ε, δ )-SMT protocols and con-
sider that PSMT is a special case of SMT where ε = δ =0,thatis,(0 , 0)-SMT. For
further investigation of SMT protocols, you may see [20,9,1,15].

R fails to recover message sent by S