Information Security, Web, Networks and Systems

Wednesday, December 10, 2014

A Digital Signature Batch Verification Scheme for ElGamal

Batch Screening is a scheme which is used with  ElGamal Signature Scheme to improve the performance of verifying large number of signed messages. In Batch screening, a batch of messages is taken together and verified all at once other than verifying each of them individualy which is the standard method. Following is an implementation of a Batch Screening system for ElGamal Signature scheme implemented in Python.
Source Code can be found at github here.

Signing Messages

A random number k (1<k<p-1 and gcd(k,p-1)=1) and the message to be signed to the function. Hash of the message is calculated using MD5 hash function which is used to create the signature. Signature is created as a tuple (r,s) where,
In my implementation, I have created 20 such distinct messages and signed each messages by calling the sign() function. These messages and signatures are then passed to each functions, singleVerify() and batchVerify() for per-message signature verification and batch screening.

Per-message signature verification (singleVerify() function)

In per-message signature verification, each message is verified individually. If all messages are verified successfully, final result would be returned as True, otherwise False. Verification is done as follows:

Batch Verification (Screening)

In Batch Screening, a batch of messages has been taken at once and verified at once. In this case, I have used the Batch size as 10, hence 10 messages will be verified at once. If all messages are signed properly and integrity not lost, batchVerify() will return true. Even if a single message in the batch is modified, verification will fail for the entire batch of messages. Batch verification is done as follows:
Condition for single message  signature verification is 
For each m_i message in a set of n messages, condition should be, 
For the entire batch of messages,
An attacker could manipulate adjascent messages so that their changes cancel out in batch verification. This might cause an attack on message integrity getting unnoticed. To prevent this, we need to select a batch of message-signature pairs randomly rather than selecting them sequencially for a single batch. 
I used a random function to select messages randomly as follows:         

On each batch of messages, validation,
             is calculated and final result for the batch will be returned as True if validation successful for each batch.


Using python time.time() function, I calculate the time it took for each two methods, Single message signature verification and batch screening and plotted the results. 
According to the graph, we can notice that the time it took to verify all the messages clearly differ in two schemes. This shows that we can gain a significant performance improvement when Batch Screening is used to verify large number of messages rather than individually verifying messages.
On average, I could notice that Batch screening took 343.224208 µs to verify 20 messages with MD5 as the hashing scheme and with batch size 10. When each message individually verified, it took 800.329844 µs on average for verification. We can clearly see that we have an improvement in verification time by 457.105637 µs on average when Batch screening is used instead of the standard method.

Following graph shows the difference between average verification times for each scheme.
Following is the change of Batch Verification time (average) with respect to Batch Size chosen. I changed the batch size by 50 each time and measured the verification time for 1000 messages. It can be noticed that Batch Verification time decreases as the batch size increases. However the rate of decrease decreases as batch size increases.
Following graph shows how Total time for verification changes as the Total message count increases. We can identify that increase of verification time is high in Individual message signature verification compared to batch screening. In this experiment, batch size was kept fixed at 10.
By above results, we can conclude that Batch Screening significantly improves the performance of ElGamal Signature scheme when there are multiple (preferably large number of) messages are to be verified for Digital Signature. As the number of messages increases, benefit of using Batch screening becomes very larger than that of Individual signature verification.


  1. Thanks for the nice blog. It was very useful for me. Keep sharing such ideas in the future as well. This was actually what I was looking for and I am glad to come here! Thanks for sharing such a valuable information with us Digital Signature Certificate

  2. Finally I found something useful to me. I have been looking for information on this particular topic for a lot of time now. I can't believe it is this difficult to find something on the Internet like this. I must be looking for the wrong thing or I don't know how to use Google. Anyway, thanks a lot for making this post available to us.Digital Signature Certificates

  3. Thanks for sharing digital signature information for dsc clients. I am just see your blog and share social site. I like you blog post.
    e-Procurement Digital Signature, e-Procurement Digital Certificate


Note: Only a member of this blog may post a comment.