A provably secure short signature scheme based on discrete logarithms (Q2456500)

The paper presents a discrete-logarithm based signature scheme, which is similar to the \textit{C. P. Schnorr} signature scheme [J. Cryptology 4, No. 3, 161--174 (1991; Zbl 0743.68058)] or the DSA [NIST, Publication 196, Federal Publications Processing Standards (1994)], but with a one-fourth reduction in both the signature length and the verification computation. In the Introduction the author justifies the utility of short digital signatures in low-bandwidth communications, low-storage and low-computations environments, such as smart cards and wireless devices. He also gives an overview of the existent proposals to date. Section 2 presents the new short digital signature scheme. As in the case of Schnorr and DSA schemes the key generation algorithm selects two primes: one large \(p\) and a smaller one \(q| p-1\) (for instance \(q\) with bit length 160, as DSA). The main difference is that the new scheme uses two hash functions \(H,F\), where the image of \(H\) are strings of length one-half the bit length \(n_q\) of \(q\). A signature is given by a pair \((h,s)\), where \(h\) is an output of \(H\) and \(s\) is in \(F_q\), therefore the signature length is \(3/2\cdot n_q\), instead of twice \(n_q\), as for the Schnorr and DSA signatures. In Section 3 the paper describes the security goals of signature schemes and the provable security in the random oracle model and then it gives a reductionist algorithm (Theorem 2) to show that the proposed signature scheme is secure against existential forgery under adaptive chosen-message attacks in the random oracle model. This result shows, in the author's words ``that the security of the proposed scheme is closely, if not tightly, related to the difficulty of solving discrete logarithms''. Section 4 is for Conclusions. The author argues the possibility to use the existing SHA-1 and SHA-512 as the hash functions \(H\) and \(F\) to implement his scheme. If so the length of the obtained signature would be 240 bits.