[ Changed 25th January 1997 ]
The Gabidulin Cryptosystem is a Public Key Cryptosystem (PKC) based on error correcting codes. Two versions of it have been published. After I showed how to break medium sized instances of the first version, Prof. Gabidulin agreed that his choice of system parameters was unfortunate, and produced a second set of parameters which he claimed were the most secure set possible. They turn out to be the least secure set possible, and this talk will show how to break even large instances of the second version in a matter of seconds, while at the same time showing how to choose the parameters so as to defeat my methods. Finding a secret key of an instance of the PKC can be reduced to solving an instance of an intriguing search problem of linear algebra, and it would be of great interest to know whether this problem is NP-complete, since there is no known PKC for which finding secret keys is NP-complete. One can make an intractability assumption that members of a certain family of instances of the search problem are almost always hard, and on this assumption the Gabidulin PKC is provably secure.