Cryptography Reference
In-Depth Information
Completeness.
An honest prover who knows
s
will be able to construct
c
1
,c
2
and
c
3
. He will always be identified by a verifier because the verifications match
with the data
c
1
,c
2
and
c
3
.
Soundness.
The proof exposed here is not the same as for the Chen protocol [5],
because of the use of hash functions. In the Chen protocol the secret key
s
is taken
of weight under
3
(
2
in Chabaud-Stern). The use of a hash function permits us to
reach
d
(it dramatically improves the parameters which can be taken in the new
protocol).
We prove the following theorem:
Theorem 1.
If a prover PR is able to correctly answer all three challenges then
either he is able to find a col lision for the hash function, or he has access to the
secret key
s
.
Proof:
If someone can answer in the three cases
b
=0
,
1
,
2 for a chosen triple (
c
1
,c
2
,c
3
),
then he knows:
-
x
1
and (
Q
1
,P
1
) such that :
c
1
=
hash
(
Q
1
|
P
1
|
Hx
1
)
,c
2
=
hash
(
Q
1
∗
x
1
P
1
)
-
w
and (
Q
2
|
P
2
) such that :
c
1
=
hash
(
Q
2
|
P
2
|
Hw
t
−
i
)
,c
3
=
hash
(
Q
2
∗
wP
2
)
-
x
2
and
z
such that :
c
2
=
hash
(
x
2
)
,c
3
=
hash
(
x
2
+
z
)
,rank
(
z
)=
r
So either the attacker finds a collision for the hash function or all the respective
pre-images of
c
1
,c
2
and
c
3
are equal and we have :
Q
1
=
Q
2
,P
1
=
P
2
,Q
1
∗
x
1
P
1
=
x
2
,Q
2
∗
wP
2
=
x
2
+
z
and
Hx
1
=
Hw
t
−
i
From which we deduce that
Q
1
∗
wP
1
=
x
2
+
z
=
Q
1
∗
x
1
P
1
+
z
and then
w
−
x
1
=
Q
−
1
1
∗
zP
−
1
1
and now:
i
=
Hw
t
−
Hx
1
=
H
(
w
−
x
1
)
t
=
H
(
Q
−
1
∗
zP
−
1
1
)
t
,
1
with
rank
(
z
)=
r
.
