Digital Signature Screening Scheme

To sign a message m ElGamal signature scheme, the signer performs the following steps.

The pair of (r,s) is the digital signature for message m. So generated the signature can be verified by using the below steps.

To speedup the verifying procedure, we can use batch verification scheme called screening. When verifying a batch of signed messages by a single signer, without calculating each and every g^H(m_i) separately, we calculate the sum of all H(m_i) values and raise it to the power of g , and verify all messages at once. That is calculating g^{H(m₁) + H(m₂) + .. + H(m_n)} and check the verifiability of all messages at same time.

If a single signature is tainted in the transmission, this procedure will capture it. But if two or more messages are tainted, error in each may cancel out. So we have to take random subsets when performing the test.

Lets see how we can do this using Java. First we generate keys and sign 10 messages.

// Key Generation
Random rand = new SecureRandom();
BigInteger secretKey = new BigInteger("12345678901234567890");
BigInteger q = BigInteger.probablePrime(64, rand); // select q, probably an integer
BigInteger g = new BigInteger("3"); // g integer
BigInteger Y = g.modPow(secretKey, q); // y = g^x mod q

//generate 10 messages
int range = 10;
Random rn = new Random();
String[] message = new String[range];
 
for(int i=0; i<range; i++){
 message[i] = rn.nextInt((int) Math.pow(2, 64))+"";
}
  
// Sign
BigInteger[] rs = new BigInteger[message.length];
BigInteger[] signs = new BigInteger[message.length];
BigInteger m, k;
for (int i = 0; i < message.length; i++) {
 m = new BigInteger(message[i]);
 k = BigInteger.probablePrime(64, rand);
 rs[i] = g.modPow(k, q);
 signs[i] = ((new BigInteger(m.hashCode() + "")).subtract(secretKey
     .multiply(rs[i]))).multiply(k.modInverse(q
     .subtract(new BigInteger("1"))));
}

Now we can see how the normal verification works.

// Normal Verification
BigInteger rhs, lhs;
for (int i = 0; i < message.length; i++) {
 rhs = g.modPow(
   new BigInteger((new BigInteger(message[i])).hashCode() + ""),
   q);
 lhs = Y.modPow(rs[i], q).multiply(rs[i].modPow(signs[i], q)).mod(q);
 if (rhs.equals(lhs)) {
   System.out.println("Signature " + (i+1) + " : verified");
 } else {
   System.out.println("Signature " + (i+1) + " : not verified");
 }
}

This is how the batch verification is done.

// Batch Verification
int randomNum = rn.nextInt(range);
  
BigInteger sumhm1 = new BigInteger("0");
BigInteger lhsMultiplication1 = new BigInteger("1");
 
BigInteger sumhm2 = new BigInteger("0");
BigInteger lhsMultiplication2 = new BigInteger("1");
 
//divide into 2 subsets
for (int i = 0; i < message.length; i++) {
 if (i < randomNum) {
  sumhm1 = sumhm1.add(new BigInteger((new BigInteger(message[i]))
   .hashCode() + ""));
  lhsMultiplication1 = lhsMultiplication1.multiply(Y
   .modPow(rs[i], q).multiply(rs[i].modPow(signs[i], q))
   .mod(q));
 }else{
  sumhm2 = sumhm2.add(new BigInteger((new BigInteger(message[i]))
   .hashCode() + ""));
  lhsMultiplication2 = lhsMultiplication2.multiply(Y
   .modPow(rs[i], q).multiply(rs[i].modPow(signs[i], q))
   .mod(q));
 }
}
  
//verify subset 1
BigInteger rhs1 = g.modPow(sumhm1, q);
BigInteger lhs1 = lhsMultiplication1.mod(q);

if (rhs1.equals(lhs1)) {
  System.out.println("Batch Screen subset 1 : verified");
} else {
  System.out.println("Batch Screen subset 1 : not verified");
}
  
//verify subset 2
BigInteger rhs2 = g.modPow(sumhm2, q);
BigInteger lhs2 = lhsMultiplication2.mod(q);

if (rhs2.equals(lhs2)) {
  System.out.println("Batch Screen subset 2 : verified");
} else {
  System.out.println("Batch Screen subset  :2 not verified");
}

Lets see results of the work. By verifying 10 messages 10 times using both procedures I got below results.

Average for single message verification = 8386173.8

Average for screening = 6563373.1

So from the results we can see that using batch verification scheme, a noticeable improvement of performance can be achieved.