Is there a method to break an EC curve for all key-pairs (Q,d) such that (Q=d*G) faster than breaking every single key-pair? I've read baby-step giant-step algorithm for solving the discrete log and it uses a pre-computed table that can be reused to break following keys, but I don't know how the cost of building the table relates to the total cost of the algorithm. If building the table is 99% of the required time, then one can break 100 keys at the price of one.
I don't see how Pollard's rho algorithm for logarithms can be optimized to break many key-pairs at the price of one.
What is the signature scheme with the fastest batch verification protocol for multiple signers? Excellent review! But if you need to verify, say, 10000 signatures, then batching can really impact performance. I'm trying to figure out a scheme where verification of a batch of n signatures is O(1) or O(log n) "slow" operations (e.g. modexp) and O(n) "fast" operations (e.g. multiplication). Sadly I think such as scheme does not exists.
meta user
network profile
