Cryptography Reference
In-Depth Information
Full Cryptanalysis
of the Chen Identification Protocol
Philippe Gaborit
1
, Julien Schrek
1
, and Gilles Zémor
2
1
Université de Limoges, XLIM-DMI,
123, Av. Albert Thomas
87060 Limoges Cedex, France
{gaborit,julien.schrek}@unilim.fr
2
Institut Mathématiques de Bordeaux UMR 5251 - Université Bordeaux I,
351 cours de la Libération, 33451, Talence, France
{gilles.zemor}@math.u-bordeaux.fr
Abstract.
In 1995, K. Chen proposed a 5-pass zero-knowledge identifi-
cation protocol based on the rank distance. The protocol is a 5-pass pro-
tocol with cheating probability
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 pro-
tocol'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 iden-
tification 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.
Keywords:
Chen protocol, zero-knowledge, cryptanalysis, rank metric.
1
Introduction
Today, identification protocols are essential for the security of computer networks
and smart cards. Zero-Knowledge is a useful tool to prove that a protocol can
be reused without loss of security. Most practical zero-knowledge protocols are
based on number theory and it is worth searching for alternatives for at least
two reasons: first, number theory based protocols are often costly in terms of
computational complexity and second their security will collapse if a workable
quantum computer comes to exist.
Over the years several protocols have been proposed that rely on NP-Complete
problem and based on linear functions [11], [13], [14]. Although recent advances
have appeared, e.g. [8], that improve some of these protocols they are still mostly
unsatisfactory because of their key size and/or their communication cost, more-
over they intrinsically rely on a hash function which can be seen as a drawback
