Evaluation of effectiveness of chosen-plaintext attacks on the Rao-Nam cryptosystem over a finite Abelian group

Abstract

The Rao-Nam cryptosystem is a symmetric version of the McEliece code-based cryptosystem proposed to get rid of the shortcomings inherent in the first symmetric code-based encryption schemes. Almost immediately after the publication of this cryptosystem, attacks on it based on selected plaintexts appeared, which led to the emergence of various improvements and modifications of the original cryptosystem.

The secret key in the traditional Rao-Nam scheme is a certain Boolean matrix and a set of binary vectors used to generate distortions during encryption. Such vectors must have different syndromes, that is, be different modulo of the code generated by the rows of the specified matrix. The original work of Rao and Nam considered two methods of forming the set of these vectors, the first of which consists in using predetermined vectors of sufficiently large weight, and the second is random selection of these vectors according to the equiprobable scheme. It is known that the first option does not provide the proper security of the Rao – Nam cryptosystem (due to the small number and simple structure of these vectors), but the second option is more meaningful and requires additional research. The purpose of this paper is to obtain estimates of the effectiveness (time complexity for a given upper bound of the error probability) of attacks on a cryptosystem, which generalizes the traditional Rao – Nam scheme to the case of a finite Abelian group (note that the need to study such versions of the Rao – Nam cryptosystem is due to their consideration in recent publications). Two attacks, based on selected plaintext, are presented. The first of them is not mentioned in the works known to the authors of this article and, under certain well-defined conditions, it allows recovering the secret key of the cryptosystem with quadratic complexity.

The second attack is a generalized and simplified version of the well-known Struik-van Tilburg attack. It is shown that the complexity of this attack depends on the power of the stabilizer of the set of vectors, which forms the second part of the key, in the translation group of the Abelian group, over which the Rao – Nam cryptosystem is considered. In this paper, a bound is obtained for the probability of triviality of the stabilizer under the condition of random choice of this set. From the obtained bound, it follows that Struik-van Tilburg attack is, on average, noticeably more efficient than the worst case considered earlier.