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 ellipticcurve 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 128bit 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/Rabintype 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 linearcombination
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 256bit (2v+1)scalar multiplication. How quickly can we do this?
(If the verification failsas it will if an attacker is sending many
forgeries to consume all available CPU timethen 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 2scalar 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 signatureverification 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
 Batch verification via Pippenger's algorithm
 Prev by Date: Re: LargeNumber Math DLL?
 Next by Date: Re: Primitive polynomials in extended Galois fields
 Previous by thread: Batch verification via Pippenger's algorithm
 Index(es):
Relevant Pages
