Authenticators and signatures

python boscoster2.py 8Output:

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 forgeriesEach 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.