International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient Zero-knowledge Authentication Based on a Linear Algebra Problem MinRank

Authors:
Nicolas T. Courtois
Download:
URL: http://eprint.iacr.org/2001/058
Search ePrint
Search Google
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).
BibTeX
@misc{eprint-2001-11470,
  title={Efficient Zero-knowledge Authentication Based on a Linear Algebra Problem MinRank},
  booktitle={IACR Eprint archive},
  keywords={Zero-knowledge, identification, entity authentication, MinRank problem, NP-complete problems, multivariate cryptography, rank-distance codes, syndrome decoding (SD), group signatures, ring signatures},
  url={http://eprint.iacr.org/2001/058},
  note={This is the full up-to-date version of the paper published at Asiacrypt 2001 courtois@minrank.org 11588 received 21 Jul 2001, last revised 23 Sep 2001},
  author={Nicolas T. Courtois},
  year=2001
}