Information Technology Reference
In-Depth Information
4 Security of the Scheme
We first briefly discuss security issues from an informal point of view. A more
formal approach will be taken at the end of this section. Clearly, the security of
the scheme relies on the diculty of the Distributional Matrix Representability
Problem because in order to pass all the possible verifications A should know
the
whose product is her public identification
matrix. So, since the base problem of the scheme is NP-complete on average, an
adequate choice of parameters
n
matrices
M
i
j
for
j
=1
,
2
, ..., n
and a truly random generation of matrices
guarantee that solving the problem is beyond the limits of current computing
technology independently of the choice of random instances.
Regarding parameters
k
and
n
k
n
and
, in order to avoid an exhaustive search through
all the
n
possible combinations of
n
k
matrices from the set, the integer
should
be approximately two times
, and both values should be large enough, which
implies for today resources approximately
n
130.
On the other hand, in the second variant the matrix size
r
is one of the
security parameters, but in this case it is dicult to recommend a minimum size
for it because the problem has been shown undecidable even for small values as
r
k ≥
= 4, [23]. Anyway, it may be assumed that larger sizes yield better security.
With respect to the Completeness property, if A follows the protocol, it
is clear that B always accepts A's proof. To see it, note that in each itera-
tion A builds the products
M
i
v
T
)
T
}
i
=1
,...,k
as described in the com-
mit stage of the algorithm. If B chooses the challenge
{vM
i
,
(
e
=0, then A is able
to give him the vector
v
and the integer
x
. In this way B can generate the
vM
A
x
v
T
in order to compare
these results with the witnesses given by A in the commit stage. Both previ-
ous results coincide since A has followed correctly the protocol. On the other
hand, in case B chooses the challenge
M
i
v
T
)
T
}
i
=1
,...,k
products
{vM
i
,
(
and the integer
e
=1, he receives for
j
=1
, ..., t
the
vM
A
j
−
1
x
v
T
, the vectors
M
i
n
−
j
+1
v
T
, and the
integer
vM
i
j
and
r × r
matrix
M
i
j
−
1
M
A
j
−
1
x
M
i
n
−
j
+1
−
1
, so when B multiplies the row vector
M
A
j
=
vM
i
j
, the
M
i
n
−
j
+1
v
T
, he obtains the witness integer
vM
A
j
−
1
x
v
T
that was sent to him by A in the commit stage.
Regarding the security from the verifier's point of view (i.e. soundness prop-
erty), a cheating prover may guess the verifier's challenge
matrix
M
A
j
and the column vector
in advance, and so
choose an adequate response to the corresponding challenge, compute the false
commitments and send them in the challenge step. Evidently, if the verifier's
question happens to be
e
, then the cheating prover successfully passes the veri-
fication. However, the probability of this event is just 1/2 for one round and so
2
−m
for the whole protocol. In order to answer all verifier's possible questions,
an impersonator should be able to generate witnesses satisfying at the same time
a possible decommit stage and proof stage. However, finding such a combination
is as hard as solving A's instance of the Distributional Matrix Representability
Problem.
Zero-knowledge property is commonly proved through the simulation
paradigm. A black-box simulator is an algorithm that tries to simulate the in-
teraction of a possible adversary with a honest verifier Bob, without knowing his
e
