# Re: Batch verification via Pippenger's algorithm

*From*: "daniel bleichenbacher" <daniel_bleichenbacher@xxxxxxxxx>*Date*: 28 Mar 2007 00:10:23 -0700

On Mar 28, 2:18 am, "D. J. Bernstein" <d...@xxxxxxxx> wrote:

Let's look at a typical elliptic-curve signature system within the

ElGamal/Schnorr/DSA/etc. family:

* Everyone knows a standard base point B of prime order on an

elliptic curve. Let's say the order #<B> of B is around 256 bits.

* The sender knows a secret key n mod #<B>.

* Everyone knows the sender's public key, compressed nB, let's say

256 bits.

* Everyone knows a hash function H, at least 128-bit output.

* The sender signs a message m by choosing a random number z mod #<B>

and sending (m,compressed zB,(H(zB,m)z+n) mod #<B>).

* The receiver checks (m,compressed Q,t) by checking tB = H(Q,m)Q+nB.

This is the system proposed in September by Matthijs van Duin. It isn't

a completely arbitrary choice of signature system within the family; I'm

deliberately avoiding some of Schnorr's ideas, because those ideas are

incompatible with the speedups discussed below. I'm also ignoring

RSA/Rabin-type systems, which provide much faster verification but need

longer keys and longer signatures.

Consider a verifier that receives, in parallel, (m_1,compressed Q_1,t_1)

and (m_2,compressed Q_2,t_2) and so on. Bellare, Garay, and Rabin

(Eurocrypt 98) suggested verifying all the equations

t_i B - H(Q_i,m_i) Q_i - n_i B = 0

by verifying a linear combination of the equations:

(sum_i r_i t_i) B - sum_i r_i H(Q_i,m_i) Q_i - sum_i r_i n_i B = 0.

Here the r_i's are reasonably long (say 128 bits) and chosen randomly by

the verifier (for example using a hash of a secret key and the inputs,

or simply reusing previous r_i's that were kept secret). There were

subsequent complaints about the reliability of the linear-combination

test, but one can guarantee reliability at low cost by inserting a

cofactor in front of Q_i and checking that Q_i is in the base field.

Anyway, let's say there are v messages to verify. The linear combination

then has v points Q_i; v public keys n_i B (or fewer if some public keys

appear more than once); and 1 base point B. Verification now boils down

to a 256-bit (2v+1)-scalar multiplication. How quickly can we do this?

(If the verification fails---as it will if an attacker is sending many

forgeries to consume all available CPU time---then there are extra costs

to locate and eliminate the forgeries. But let's ignore these costs and

consider the situation that verification practically always succeeds.)

The obvious answer is Pippenger's 1976 exponentiation algorithm, which

uses 256 doublings and roughly 512v / lg(8v) additions. (Probably fewer

when one takes into account negations, the size of r_i, etc., but I

haven't done experiments yet.) For example, if v = 32 then the algorithm

uses 256 doublings and roughly 2048 additions; i.e., for each message, 8

doublings and roughly 64 additions. This is maybe four times faster than

doing a separate 2-scalar multiplication for each message. The advantage

grows as v grows.

But this isn't what Bellare, Garay, and Rabin said in 1998. They

proposed a naive binary algorithm that uses many more additions, and

then a more complicated "Bucket Test" that scales better than the naive

binary algorithm as v grows past 200 but that doesn't seem competitive

with Pippenger's algorithm.

Has anyone previously considered Pippenger's algorithm in this context?

I've seen quite a few complaints about signature-verification speed, and

I've seen very little use of batch verification; I wonder whether the

superior performance of Pippenger's algorithm would attract more

attention to batch verification.

---D. J. Bernstein, Professor, Mathematics, Statistics,

and Computer Science, University of Illinois at Chicago

Other addition chain algorithms should be considered too.

I.e. the paper by Peter de Rooij, "Efficient Exponentiation using

Precomputation

and Vector Addition Chains," EUROCRYPT '94, 1994 proposes the

following

method to generate an addition chain for a set S of integer:

Let a and be the largest rsp. second largest element in S.

Represent a = kb+c. (Usually k will be 1).

Let S' be the set derived from S by removing a and inserting c.

Recursively, find an addition chain for S'.

My experience is that de Rooij's algorithm is frequently better than

Pippenger's algorithm.

Daniel Bleichenbacher

.

**References**:**Batch verification via Pippenger's algorithm***From:*D. J. Bernstein

- Prev by Date:
**Re: Large-Number Math DLL?** - Next by Date:
**Re: Primitive polynomials in extended Galois fields** - Previous by thread:
**Batch verification via Pippenger's algorithm** - Index(es):