Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Full Cryptanalysis of the Chen Identification Protocol
verfasst von : Philippe Gaborit, Julien Schrek, Gilles Zémor
Erschienen in: Post-Quantum Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In 1995, K. Chen proposed a 5-pass zero-knowledge identification protocol based on the rank distance. The protocol is a 5-pass protocol with cheating probability
$\frac{1}{2}$
in the spirit of Shamir’s PKP protocol and Stern’s SD protocol, but it has the additional property of avoiding the use of a hash function. This latter feature is very interesting from a low-cost cryptography perspective, but it also raises the suspicion of being too good to be true.
The contribution of this paper is twofold, first we show that the protocol’s proof of zero-knowledge is flawed and we describe how to fully break the protocol in two different ways and in time polynomial in the size of the parameters. Secondly we propose a new zero-knowledge identification protocol for rank distance, for which we give a rigorous proof of zero-knowledge: however the proof requires the use of a hash function. The parameters of the new protocol are substantially improved compared to those of Chen’s original protocol.