Johan van Tilburg, `` Security-Analysis of a Class of Cryptosystems Based on Linear Error-Correcting Codes,'' Ph. D., Eindhoven University of Technology, Eindhoven, the Netherlands, November 29, 1994

This dissertation describes a new universal probabilistic algorithm for decoding arbitrarily linear encoding schemes. Its decoding complexity is shown to be equal to the Information Set Decoding. The work-factor, memory-factor and complexity of this new algorithm are evaluated and its overall performance is compared to other general decoding algorithms. Furthermore, the new algorithm is rewritten as a syndrome decoding algorithm and then extended to simultaneously process several syndromes in a batch. Finally, a slight structure modification of the batch description yields a syndrome decoding algorithm with several simple, dedicated circuits. To date, this new algorithm is the most efficient one in its class for moderate code parameter values.

This dissertation analyzes locally-randomized cryptosystems which make use of linear encoding schemes. In this class of cryptosystems, the message blocks are encoded into codewords and then locally randomized using random error patterns. This dissertation focuses on the McEliece locally-randomized public-key cryptosystem by first giving a detailed compilation and analysis of relevant literature describing its security. Then, this system's relation to the Niederreiter and the Stern public-key cryptosystems are briefly discussed. It is shown that the new decoding algorithms determine the range of values of the code parameters for which these locally-randomized public-key cryptosystems' security is vulnerable to cryptanalysis. Three insecure and related digital signature schemes are also identified.

In contrast to the McEliece public-key cryptosystem, the Rao-Nam and Li-Wang locally-randomized secret-key cryptosystems keep their linear encoding scheme secret. It is believed that this secrecy allows simpler and smaller codes to be used, which require less storage and enable faster processing. However, this dissertation shows that for this class of secret-key cryptosystems an equivalent encoding scheme can be obtained in an efficient way. Hence, it is concluded that the code parameter values for locally-randomized secret-key cryptosystems should be as large as those for locally-randomized public-key cryptosystems.