Cryptography Reference
In-Depth Information
of the simulator may imply attacks using a potential leak of information of the
protocol. We present here two attacks based on using that leak of information.
Indeed, we prove that Hx t gives information about x (by linearity) and sP
gives information about s (the underlying vector space of sP is the same as the
underlying vector space of s ), with the two following attacks.
4.2 The Support Attack
High level overview. In the protocol the matrix P is used to mask the secret
s into a potential secret sP like it is done in PKP [11] or in SD [13], P taking
the place of the permutation in these protocols. However in Chen's protocol the
masking by P is weak and leaks information. To understand this point, consider
the case of Stern's SD protocol: a permutation of coordinates has the property
that it can transform any codeword with a given Hamming weight into any
codeword with the same weight. This point is crucial for indistinguishability in
the zero-knowledge proof of Stern SD protocol. In the case of Chen's protocol, the
multiplication by the matrix P is the equivalent notion to that of the permutation
for the Hamming distance in Stern's SD protocol, however this transformation
does not possess the same feature as the permutation in the Hamming distance
case. Indeed this transformation does not permit to associate a given word with
a given rank distance, to any word with the same rank distance, it only gives a
subset of codewords with the same rank distance. In practice it leads to a leak
of information.
Indeed a right multiplication of s by P does not change the basis gener-
ated by the coordinates of s and therefore all elements of the form sP generate
the same vector space. Therefore the masking sP is not general enough and
gives information on the secret s by revealing the vector space generated by its
coordinates.
If we compare this attack with the Chabaud-Stern attack of [4], we derive a
vector space basis which contains the secret s when their attack (which is more
general on the rank distance) consists in an exponential search for such a vector
space basis. Our attack therefore avoids the exponential search of a basis and
reads it directly from sP , leaving only the linear algebra part of the attack.
Description. Each time a prover wants to be identified with the protocol and
his key s , he has to pass a sequence of challenges. The attack presented in this
paragraph works when the challenge is the one represented by the value b =1
in the description of the Chen protocol. This challenge occurs so many times
that the attack can be executed in a passive way instead of an active way. We
consider an execution of the protocol when the prover has to send the value x
(case b = 1). In this case the value sP 1 can be computed with the formula
λ 1 ( w x ). The attack uses the fact that there is a way to retrieve s from sP 1
with a very low complexity.
In the Basic Facts section we saw that s sP 1 , so their coordinates generate
the same vector space E over GF(q). The specific rank r of s implies that E is a
 
Search WWH ::




Custom Search