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.
doublescalarmult.py: reasonable double-scalar-multiplication algorithm.