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

概要

論文の詳細を見る
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.
社団法人電子情報通信学会の論文
1995-09-25