Cryptology ePrint Archive: Report 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).

Category / Keywords: Zero-knowledge, identification, entity authentication, MinRank problem, NP-complete problems, multivariate cryptography, rank-distance codes, syndrome decoding (SD), group signatures, ring signatures

Publication Info: This is the full up-to-date version of the paper published at Asiacrypt 2001

Date: received 21 Jul 2001, last revised 23 Sep 2001

Contact author: courtois at minrank org

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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.

Version: 20010923:205711 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]