Re: Batch verification via Pippenger's algorithm

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
and Vector Addition Chains," EUROCRYPT '94, 1994 proposes the
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