Digital Signature Schemes Based on Error-correcting Codes

Abstract

We examine the security of several digital signature schemes based on algebraic block codes. It is shown that Xinmei's digital signature scheme can be totally broken by a known plaintext attack with complexity O(k/sup 3), where k is the dimension of the code used in the scheme. Ham and Wang have proposed a modified version of Xinmei's scheme that prevents selective forgeries. Their scheme is also shown to be vulnerable to a known plaintext attack. We then present a new signature scheme that we believe to be resistant to the previously described attacks.