Paper 2011/082

Does Pseudo-basis Extend to General Adversary?

Ashish Choudhury, Kaoru Kurosawa, and Arpita Patra

Abstract

Pseudo-basis is a powerful and fundamental concept in coding theory, introduced by Kurosawa and Suzuki (EUROCRYPT '08), which allows to efficiently localize t errors in a codeword in an interactive fashion, even by using a linear error correcting code with distance only t+1. It is used to construct the first efficient, communication and round optimal, 2-round perfectly secure message transmission (PSMT) scheme for n=2t+1, where an infinitely powerful adversary can actively corrupt t out of n (bidirectional) channels between a sender S and a receiver R. Recently, Yang and Desmedt (ASIACRYPT '10) claimed that by using pseudo-basis, they constructed the first ever efficient, constant round PSMTs against general (non-threshold) adversaries in undirected as well as directed networks. In this paper, our main contribution is to show that pseudo-basis can not be extended to general adversaries. This means that the PSMTs of Yang and Desmedt (based on pseudo-basis) are flawed. We next show a truly efficient, three round PSMT over directed networks against general adversaries without using pseudobasis. While the previous PSMT schemes in directed network designed without using pseudobasis are either inefficient or prone to guessing attack (shown by Yang and Desmedt in ICITS '09), our efficient scheme can resist guessing attack. Instead of using pseudo-basis, we generalize the union technique to our setting, which was previously used to construct PSMTs against threshold proactive adversaries over undirected networks. We also present simple and efficient 3-round scheme in undirected network, without basing it on pseudobasis, which can send multiple messages concurrently.

Note: During our detailed analysis of the paper, we found that the claims made in our paper are incorrect. The protocols of the paper titled "General Perfectly Secure Message Transmission Using Linear Codes" by Q. Yang and Y. Desmedt (accepted in ASIACRYPT 2010) are correct and indeed using generalized pseudo-basis we can design efficient PSMT protocols against non-threshold adversary. So the claims made in our paper regarding ASIACRYPT 2010 paper are incorrect. We are extremely sorry for the (negative) impression about the ASIACRYPT 2010 paper that might have been created due to our incorrect claims.