9 January 1998
See related: Batch RSA and Batch RSA for Stego Data

    Date: Fri, 9 Jan 1998 20:35:11 +0100 (MET)
    From: Anonymous <nobody@replay.com>
    Subject: Batch DSA
    To: cypherpunks@cyberpass.net, coderpunks@toad.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.