Welcome to the resource topic for 2001/058
Title:
Efficient Zero-knowledge Authentication Based on a Linear Algebra Problem MinRank
Authors: Nicolas T. Courtois
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).
ePrint: https://eprint.iacr.org/2001/058
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .