Cryptography Reference
In-Depth Information
5 Countermeasures
5.1 Defense against the Support Attack
The support attack uses the fact that
s
∼
sP
. A simple repair is to multiply
s
by a matrix
Q
in
GL
m
(
q
) using the product
and a matrix
P
in
GL
n
(GF(
q
))
instead of just using the matrix
P
. The fact that every vector can be turned into
any vector with the same rank implies that a support attack is not possible. The
change affects also
c
which has to be
c
=
H
(
Q
∗
xP
)
t
,
w
becomes
x
+
Q
−
1
sP
−
1
and if (
b
= 0) the prover has to send
Q
and
P
instead of
P
.Wenoticethatthe
verification has no problem because we have (
Q
∗
x
)
P
=
Q
∗
∗
(
xP
). However this
repair does not affect the linear attack.
5.2 Defense against the Linear Attack
The problem of the Chen protocol exploited in the linear attack is that
Hx
t
is
a linear equation which simplifies other linear equations. A simple way to repair
the linear attack is to replace
c
=
Hx
t
by a non linear equation. We use here
c
=
hash
(
x
)where
hash
is a hash function to be sure that no information can
be obtained from
c
.
6ANewProtocol
We saw in previous sections that the zero-knowledge proof of the Chen protocol
was incomplete and hence opened the door to potential attacks. We saw that such
attacks could be made possible through the exploitation of a bad masking and the
fact that no hash function was used in the commitment step. We hence propose
a new protocol for which a correct zero-knowledge proof is possible. It implies in
particular the use of a correct masking (see Proposition 3) and a hash function
for commitments. The protocol can be seen as an adaptation of the Stern SD
protocol in a context of rank distance, we prove that our protocol benefits from
the same feature as the Stern SD protocol: a 3-pass zero-knowledge identification
protocol with a 2/3 cheating probability. However in terms of communication
cost it is better than Stern's SD protocol.
6.1 Description of the Protocol
The protocol proposed here is a rank metric adaptation of the Stern protocol
[13] in which the masking of a codeword by a permutation is replaced by the
masking
x
→
Q
∗
xP
which has the same property in terms of rank distance as
a permutation for a codeword with Hamming distance, since it can transform
any given
x
with given rank to
any
element with the same rank. This property
(which is not obtained if one only applies a right multiplication by
P
)iscrucial
for the zero-knowledge proof of the protocol. It also contains a hash function for
the commitment.
