votingworks / electionguard-kotlin-multiplatform

An implementation of ElectionGuard version 2.0.0 in Kotlin.
MIT License
9 stars 5 forks source link

add support for EG 2.0 encryption #38

Closed danwallach closed 2 years ago

danwallach commented 2 years ago

EG 2.0 encryption changes from using the generator as the base for encoding the 0-or-1 counter to using the public key. This ultimately removes the need for one of the modular exponentiation operations in the disjunctive Chaum-Pedersen proof.

Changes that will be required:

danwallach commented 2 years ago

All the changes for the new ElGamal and the new Chaum-Pedersen proofs are merged. What's next is the "Montgomery form" optimizations, which will speed up the PowRadix table derivation as well as operations using it.

Among other sub-tasks, this will require updating libhacl to get the new features here: https://github.com/project-everest/hacl-star/blob/master/dist/gcc-compatible/Hacl_GenericField64.c

danwallach commented 2 years ago

Montgomery form now works correctly and yields ~30% speedup for JVM. Doing it for HACL is going to require pulling in a more C code from HACL and possibly switching from the "Hacl_Bignum4096" type to the "Hacl_Bignum64" type, which then supports arbitrary lengths and which we can use "Hacl_GenericField" code to convert to and from Montgomery form.

danwallach commented 2 years ago

Linked in the full HACL distribution rather than the "election-guard" subset used in electionguard-cpp. All existing tests pass. Also replaced our code for PlatformNative.kt to use a function provided by HACL that does the correct thing on Windows and Unix, including using the SYS_getrandom syscall on Linux (which has existed since 2014).

danwallach commented 2 years ago

Next steps:

danwallach commented 2 years ago

Oh, and for some reason montgomeryFormMultiplication3072() fails the tests right now. The fix for this should fall out of the switch away from HaclBignum4096.

danwallach commented 2 years ago

63 largely addresses this issue. We still need to sort out partial encryptions & decryptions.

JohnLCaron commented 2 years ago

Tests are passing. I think this can be closed, do you agree danwallach?