Cryptology ePrint Archive: Report 2001/004

MinRank problem and Zero-knowledge authentication

Nicolas T. Courtois

Abstract: A zero-knowledge protocol provides provably secure authentication based on a computational problem. Several such schemes have been proposed since 1984, and the most practical ones rely on problems such as factoring that are unfortunately subexponential. Still there are several other (practical) schemes based on NP-complete problems. Among them, the problems of coding theory are in spite of some 20 years of significant research effort, still exponential to solve.

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