For Full-Text 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.
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
Publication Date: 1995/09/25
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>>
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.