
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Strong Identification Based on a HardonAverage Problem
Pino CABALLEROGIL
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E88A
No.5
pp.11171121 Publication Date: 2005/05/01
Online ISSN: Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: cryptography, computational complexity, algorithms, discrete mathematics,
Full Text: PDF(101.3KB) >>Buy this Article
Summary:
The aim of this work is to investigate the possibility of designing zeroknowledge identification schemes based on hardonaverage problems. It includes a new twoparty identification protocol whose security relies on a discrete mathematics problem classified as DistNPComplete under the averagecase analysis, the socalled Distributional Matrix Representability Problem. Thanks to the use of the search version of the mentioned problem, the zeroknowledge property is formally proved by blackbox simulation, and consequently the security of the proposed scheme is actually guaranteed. Furthermore, with the proposal of a new zeroknowledge proof based on a problem never used before for this purpose, the set of tools for designing cryptographic applications is enlarged.

