Batch DSA

[Anonymous <nobody@REPLAY.COM>]

Batch DSA

Amos Fiat invented a way to do multiple RSA signatures using only one
full-sized exponentiation [J Cryptology v10 n2 p75].  The trick is to
sign each one with a different RSA key, where the keys all share the
same modulus n but differ in their public exponents e.

A similar technique allows DSA signatures to be batched.  As with
Batch RSA, each message ends up being signed with a different DSA key,
where the keys share the same p, q, and g values, but differ in their
public y values, where y = g^x mod p for a secret x.

These techniques may be useful for situations where heavily loaded servers
need to digitally sign many responses.

A DSA signature on a message M (where M is the hash of the actual data)
is done as follows:

	Choose a random value k.  k must be different for every signature.
	Calculate R = g^k mod p mod q.
	Calculate S from S*k = M + R*x mod q.

Then (R, S) is the signature.

The time consuming part of this is the calculation of g^k.  This is the
only exponentiation which must be done.  All the other calculations can
be very fast.

We can't re-use a k value because it allows x to be discovered very
easily.  If two signatures (R, S_1) and (R, S_2) use the same k value,
we have (mod q):

	S_1*k = M_1 + R*x
	S_2*k = M_2 + R*x

The capitalized values are known, the lower case k and x are the unknowns.
We have two equations in two unknowns, which allows us to recover k and x.

If different x values are used for each signature, then it should be safe
to re-use k.  This is how Batch DSA would work.

The signer would publish his public key as p, q, and g as usual, but now
he would publish multiple y_i = g^x_i values.  The convention is that
any message is considered signed by the key if it is signed by any of the
y_i.

To sign a batch of messages, one k value is used for all of them.  The
same calculation as above is used:

	R = g^k mod p mod q  (same for all)
	S_i * k = M_i + R * x_i mod q

The signature is (R, S_i, i), where the index i is included to tell the
verifier which y_i to use.

This is not vulnerable to the problem above of re-using k.  The multiple
signatures have the relationships:

	S_1*k = M_1 + R*x_1
	S_2*k = M_2 + R*x_2
	S_3*k = M_3 + R*x_3
	...

We always have more unknowns than there are equations, which hides the
values of k and x_i.

This same technique can be applied to most other discrete log signatures,
which generally have the same structure although they differ in the details
of how x and k are used to construct R and S.

With Batch RSA, there is a tradeoff between batch size and efficiency.
The calculations become inefficient for batch sizes larger than tens
of messages when keys are about 1K bits.

Batch DSA can efficiently handle larger batches, but it has a tradeoff
between batch size and key size.  Each key variant requires specifying a
full-sized y value, while with Batch RSA the variants just required
listing a small e value (and possibly not even that, if the exponents
are the small primes).  This will limit Batch DSA in most circumstances
to similar batch sizes of on the order of tens of messages, otherwise
the keys become unreasonably large.