Cryptanalysis of the Harn and Wang modification of the Xinmei digital signature scheme

摘要

Xinmei (see ibid., vol.26., no.13, p.898-9,1990) has devised a digital signature scheme based on error correcting codes. Harn and Wang (see ibid., vol.28, no.2, p.157-9, 1992) have observed that the combination of valid signatures produced by the Xinmei digital signature scheme yields valid signatures for other messages. Harn and Wang have proposed a modified version of the Xinmei scheme that prevents such selective forgeries. The authors have previously shown that the Xinmei scheme can be totally broken by a chosen-ciphertext attack with complexity O(n/sup 3/), where n is the length of the code used in the scheme. In this article it is shown that the Harn and Wang modified scheme can be broken by a known-plaintext attack with complexity O(k/sup 3/).