Paper 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.