Information Technology Reference
In-Depth Information
private input (i.e. his challenges). So, for this algorithm a resettable simulator
may be constructed from the end to the beginning in the following way. First
the adversary assume a verifier's challenge and according to such assumption it
constructs the witness information in order to pass the verification. This means
that in case
=0, witnesses are constructed as specified in the algorithm. On the
other hand, if
e
=1, then the simulator builds false witnesses from artificial ma-
trices whose product is
e
M
A
, or matrices from the set but such that their product
is not
M
A
. In both cases the simulator may use its knowledge of all the factor
matrices in order to pass successfully the verification. Note that the fact that the
challenges
's are chosen by Bob randomly and independently in each iteration
of the protocol is of particular importance because otherwise Alice could take
advantage of it.
e
5 Performance of the Scheme
The proposed scheme achieves limited computing time and storage space both
on the user's side and on the verifier's side, and affordable communication com-
plexity.
It might be thought that the proposed scheme requires a large amount of
memory and time of computing, but this is not accurate in case the integer entries
of all the matrices are upper bounded, because the operations to perform are very
simple and can be implemented in hardware in a quite ecient way. Concretely,
the heaviest part of Alice's computing load is to compute the product of matrices,
but note that this product can be computed eciently through the algorithm
proposed in [22]. Anyway, since Alice's computations may actually take place
on a portable device with limited computation power, obtaining those products
may be troublesome for large values of
, so in such a case this parameter should
also be adequately chosen in the first variant of the protocol. Anyway, note that
in general the computation of successive products can be done taking advantage
of previous results.
Regarding storage space, in each recursive iteration Alice can store only in-
termediate results so the complete identification scheme can be implemented
using small storage space.
In order to limit communication complexity, a non-interactive version based
on a commitment on the challenges may be proposed. In such a case, all random
choices of both participants could be done at the beginning and sent through a
Secret Interchange Protocol or simply by committing to them through a hash
function. In both cases, after that, the only necessary interaction is A's response
to every B's challenge, that had been previously sent.
Finally, note that a practical advantage of the described scheme is that it
allows to add easily new users to the identification system.
r
6 Conclusions and Open Problems
The main objective of this work is the proposal of a hard-on-average problem as
base for a new zero-knowledge proof, which allows its application for the design
