A Digital Signature is an important type of authentication in a public-key (or asymmetric) cryptographic system, and it is in wide use. The performance of an Internet server computing digital signatures online is limited by the high cost of modular arithmetic. One simple way to improve the performance of the server is to reduce the number of computed digital signatures by combining a set of documents into a batch in a smart way and signing each batch only once. This reduces the demand on the CPU but requires extra information to be sent to clients. In this paper, we investigate performance of online digital signature batching schemes and show that significant computational benefits can be obtained from batching without significant increases in the amount of additional information that needs to be sent to the clients. We also give a semi-Markov model of a batch-based digital signature server and its approximate solution. We validate the solutions of the analytical model through both emulation and simulation. Also UMIACS-TR-2002-03