Digital signatures are one of the most elemental cryptographic technologies, and are essential for the modern information society. In digital signature schemes, a random key pair consisting of a public key and a secret key is generated; a signer creates a digital signature for data with the secret key in the signing process; and a verifier checks the validity of the data with the public key in the verification process. Digital signatures have the property that an unlimited number of users can check the validity of data, because the public key can be made public for all users.

In constructing digital signature schemes, we need to assume the infeasibility of a certain computational problem. Currently, there is no computational problem that has proven to be infeasible. Hence, we need to utilize a computational problem such that no polynomial-time algorithm is known for solving it for a long time, and those problems include the integer factoring and discrete logarithm problems. Another approach is to use an NP-hard problem assuming P≠NP. Anyway, it is required to utilize a computational problem that is considered to be relatively infeasible compared to other ones. On the other hand, it is also required that the security parameter of the digital signature scheme is close to a parameter that makes the computational problem infeasible. This is because the security parameter of the digital signature scheme would be large if those parameters were not close.

This paper proposes a new digital signature scheme based on the infeasibility of the computational Diffie-Hellman (CDH) problem. The CDH problem is relatively infeasible compared to problems related to the discrete logarithm problem. In addition, the digital signature scheme in this paper has a constant-size signature and the security parameter of the digital signature scheme is closest to the parameter that makes the CDH problem infeasible for digital signature schemes having such a property. In summary, the digital signature scheme proposed in this paper has the following three advantages: it is based on the infeasibility of the CDH problem; it has a constant-size signature; and the security parameter of the digital signature scheme is closest to the parameter that makes the CDH problem infeasible. From these viewpoints, this paper not only contributes to the development of modern cryptography but is also useful in our modern information society. Therefore, from these achievement, this paper is worthy to receive the IEICE award.