Information Technology Reference
In-Depth Information
NP-complete problems may be eciently solved when the instance is randomly
generated [14]. So, one of the most immediate solutions in cryptography is to
choose as base problems those whose diculty is guaranteed by the average-case
analysis. In this paper, the first (to the knowledge of the authors) zero-knowledge
interactive identification protocol based on a problem catalogued as NP-complete
from the point of view of the average-case analysis is proposed. The problem
selected as base for the protocol proposed here is the so-called
Distributional
Matrix Representability Problem
[15] which possesses such a characteristic.
The structure of the present work is as follows. The next section discusses
the underlying problem in the framework of average-case complexity. The zero-
knowledge identification scheme is described in detail in section 3. In sections 4
and 5 the security and performance of the proposed scheme are analyzed. Finally,
several conclusions and open problems close the paper.
2 The Underlying Problem
The average-case analysis is based on the concept of distributional decision prob-
lem [16], which is formed by a decision problem and a probability distribution
defined on the set of instances. In this context, the choice of the probability
distribution plays an important role since to fix a probability distribution could
directly influence the practical complexity of the problem. In fact, it has been
proved the existence of NP-complete problems solvable in polynomial time when
the instances are randomly generated under certain distributions.
The distributional class analogous to NP in the hierarchy associated to the
average-case analysis is the DistNP class. It is formed by pairs containing a de-
cision problem belonging to the NP class and a probability distribution polyno-
mially computable. As in worst-case complexity theory, a distributional problem
is said to be average-case NP-complete (or DistNP-complete) if it is in DistNP
and every distributional problem in DistNP is reducible to it. The first problem
catalogued as DistNP-complete is the distributional tiling problem whose formal
proof of membership may been found in [16]. Later, other works containing the
description of new NP-complete problems have been published [17], [18], [19],
[15].
The main diculty when trying to use problems belonging to this category in
practical applications is the artificiality of their specifications. So, the principal
reason why we have chosen the Distributional Matrix Representability Problem
as base for the Zero-Knowledge Proof here proposed is its naive formulation.
The original Distributional Matrix Representability Problem can be roughly
defined in the following way. All the matrices intervening in the problem are
square and with integer entries. Given an
r × r
matrix
M
and a set of matrices
{M
1
,
M
2
, ..., M
k
}
M
with the same size
can be
expressed as a product of matrices in the given set. This problem was shown to
be average-case NP-complete by Venkatesan and Rajagopalan [19].
In this work also a bounded version of this problem for 20
, it should be decided whether
20 matrices,
defined in [19], is proposed to be used. In this case the instance consists of a
×
