Efficient signature generation by smart cards (Q1180508)

This paper presents a new public-key signature scheme and a corresponding authentication scheme that are based on discrete logarithms. A signature \((e,y)\) for the message \(m\) can be generated according to \(e=h(x,m)\) and \(y=r+se(\mod q)\), where \(r\) is a random number in \(\{1,\dots,q\}\) and \(x=\alpha^ r(\mod p)\), \(s\) is the user's private key, and the prime \(p(\geq 2^{512})\), the prime \(q(\geq 2^{140}\), a divisor of \(p-1)\), \(\alpha\) in \(Z_ p\) with order \(q\) and a hash function \(h\) from \(Z_ q\times Z\) to \(\{0,1,\dots,2^ t-1\}\) (\(t=72\)) are public key of the key authentication center. To verify the signature \((e,y)\) for \(m\) with the user's public key \(v=\alpha^{-s}(\mod p)\) compute \(x'=\alpha^ yv^ e(\mod p)\) and check that \(e=h(x',m)\). This scheme improves the El Gamal signature scheme [IEEE Trans. Inf. Theory 31, 469--472 (1985; Zbl 0571.94014)] in the speed and in the bit length of signatures. Computing \(\alpha^ r(\mod p)\) is done in a preprocessing stage that is independent of the message, and the message-dependent part of signature generation consisting of multiplying a 140-bit integer with a 72-bit integer. Finally, an efficient algorithm that preprocesses the exponentiation of a random residue modulo \(p\) is also presented.