Cryptography Reference
In-Depth Information
If
j
= 2 it sends
c
1
,c
2
and
c
3
such that:
c
1
=
hash
(
x
)
,c
2
=
hash
(
Q
∗
xP
)
,c
3
=
hash
(
Q
∗
(
x
+
z
)
P
)
2.
B
chooses
b
∈{
.
3. If
b
=0,
S
sends
x
,
Q
and
P
.
If
b
=1,
S
sends
x
,
Q
and
P
.
If
b
=2,
S
sends
Q
∗
xP
and
Q
∗
zP
.
0
,
1
,
2
}
4. If
b
=
j
the execution works (it was made for it) and the simulator saves the
execution, otherwise the simulator restarts this execution.
The simulation succeeds if it can save
l
executions of this scheme with
b
=
j
.This
can be done in about 3
l
executions since the probability that
b
=
j
is
1
3
.The
simulator creates a simulated execution of the protocol which is indistinguishable
from a real execution because of the use of the hash function, it was not the case
in the Chen protocol. The value
x
,
Q
and
P
are clearly constructed with a uni-
form distribution, which is the same as the distribution given by
Q
∗
(
x
+
s
)
P
in
the real scheme. The last value
z
has the same distribution as the value
Q
∗
sP
because of the use of
Q
and
P
. Indeed, if
Q
and
P
are randomly chosen, for
s
a
vector of rank
r
, we saw in Section 2.2 that the vector
Q
∗
sP
could be
any vector
of rank
r
with a uniform probability. It is possible for the simulator to guess in ad-
vance all challenge values
b
with a uniform distribution. All distributions are equal
to those in the real scheme, it makes this simulator indistinguishable from a real
execution. With this simulator anyone can simulate an execution of the scheme
without knowing the secret key, which proves the zero-knowledge property.
Remark:
This proof is made possible because of the use of matrices
P
and
Q
on
one hand and of the hash function on the other hand which assure the indistin-
guishability between a real execution of the protocol and a simulation. The Chen
protocol did not use these features, for instance for
l
executions of the Chen pro-
tocol it is possible to distinguish between random words
z
of rank
r
(in the sim-
ulation) and vectors
sP
which by construction always belong to the same vector
space. The same phenomenon occurs with the use of hash functions in the com-
mitment step.
7 Parameters, Improvements and Comparison
7.1 Parameters
The soundness proof we proposed in the previous section enables us to take for
the weight of the secret
s
a value just below the minimum distance of the code. If
one considers random codes, it is known that with high probability they lie on the
Gilbert-Varshamov bound (cf. [9] for the details on the exact formulae for these
parameters). If we consider,
q
=2
,n
=20
,m
=20and
k
=11oneobtainsa
minimal distance of 7, hence we can take
r
= 6 for the rank weight of the secret.
In that case the known attacks lead to a complexity of at least 2
83
operations.
