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

Nicolas T.  Courtois

Paper 2001/058

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

Nicolas T. Courtois

Abstract

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.

Metadata

Available format(s): PDF PS
Publication info: Published elsewhere. This is the full up-to-date version of the paper published at Asiacrypt 2001
Keywords: Zero-knowledge identification entity authentication MinRank problem NP-complete problems multivariate cryptography rank-distance codes syndrome decoding (SD)group signatures ring signatures
Contact author(s): courtois @ minrank org
History: 2001-09-23: last of 2 revisions; 2001-07-23: received; See all versions
Short URL: https://ia.cr/2001/058
License: CC BY

BibTeX

@misc{cryptoeprint:2001/058,
      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},
      url = {https://eprint.iacr.org/2001/058}
}