CryptoDB
MinRank problem and Zero-knowledge authentication
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2001-11416,
title={MinRank problem and Zero-knowledge authentication},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / Zero-knowledge, NP-complete problems, authentication, MinRank, SD, anonymous group signatures},
url={http://eprint.iacr.org/2001/004},
note={ courtois@minrank.org 11348 received 15 Jan 2001, withdrawn 26 Jan 2001},
author={Nicolas T. Courtois},
year=2001
}