Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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:
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.
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!)
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.
$\endgroup$
Aug 31, 2011 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.
See, e.g., Bernstein's paper RSA signatures and Rabin–Williams signatures: the state of the art and associated resources, as well as High-speed high-security signatures and A secure public-key signature system with extremely fast verification.
