Information Technology Reference
In-Depth Information
the same size than the matrices intervening in the protocol. This generated
vector and its transposed
v
T
are used to generate 2
k
witness vectors of size
M
i
v
T
)
T
}
i
=1
,...,k
. So, the interactive identification proposal includes
k
,
{vM
i
,
(
m
rounds of the following atomic sub-routine:
1.
(Commit)
A generates at random a secret vector of size
r
,
v
, and an integer
between 2 and 2
n
, and sends to B in a random order the 2
x
k
witness vectors
vM
A
x
v
T
.
M
i
v
T
)
T
}
i
=1
,...,k
and the witness integer
of size
k
,
{vM
i
,
(
2.
(Challenge)
B selects randomly a bit
e
, and depending on its value, B re-
quests to A:
(a)
(Decommit)
the vector
v
and the integer
x
,if
e
=0, or
M
i
n
v
T
, and the
(b)
(Proof )
the vectors
vM
i
1
and
r × r
matrix
M
A
1
=
M
i
1
−
1
M
A
x
M
i
n
−
1
,if
e
=1.
3.
(Response)
A responses to the challenge
4.
(Verification)
Depending on the selected challenge, B checks that:
(a) if
e
=0, witness information is correct.
e
vM
i
1
, the matrix
M
A
1
(b) if
=1, from the product between the row vector
vM
A
x
v
T
is obtained. Also,
M
i
n
v
T
, the witness integer
and the column vector
B uses recursively for
j
=2
, ..., t
the following steps to verify that A knows
the factor matrices of
M
A
:
b1.
(Commit)
A sends to B the witness integer
vM
A
j
−
1
x
v
T
M
i
n
−
j
+1
v
T
b2.
(Proof )
A indicates to B the two vectors
vM
i
j
and
, and
M
A
j
−
1
x
M
i
n
−
j
+1
−
1
.
b3.
(Verification)
B checks that from the product between the row vector
vM
i
j
, the matrix
M
i
j
−
1
sends him the
r × r
matrix
M
A
j
=
M
A
j
M
i
n
−
j
+1
v
T
, the witness
and the column vector
vM
A
j
−
1
x
v
T
is obtained.
integer
In the first variant corresponding to the original problem, since B does not
know the number
of recursive iterations should be previously
agreed by both participants according to their different interests. In the second
variant such a number should be
n
, the number
t
t
=
n/
2 in order to prove the knowledge of the
n
factor matrices.
As in any zero-knowledge identification scheme there exists certain proba-
bility that a fraudulent prover passes the verification stage. In this case, such a
probability depends strongly on the number of iterations
m
(and also on
t
in the
first variant).
The random choice of vectors
allows to detect a possible fraud of a prover
that does not generate adequately the commitment witness. The Monte Carlo
algorithms described by Freivalds [21] for the verification of the product of two
matrices may be used in the verfication stage to achieve the detection process.
The error probability in this probabilistic algorithms is bounded by 2
−m
, where
m
v
is the number of iterations to be performed. Furthermore, all the products
of matrices required in the protocol should be carried out using the algorithm
proposed in [22], due to its eciency.
