Interactive identification schemes based on the discrete logarithm problem over a field
Mototsugu Nishioka · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1997
Various zero-knowledge identification schemes have been proposed up to now. Of these, zero-knowledge identification schemes based on a discrete logarithm problem over a field like the Beth scheme can accomplish sufficient security with a limited amount of prover secret information and communication time between the prover and the verifier, unlike the Fiat-Shamir scheme. This is because these schemes can reduce the false-right probability per round. However, some exponential calculations that are time-consuming appear in the authentication protocol of zero-knowledge identification schemes based on the discrete logarithm problem over a field. Consequently, for efficient authentication it is necessary to decrease the number of exponential calculations in the authentication protocol. In this paper, we first show that it is possible to decrease the number of exponential calculations in the authentication protocol of the Beth scheme by modifying the ElGamal signature scheme, which is utilized to construct the Beth scheme. (For convenience, we have called the Beth scheme and the modified identification scheme identification scheme 1 and identification scheme 2, respectively.) Second, we give the lower bound for the exponential calculation number χ(X, Y, Ω) which represents the number of exponential calculations in the authentication protocol of the identification and discrete-logarithm-based interactive identification scheme (X, Y, Ω) that is a generalized concept for identification scheme 1 and identification scheme 2, when (X, Y, Ω) satisfies a certain security condition. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(10): 60–77, 1997