Paper 2001/058

Efficient Zero-knowledge Authentication Based on a Linear Algebra Problem MinRank

Nicolas T. Courtois


A Zero-knowledge protocol provides provably secure entity authentication based on a hard computational problem. Among many schemes proposed since 1984, the most practical rely on factoring and discrete log, but still they are practical schemes based on NP-hard problems. Among them, the problem SD of decoding linear codes is in spite of some 30 years of research effort, still exponential. We study a more general problem called MinRank that generalizes SD and contains also other well known hard problems. MinRank is also used in cryptanalysis of several public key cryptosystems such as birational schemes (Crypto'93), HFE (Crypto'99), GPT cryptosystem (Eurocrypt'91), TTM (Asiacrypt'2000) and Chen's authentication scheme (1996). We propose a new Zero-knowledge scheme based on MinRank. We prove it to be Zero-knowledge by black-box simulation. An adversary able to cheat with a given MinRank instance is either able to solve it, or is able to compute a collision on a given hash function. MinRank is one of the most efficient schemes based on NP-complete problems. It can be used to prove in Zero-knowledge a solution to any problem described by multivariate equations. We also present a version with a public key shared by a few users, that allows anonymous group signatures (a.k.a. ring signatures).

Note: A preliminary version of the scheme was presented at the rump session of Crypto 2000 as well as at the conference "Public Key Cryptography and Computational Number Theory", Warsaw, September 11-15, 2000.

Available format(s)
Publication info
Published elsewhere. This is the full up-to-date version of the paper published at Asiacrypt 2001
Zero-knowledgeidentificationentity authenticationMinRank problemNP-complete problemsmultivariate cryptographyrank-distance codessyndrome decoding (SD)group signaturesring signatures
Contact author(s)
courtois @ minrank org
2001-09-23: last of 2 revisions
2001-07-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicolas T.  Courtois},
      title = {Efficient Zero-knowledge Authentication Based on a Linear Algebra Problem MinRank},
      howpublished = {Cryptology ePrint Archive, Paper 2001/058},
      year = {2001},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.