The problem MinRank recently arouse in cryptanalysis of HFE (Crypto'99) and TTM (Asiacrypt'2000) public key cryptosystems. It happens to ba a strict generalization of those hard problems of (decoding) error correcting codes.
We propose a new Zero-knowledge scheme based on MinRank. We prove it to be Zero-knowledge by black-box simulation. We compare it to other practical schemes based on NP-complete problems.
The MinRank scheme allows also an easy setup for a public key shared by a few users, and thus allows anonymous group signatures.
Category / Keywords: public-key cryptography / Zero-knowledge, NP-complete problems, authentication, MinRank, SD, anonymous group signatures Date: received 15 Jan 2001, withdrawn 26 Jan 2001 Contact author: courtois at minrank org Available format(s): (-- withdrawn --) Version: 20010126:232704 (All versions of this report) Short URL: ia.cr/2001/004 Discussion forum: Show discussion | Start new discussion