Skip to main content
SpringerLink
Log in

Severely denting the Gabidulin version of the McEliece Public Key Cryptosystem

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

Gabidulin has proposed a version of the McEliece Public Key Cryptosystem using what he calls maximum rank distance (MRD) codes in place of Goppa codes. It is shown how to break such a system by finding a trapdoor to it. For the size of code he suggests this can be done in about a week on a fast personal computer. The attack can be thwarted by increasing the size of the code, but the advantages claimed for the Gabidulin version over the McEliece version are then largely lost.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E. F. Brickell,Breaking Iterated Knapsacks, Lecture Notes in Computer Science, Springer-Verlag, New York, 196 (1984).

    Google Scholar 

  2. E. M. Gabidulin,Ideals over a Non-Commutative Ring and their Applications in Cryptography, Lecture Notes in Computer Science, Springer-Verlag, New York, 547 (1991).

    Google Scholar 

  3. E. M. Gabidulin, Theory of codes with maximum rank distance,Problems of Information Transmission, Vol. 21, No. 1 (1985). (Russian original January–March 1985).

  4. E. M. Gabidulin, Rank Metrics, Array-Error Correcting Codes, and Applications. Seminar given at R.H.B.N.C, University of London, 1992.

  5. J. K. Gibson,Equivalent Goppa Codes and Trapdoors to McEliece's Public Key Cryptosystem, Lecture Notes in Computer Science, Springer-Verlag, New York, 547 (1991).

    Google Scholar 

  6. R. Heiman,On the Security of Cryptosystems Based on Linear Error Correcting Codes. MSc. Thesis, Feinberg Graduate School of the Weizmann Institute of Science. August 1987.

  7. P. J. Lee and E. F. Brickell,An Observation on the Security of McEliece's Public Key Cryptosystem, Lecture Notes in Computer Science, Springer-Verlag, New York, 330 (1988).

    Google Scholar 

  8. R. Lidl and H. Niederreiter,Introduction to Finite Fields and their Applications, Cambridge University Press (1986).

  9. R. J. McEliece,A Public Key Cryptosystem Based on Algebraic Coding Theory, DSN Progress Report (Jan, Feb), Jet Propulsion Lab., California Institute of Technology, 1978.

  10. J. Van Tilburg,On the McEliece Public Key Cryptosystem, Lecture Notes in Computer Science, Springer-Verlag, New York, 403 (1988).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Birkbeck College, Malet Street, WC1E 7HX, London, England

    J. K. Gibson

Authors
  1. J. K. Gibson
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gibson, J.K. Severely denting the Gabidulin version of the McEliece Public Key Cryptosystem. Des Codes Crypt 6, 37–45 (1995). https://doi.org/10.1007/BF01390769

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01390769

Keywords

Search

Navigation