A Secure Key Authentication Scheme Based on the Hardness of Solving Elliptic Curve Discrete Logarithm Problem

Abstract

A key authentication scheme is a scheme that protects a user’s public key from modification and counterfeiting by an adversary. The new development and improvement of key authentication schemes should be made continuously so that the systems are safe and practical to be used. To the best of our knowledge, there is no key authentication using the elliptic curve so far. Thus, in this paper, we propose the first secure elliptic curve-based key authentication scheme with its security, relying on the difficulty of solving the elliptic curve discrete logarithm problem. We show that the proposed scheme is secure against various defined cryptographic attacks such as public keyword modification and keyword guessing attacks. Next, we analyze the computational time complexity of the algorithms by computing the number of modular operations needed in these algorithms together with asymptotical analysis of running time using O(g(n)) notation. It turns out that our scheme requires the least amount of time complexity of 203.36T_mul + T_h for user registration phase, 58.12T_mul for key authentication phase, and offers less running time compared to some existing key authentication schemes.