D. J. Bernstein
Authenticators and signatures

Faster batch forgery identification

Papers

[badbatch] 20pp. (PDF) Daniel J. Bernstein, Jeroen Doumen, Tanja Lange, Jan-Jaap Oosterwijk. Faster batch forgery identification. Document ID: 3bde3ab884b9aa2995cb5589e3037232. URL: http://cr.yp.to/papers.html#badbatch. Date: 2012.09.19.

Software

Typical usage:
     python boscoster2.py 8
Output:
     0.963 *nb additions; b= 128 bits security; n= 8 signatures; 0 forgeries
     3.759 *nb additions; b= 128 bits security; n= 8 signatures; 1 forgeries
     3.757 *nb additions; b= 128 bits security; n= 8 signatures; 2 forgeries
     3.761 *nb additions; b= 128 bits security; n= 8 signatures; 3 forgeries
     3.751 *nb additions; b= 128 bits security; n= 8 signatures; 4 forgeries
     3.761 *nb additions; b= 128 bits security; n= 8 signatures; 5 forgeries
     3.739 *nb additions; b= 128 bits security; n= 8 signatures; 6 forgeries
     3.739 *nb additions; b= 128 bits security; n= 8 signatures; 7 forgeries
     3.735 *nb additions; b= 128 bits security; n= 8 signatures; 8 forgeries
Each line of output reports one experiment, verifying 8 signatures with exactly the specified number of forgeries. The experiments are correlated: each experiment is obtained from the previous experiment by replacing one valid signature with a forgery.

separate.py: simplest benchmarking example. Each signature is verified separately by signatures.isvalid, which uses a naive binary algorithm.

separate2.py: similar to separate.py, but replacing signatures.isvalid with an explicit double-scalar multiplication. The double-scalar multiplication uses a naive binary algorithm.

separate3.py: similar to separate2.py, but using a reasonable double-scalar-multiplication algorithm, fewer than 3nb additions.

batch.py: similar to separate3.py, but starting with a randomized batch signature verification. The randomized batch signature verification uses a naive binary algorithm for multi-scalar multiplication, so this uses more additions than separate3.py even if the batch verification succeeds.

boscoster.py: similar to batch.py, but using the Bos--Coster algorithm (with linear scans) for multi-scalar multiplication. For 0 forgeries this uses far fewer additions than separate3.py, and the number of additions goes down as the batch size increases. For 1 or more forgeries this is slower than separate3.py.

boscoster2.py: similar to boscoster.py, but using heaps instead of linear scans. Same number of additions but less overhead.

straus.py: similar to batch.py, but using the Straus algorithm for multi-scalar multiplication.

straus2.py: similar to straus.py, but using signed digits in the Straus algorithm.

straus3.py: similar to straus2.py, but using randomized signature verification for left and right halves recursively, with reuse of precomputed multiples. Faster for 1 forgery (if the batch size is large enough) but slower for many forgeries.

straus4.py: similar to straus3.py, but replacing leaf verifications by reuse of precomputed multiples.

straus5.py: similar to straus4.py, but also reusing precomputed sums of precomputed multiples.

straus6.py: similar to straus5.py, but computing right V from top V and left V.

Lower-level libraries

signatures.py: group definition, signatures, naive binary signature verification, benchmarking.

doublescalarmult.py: reasonable double-scalar-multiplication algorithm.