Paper 2011/054

Non-Applicability of Pseudobasis for Designing Perfectly Secure Message Transmission Protocols Against Non-Threshold Adversary

Ashish Choudhury, Kaoru Kurosawa, and Arpita Patra

Abstract

In EUROCRYPT 2008, Kurosawa and Suzuki introduced a very fundamental and interesting concept in coding theory called pseudobasis, which was used to design the first ever efficient and communication optimal two round perfectly secure message transmission (PSMT) protocol tolerating a t-active threshold adversary. Recently in ASIACRYPT 2010, Yang and Desmedt designed first ever efficient two round and three round PSMT protocols tolerating non-threshold adversary in both directed and undirected network settings. The key idea behind their protocol is adaptation of the concept of pseudobasis from threshold settings to non-threshold settings. However, in this paper, we show that the concept of pseudobasis will not work in non-threshold settings. This automatically implies that the protocols presented by Yang et al. will fail to provide perfect reliability. As additional contribution, we present efficient two round and three round PSMT protocols tolerating non-threshold adversary in undirected networks. Our two round protocol sends single message while our three round protocol can send multiple messages concurrently. Our protocols are conceptually simpler, without using pseudobasis and also does not use the idea of converting a linear secret sharing scheme (LSSS) into a linear code, as done in the protocols of Yang et al.