Cryptology ePrint Archive: Report 2011/054

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

Ashish Choudhury and 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.

Category / Keywords: cryptographic protocols /

Date: received 28 Jan 2011, withdrawn 16 Feb 2011

Contact author: partho_31 at yahoo co in, partho31@gmail com, kurosawa@mx ibaraki ac jp, arpitapatra10@gmail com, arpitapatra_10@yahoo co in, arpita@cs au dk

Available format(s): (-- withdrawn --)

Version: 20110217:052944 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]