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


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.

Available format(s)
-- withdrawn --
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
partho_31 @ yahoo co in
partho31 @ gmail com
kurosawa @ mx ibaraki ac jp
arpitapatra10 @ gmail com
arpitapatra_10 @ yahoo co in
arpita @ cs au dk
2011-02-17: withdrawn
2011-01-30: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.