A New Approach to Constructing a Provably Secure Variant of Schnorr's Identification Scheme

Satoshi HADA  Hatsukazu TANAKA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.9   pp.1154-1159
Publication Date: 1995/09/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
interactive identification scheme,  provable security,  Schnorr's scheme,  Okamoto's scheme,  

Full Text: PDF(472.6KB)>>
Buy this Article

Schnorr's identification scheme is the most efficient and simplest scheme based on the discrete logarithm problem. Unfortunately, Schnorr's scheme is not provably secure, i.e., the security has not been proven to be reducible to well defined intractable problems. Two works have already succeeded to construct provably secure variants of Schnorr's scheme. They have been constructed with a common approach, i.e., by modifying the formula to compute the public key so that each public key has multiple secret keys. These multiple secret keys seem to be essential for their provable security, but also give rise to a penalty in their efficiency. In this paper, we describe a new approach to constructing a provably secure variant, where we never modify the formula, and show that with our approach, we can construct a new efficient provably secure scheme.