Secure and Practical Tree-structure Signature Schemes Based on Discrete Logarithms

Abstract

In this paper, we present another tree-structure signature scheme based on discrete logarithm problem modulo p, where p is a large prime. The basic signing algorithm is the original ELGmal signature scheme. The scheme attains ideal security, i.e, finding existential forgeries under adaptively chosen message attacks is equivalent to solving the discrete logarithm of any random integer y∈Z∗py∈Zp∗. The scheme is also efficient, it can be implemented almost as efficiently as the original ELGamal signature scheme. We can regard the scheme as an application of ELGamal signature scheme in tree-structure signature schemes.