Security of Xinmei digital signature scheme

Xinmei (see ibid., vol.26, no.13, p.898-9, 1990) has proposed a digital signature scheme that uses error correcting codes in a manner similar to that of the McEliece public-key cryptosystem. It is claimed that the cryptanalytic work factor for the Xinmei system is O((n-k)!) or O(2^n-k), where n and k are the length and dimension, respectively, of the algebraic code selected for the system. Here it is shown that, in some cases, the cryptanalytic work factor can be as low as O(n³).