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) Short URL: ia.cr/2001/058 Discussion forum: Show discussion | Start new discussion