Cryptography Reference
In-Depth Information
In the following the notation (
a
|
b
) corresponds to the concatenation of
a
and
b
.
The notation
hash
(
a
) is the hash value of
a
.
Agivenbasis
β
is fixed and known in advance for the '*' product (see Section
2.2).
For the protocol a public
k
×
n
matrix over
GF
(
q
m
)
H
is fixed. The
secret
key
is a vector
s
of
V
n
(= (
GF
(
q
m
)
n
)withrank
r
.The
public key
consists of the
matrix
H
, the syndrome
i
=
Hx
t
and the rank
r
of
s
. The protocol is described
in Fig. 2. For the protocol the small base field is
GF
(2), (ie:
q
=2).
1.
[Commitment step] The prover
PR
chooses
x
∈
V
n
,
P
∈
GL
n
(GF(
q
)) and
Q
∈
GL
m
(
q
). He sends
c
1
,c
2
,c
3
such that :
c
1
=
hash
(
Q
|
P
|
Hx
t
)
,c
2
=
hash
(
Q
∗
xP
)
,c
3
=
hash
(
Q
∗
(
x
+
s
)
P
)
2.
[Challenge step] The verifier
V
sends
b
∈{
0
,
1
,
2
}
to
P
.
3.
[Answer step] there are three possibilities :
-
if
b
=0,
PR
reveals
x
and (
Q
|
P
)
-
if
b
=1,
PR
reveals
x
+
s
and (
Q
|
P
)
-
if
b
=2,
PR
reveals
Q
∗
xP
and
Q
∗
sP
4.
[Verification step] there are three possibilities :
-
if
b
=0,
V
checks
c
1
and
c
2
.
-
if
b
=1,
V
checks
c
1
and
c
3
.
-
if
b
=2,
V
checks
c
2
and
c
3
and that
rank
(
Q
∗
sP
)=
r
.
Fig. 2.
Repaired protocol
Ver i ficat i on Step
Here we explain the verification step. There are three cases in the verification,
b
=0
,
1
,
2.
In the case
b
=0,
V
receives
x
and (
Q
|
P
), he computes
Hx
t
and
Q
∗
xP
and
checks the hash values
c
1
=
hash
(
Q
|
P
|
Hx
t
)and
c
2
=
hash
(
Q
∗
xP
).
In the case
b
=1,
V
receives
x
+
s
and (
Q
|
P
), he computes
Hx
t
=
H
(
x
+
s
)
t
−
i
since
i
=
Hs
t
and
Q
∗
(
x
+
s
)
P
which permits to check
c
1
and
c
3
.Inthecase
b
=2,
V
receives
Q
∗
xP
and
Q
∗
sP
, he computes the hash values
c
2
=
hash
(
Q
∗
xP
)
and
c
3
=
hash
(
Q
∗
xP
+
Q
∗
sP
)=
hash
(
Q
∗
(
x
+
s
)
P
). He also checks that
rank
(
Q
∗
sP
)=
r
.
6.2 Zero-Knowledge Properties
We saw that the Chen protocol has flaws in its zero-knowledge proof which implied
a total break of the system: deriving correct proofs is thereforeimportant.Inthe
case of the new protocol, the zero-knowledge proof described hereafter is based
on the zero-knowledge proof of the Stern SD protocol, adapted to the rank met-
ric context. Crucial is the 'equivalent' notion of a permutation for the Hamming
distance.
