electionguard-python
electionguard-python copied to clipboard
Election-Tech-Initiative
🧮 Precompute Exponentiation Tables
Feature Request
Description
Build and use pre-computation tables to speed up exponentiations with base g (the generator) and base K (the election public key). The most important case here uses 8-bit tables which contain all powers of g and K of the form U times 256^V there U ranges from 0 through 255 and V ranges from 0 through 31. Each table will therefore include a total of 8192 entries – each of 4096 bits. This allows any 256-bit exponent of the base to be computed by multiplying together 32 table values.
An ideal implementation would generalize this approach and enable the construction and use of n-bit tables for variable n from, say, 1 through 16.
Expected Benefit
Use of n-bit tables should speed up exponentiations by a factor of up to n.
Possible Architecture
- Load from the file system
- Load from from memory
Corresponding C++ Issue https://github.com/microsoft/electionguard-cpp/issues/184
Is there code for this yet? I've got a hacky version in the VotingWorks fork that seems to yield 2.5x throughput, and that's without the latest ideas from Josh and Olivier.
@danwallach Are you looking for an example or asking if the issue is finished?
The issue is still open and there is no code currently implemented on this.
Got it. I've got prototype code that works pretty well, mostly just makes changes to group.py and the Chaum-Pedersen proof generation. If you want, I can prepare a PR for you, but there's a lot of fun stuff flying around in email that might make things go much faster, at the cost of requiring more complicated code refactoring.