Information Technology Reference
In-Depth Information
matrix
M
, a set of
k
distinct matrices
{M
1
,
M
2
, ..., M
k
}
and a positive integer
n ≤ k
, and the question to answer may be stated as follows: is it possible to
express
M
as a product of
n
matrices belonging to the set
{M
1
,
M
2
, ..., M
k
}
.
The distribution considered to generate the integers
k
and
n
and the integer
entries of the matrices is the uniform distribution.
The proposed scheme uses the search version of the above distributional
problem. The diculty of this new version is equivalent to that of the distribu-
tional decision problem as may be deduced from the general result stated in [20],
according to which, search and decision distributional problems are equivalent
from the average-case analysis point of view.
3 The Identification Scheme
The purpose of the scheme proposed below is to allow the identification of users
in a system run by a central trusted authority. The proposed scheme uses
k
fixed
and public
, which
are common to all users and originally generated randomly by the authority.
Ideally, this means that each element of each matrix is chosen uniformly and
independently, even if practicality may impose the use of some form of pseudo-
random generator.
Two variants of the scheme may be considered corresponding to the origi-
nal Distributional Matrix Representability Problem, where each participant A
chooses the secret number
r × r
invertible matrices with integer entries
M
i
,i
=1
,
2
, ..., k
n
of matrices to compute her identification product, or
to the bounded version with
should be randomly
chosen by the authority and published as part of the identification system.
Upon registration, each user Alice chooses at random
r
= 20, where a fixed number
n
n
matrices
{M
i
1
,
from the public set, computes their product
j
=1
M
i
j
M
i
2
,...,
M
A
, and
communicates it to the authority. This matrix should be made available in some
form of public directory linked to the actual identity of the user, or be certified
by means of a digital signature of the authority. So, when a user Alice wants to
identify herself to Bob, the first step is to submit her public identification matrix
in order to undertake an identification session. Once the correctness of her public
identification has been checked by Bob, either through the public directory, or
by means of the authority sign, the interactive identification protocol can take
place.
Zero-knowledge identification schemes relies on the important notion of com-
mitment, which is an electronic way to temporarily hide a secret that cannot be
changed. This may be achieved through a two-stage process with a commit stage
and a decommit stage. In the commit phase, the user Alice sends to Bob the wit-
ness of her committed secret. Later, during the decommit phase, the user Alice
simply reveals the value of her secret so the computation of the corresponding
witness may be checked by Bob.
As usual in zero-knowledge design the proposed algorithm is composed of
several independent iterations of an atomic sub-routine. The first step of each
atomic subroutine consists in the generation of a random integer vector
v
with
M
i
n
}
=
