Cryptography Reference
In-Depth Information
Exercise 22.1.12 Show how to modify the Schnorr signature scheme (with no loss of
security) so that the verification equation becomes
g s 2 h s 1 ) .
s 1 =
H ( m
Example 22.1.13 Suppose a server must verify many Schnorr signatures (using the variant
of Exercise 22.1.12 ), always for the same value of g but for varying values of h . Suppose
that 2 l 1 < r< 2 l (where l is typically also the output length of the hash function). One
strategy to speed up signature verification is for the server to precompute and store the
group element g 1 = g 2 l .
Given a signature ( s 1 , s 2 ) with 0
s 1 < 2 l and 0
s 2 <r one can write s 2 =
2 l s 2 , 1 with 0
s 2 , 0 , s 2 , 1 < 2 l . The computation of g s 2 h s 1
s 2 , 0 +
is performed as the three-
dimensional multi-exponentiation (see Section 11.2 )
g s 2 , 0 g s 2 , 1 h s 1 .
The cost is roughly l squarings and 3 l/ 2 multiplications (the number of multiplications can
be easily reduced using window methods, signed representations etc.).
Schnorr [ 470 ] presents methods to produce the group elements g k without having to
perform a full exponentiation for each signature (the paper [ 470 ] is particularly concerned
with making signatures efficient for smartcards). Schnorr's specific proposals were crypt-
analysed by de Rooij [ 155 ].
22.2 Other public key signature schemes
The Schnorr signature scheme is probably the best public key signature scheme for practical
applications. 2 A number of similar schemes have been discovered, the most well-known
of which are Elgamal and DSA signatures. We discuss these schemes very briefly in this
section.
22.2.1 Elgamal signatures in prime order subgroups
Elgamal [ 177 ] proposed the first efficient digital signature based on the discrete logarithm
problem. We present the scheme for historical reasons, and because it gives rise to some
nice exercises in cryptanalysis. For further details see Section 11.5.2 of [ 376 ]orSection
7.3 of [ 532 ].
Assume that g is an element of prime 3 order r in an algebraic group G . In this section
we always think of G as being the “full” algebraic group (such as
F q or E (
F q )) and assume
2
However, Schnorr signatures are not very widely used in practice. The reason for their lack of use may be the fact that they
were patented by Schnorr.
3
The original Elgamal signature scheme specifies that g is a primitive root in F p , but for compatibility with all other cryptographic
protocols in this topic we have converted it to work with group elements of prime order in any algebraic group.
Search WWH ::




Custom Search