# What is the signature scheme with the fastest batch verification protocol for multiple signers?

I'm looking for a scheme where signing may be costly (slow) but batch verification with different signers is the fastest possible.

Modified ECDSA allows batch verification for different signers with a 4X speedup [1].

Is there any signature scheme than can do better?

[1] Fast Batch Verification of Multiple Signatures. Jung Hee Cheon and Jeong Hyun Yi

-

There isn't a simple answer, as speed of batching depends on a number of parameters.

First, the speed of the signature and the speed of the batching is largely independent. If you have two signature algorithms S1 and S2 that both permit batching technique B1, then generally they will both permit batching technique B2. If S1 is faster than S2 for individual verification, then S1 with B1 will be faster than S2 with B1. Similarly, if B1 is faster than B2 on S1, it will also be on S2.

Finding the fastest Si+Bi is largely a question of finding the fastest Si and the fastest Bi independently. @Thomas's answer is geared at finding the fastest Si and his point is correct: this is likely to give you the biggest speedup, not finding the right Bi.

To find the fastest Bi, you need to consider a few things:

1. Batch verification is not perfect. If your error tolerance is $2^{-a}$, the fastest batch verification algorithm could differ for a=5 as opposed to a=20 or 60.
2. What happens if there is an invalid signature? Do you throw out the whole batch or just the bad signature(s). Batch verification only detects the presence of a bad signature(s), it doesn't find the bad ones. You need a second group testing algorithm to find the bad signature(s).
3. How many bad signatures are you anticipating? For example, it might be none but you need to verify them to make sure. Alternatively, it might be a whole lot. One known result is that if more than 1/3 of the signatures are bad, individual verification will be faster than any batching technique for finding them.
4. The fastest sequential verification algorithms are not necessarily the fastest parallel verification algorithms.

If you are approaching the problem as someone looking for a solution laid out in the literature, then the paper you cite is essentially state-of-the-art for DSA-style signatures. I wouldn't hesitate is using it.

If you are a researcher that is willing to optimize the verification to the exact requirements of the application, you likely won't find an existing technique that address exactly what you need and you might entertain some of the "fine-print" I've outlined in tailoring an approach specific to your needs.

-

Rabin signatures have a very fast verification algorithm: a simple squaring modulo some integer. RSA signature verification (with a public exponent equal to 3) is also very fast. These signature algorithms are simple to implement and will beat ECDSA for verification speed, even if batch verification is used for ECDSA.

The Niederreiter digital signature scheme should also have a very fast verification (but with a mammoth-sized public key); schemes based on Hidden Field Equations (Quartz and Sflash, notably) also offer a fast verification, albeit with a questionable security (the last decade of research on HFE-based schemes has been a long sequence of break-and-repair cycles). NTRUSign is also supposed to be very fast.

Bottom-line is that ECDSA signature verification is quite slow, compared to other signature schemes (it is still fast in practice, because elliptic curves can be optimized in many ways), so there are many signature schemes which will offer faster verification even without batching.

Another kind of batching can be done with ECDSA, when using a binary curve (a curve defined over the $\mathbb{F}_2^m$ field of characteristic 2, for some $m$) and bitslice code: you represent the complete verification process as a circuit of elementary operations on bits (XOR, AND... ECDSA in a binary field is quite appropriate for that); then you use big registers (e.g. 128-bit SSE2 registers) to perform many such computations in parallel, with bitwise operators (when you XOR together two 128-bit registers, you are performing 128 XOR operations in parallel). Writing out such code is difficult, but can offer some impressive speed-ups; see for instance this article (it will still not beat RSA signature verification, though).

Yet another possible ways to speed up ECDSA is by using Koblitz curves (curves in $\mathbb{F}_2^m$ with equation $y^2+xy=x^3+ax^2+1$ where $a$ is $0$ or $1$) which allow for very fast implementations: the doublings in a double-and-add algorithm can be replaced with simple squarings of both coordinates (in mathematical terms, applying the Frobenius endomorphism), something which can be implemented very efficiently. There are some standard Koblitz curves defined by NIST in FIPS 186-3 (the DSA / ECDSA standard), and the whole thing is described in details in the Guide to Elliptic Curve Cryptography (a very good book which I warmly recommend). Combine that with a recent enough x86 CPU with the AES-NI instruction set (not because of the AES things, but for the pcmulqdq instruction for "carryless multiplication"), and you could get some record-breaking ECDSA code which may be competitive even with RSA verification.

So there are many things which can be done with ECDSA; "mathematical" batching is just one of them, and not the one which may yield the biggest speedup in practice.

-
Excellent review! But if you need to verify, say, 10000 signatures, then batching can really impact performance. I'm trying to figure out a scheme where verification of a batch of n signatures is O(1) or O(log n) "slow" operations (e.g. modexp) and O(n) "fast" operations (e.g. multiplication). Sadly I think such as scheme does not exists. – SDL Aug 30 '11 at 15:01
Well, with Rabin signatures, verifying $n$ signatures is $O(n)$ modular multiplications -- one per signature. There is no actual batching involved, but it does fit your requirements. – Thomas Pornin Aug 30 '11 at 15:14

I'm surprised that Daniel J. Bernstein's EdDSA has not been mentioned.

High-speed high-security signatures

Even faster batch verification. The software performs a batch of 64 separate signature verifications (verifying 64 signatures of 64 messages under 64 public keys) in only 8.55 million cycles, i.e., under 134000 cycles per signature. The software fits easily into L1 cache, so contention between cores is negligible: a quad-core 2.4GHz Westmere veries 71000 signatures per second, while keeping the maximum verification latency below 4 milliseconds.

If we are talking about concrete speed instead of theoretical speed and especially if we are talking about speed on a certain platform only, the specifics of the implementation can not be left out.

If you want to compare implementations on PC hardware in general, eBASH benchmarks public-key signatures as well. It does not benchmark batch verification, but it might give some pointers.

I am unaware of any signature system implementation providing 2128 security that would be faster than the ed25519 implementation for batch verification on PC hardware. But I might be wrong though! Please correct me if you find one! (Okay, mqqsig256 may be, but public keys are nearly 800 kilobytes in size!)

-
Are you sure this is the fastest method for verification? While I don't have the performance measurements to prove it, I would have expected Rabin-Williams mod n to have even faster verification. Corroborating evidence: p.4 of the paper you cite says "Some RSA-type systems provide faster verification [...] [but] for many applications the advantage is outweighed by much slower signatures", which seems to support the expectation that Rabin-Williams (or RSA) will provide faster verification than ed25519. – D.W. Aug 31 '11 at 3:31
On eBASH, ronald3072 is RSA at 3072 bits (roughly the same security level). It seems to be verifying signatures at 178592 cycles per verification (non-batched), which is faster than ed25519 without batching, but not with. I am not debating that Rabin-Williams can be made to provide faster verification than ed25519, I just am not aware of any concrete implementations that do. Also, if the security level can be less than exactly 2<sup>128</sup>, RSA will get significantly faster compared to the alternatives. – Nakedible Aug 31 '11 at 4:50

I recommend you use Rabin signatures. Rabin signatures without batch verification are likely to be faster than most other signatures with batch verification.

Moreover, read Dan Bernstein's work. He has shown how to make Rabin signatures even faster. For standard Rabin signatures, verification requires approximately one modular multiplication modulo n (say, a 1024-bit number). In Bernstein's improved scheme, verification requires approximately one modular multiplication modulo a 128-bit prime, chosen secretly by the verifier. The trick is to check validity of an equation over the integers by checking that it holds modulo a random prime. With this trick, signature verification becomes awfully darn fast.

-