Cryptography Reference
In-Depth Information
from the point of view of low cost cryptography. In this context K. Chen pro-
posed in 1995 [5] an ecient zero-knowledge authentication protocol
without
using a hash function
and based on the syndrome decoding problem for the rank
metric.
The Chen protocol is in the spirit of Shamir's PKP protocol, but the hard
underlying problem is, as in the case of Stern's SD protocol, a syndrome decoding
problem, though for the rank distance rather than the Hamming distance.
The syndrome decoding problem for the rank metric is less known and less
studied than it's Hamming distance counterpart but it is believed to be hard by
the community. In particular the complexity of the best known attacks is more
than exponential in the size of the parameters, which enables one to consider
small parameters and hence obtain rather small key size. This latter aspect and
the fact that the Chen protocol does not use any hash function makes it a very
appealing alternative to more classical protocols.
The proposed parameters for the Chen protocol have already been attacked
twice. First by Chabaud and Stern at AsiaCrypt'96 in [4] and later by Ourivski
and Johansson in [10]: however the attacks proposed in these two papers were not
specific to the Chen protocol. In fact they improved the algorithms for solving the
generic syndrome decoding problem for the rank distance and as a by-product
broke some of the proposed parameters for the Chen protocol. In practice, since
the algorithms for the rank distance syndrome decoding problem remains largely
exponential, a small increase of the parameters for the Chen protocol permits to
resist these attacks while preserving relatively small key sizes. Overall the Chen
protocol was still unbroken in itself and was still attractive for applications.
Our Contribution:
The main result of the present paper is a total break of
the Chen zero-knowledge identification protocol in two different ways. These
attacks are made possible by the fact that the zero-knowledge proof of the Chen
protocol is flawed. These attacks are polynomial (more precisely cubic) in the
parameter size of the code and therefore lead to a total break of the protocol.
The first attack relies on an unsatisfactory way to mask a word by a simple
right matrix multiplication in the protocol. The second attack uses the fact that
no hash function is used in the commitment step of the protocol, and uses the
commitment to derive information on the secret key.
In a second part of the paper we propose a new protocol which permits the use
of the rank metric for a zero-knowledge identification scheme. Our new protocol
is a 3-pass protocol for which we add a hash function for the commitment step
and a correct way to mask a word. The protocol we propose is based on Stern's
SD protocol for the Hamming distance, adapted to the context of the rank
metric. We then give a correct zero-knowledge proof for our new protocol whose
security relies in part on the security of the hash function as in the case of Stern's
SD and Shamir's PKP protocols. Finally, a really good feature of the use of a
hash function is that it enables us to dramatically improve the soundness proof
and to significantly recuce parameter sizes. These features should make the new
protocol a strong candidate for low-cost cryptography.
