Cryptography Reference
In-Depth Information
∗
zP
−
1
)=
rank
(
z
), the attacker knows a solution of the dif-
ficult problem which describes the secret key
s
(and which is unique for
r
less
than the Gilbert-Varshamov-like bound). He is therefore able to reconstruct the
secret
s
Since
rank
(
Q
−
1
1
A corollary of the theorem is that the probability of success when the secret key
s
is not known is less or equal to
3
. Now it is possible to anticipate (as for the Stern
SD scheme) any two challenges among the three:
-
for
b
= 0 or 1, a cheater takes random
P
,
Q
and
x
and constructs
z
which
satisfies
Hz
t
=
Hx
t
+
i
(notice that since there is no weight constraint finding
a
z
is easy). He takes
c
1
and
c
2
as in the protocol and
c
3
=
hash
(
Q
∗
zP
). For
b
= 0 the cheater reveals
x
and (
P
|
Q
)andfor
b
=1hereveals
P, Q
and
z
.
The verification follows.
-
for
b
= 0 or 2, a cheater takes random
P
,
Q
and
x
and constructs
z
random
of rank weight
r
.Hetakes
c
1
and
c
2
as in the protocol and
c
3
=
hash
(
Q
∗
(
x
+
z
)
P
). For
b
= 0 the cheater reveals
x
and (
P
|
Q
)andfor
b
=2hereveals
Q
∗
xP
and (
Q
∗
zP
). The verification works.
-
for
b
= 1 or 2, a cheater takes random
P
,
Q
,
x
and
z
random of rank weight
r
. He sends
c
1
=
hash
(
P
|
Q
|
H
(
x
+
z
)
t
(
x
+
z
)
P
)and
c
2
=
hash
(
Q
∗
xP
). Now for
b
= 1 the cheater reveals
x
+
z
and
P, Q
,andfor
b
=2:
Q
∗
xP
and
Q
∗
zP
. The verification follows.
−
i
)
,c
3
=
hash
(
Q
∗
2
Overall the probability of cheating is therefore exactly
3
.
Security.
The security of the secret key is based on the Syndrome decoding prob-
lem for the rank distance in the same way than for the Chen protocol.
Zero-Knowledge.
The aim of this proof is to construct a simulator of the scheme.
If we can simulate the scheme, we can use this construction to attack the secret
key without needing to actually run the scheme. This implies that a transcript of
the actual scheme gives no usable information.
Let be
B
a verifier and
S
be the simulator that we construct. We construct
a simulator which can answer any of the three challenges because the simulator
always makes a good guess (in particular only 2 of the 3 commitments need to be
verified). The protocol can be simulated as follows:
1.
S
chooses random
x
∈
V
n
and
P
∈
GL
n
(GF(
q
)),
Q
∈
GL
m
(
q
)and
z
with
rank
(
z
)=
r
.
The simulator also chooses
j
∈{
0
,
1
,
2
}
corresponding to the challenge that
he tries to guess in advance.
If
j
= 0, it sends
c
1
,c
2
and
c
3
such that :
c
1
=
hash
(
Q
|
P
|
Hx
t
)
,c
2
=
hash
(
Q
∗
xP
)
,c
3
=
hash
(
x
)
If
j
= 1 it sends
c
1
,c
2
and
c
3
such that:
c
1
=
hash
(
Q
|
P
|
Hx
t
−
i
)
,c
2
=
hash
(
Q
∗
xP
)
,c
3
=
hash
(
Q
∗
xP
)
