perf: safe-prime generation

[ivokub]

Issue summary

CGGMP paper requires that the ring-Pedersen parameters is a product of safe primes. For security we need to generate 1024 bit safe primes, which is quite time-consuming. One issue is that right now we're using kzen-paillier for generating Paillier keys. It uses fixed number of Miller-Rabin primality checks, but it is more than recommended.

Additionally, we could use https://eprint.iacr.org/2003/186.pdf - right now we sieve p,q individually but the paper recommends an unified sieve, giving potentially 15x speedup

[luca992]

Is this as result of #34 ? I'm using the multi-party-ecdsa implementation here now as if seems it is actually being maintained... But it seems like it is a lot slower now.

[tmpfs]

@luca992, the c-split fixes did have a significant performance impact for DKG (particularly noticeable in webassembly), however I think @ivokub is referring to additional (upcoming) performance impact but happy to be corrected.

For more confidence in the security of this implementation I think we need to prefer correctness over performance.

[luca992]

@tmpfs yeah for sure. There's no point to any of it if it's not secure haha. But it is a bit slow now. On wasm with the config parties: 5, threshold: 2 it is taking about 5 minutes to generate keys now... it was less than one before if I recall correctly... this is when running keygen all on one machine with a round_based Simulation. Is there a faster way to do key gen if I don't care about distributed generation?

Ps I can make a seprate issue if this is not relevant here

[ivokub]

Hi @luca992, yes the tests are now taking longer as we are now sampling safe primes as according to the paper. Additionally, #44 introduces additonal overhead as we fix the protocol in more places.

This issue should make the impact less noticeable. There are two main things which make tests slow - the key generation is run in a single thread and the safe prime generation is not optimal. There is a paper referenced in the first post, which should help with the second. And in practice, keys are generated in parallel which should help with the first.

[luca992]

Just another stat: on wasm in a single threaded simulation doing key refresh from parties: 5, threshold: 2 -> parties: 6, threshold: 2 is takes about 40 minutes

Doing it in a single threaded way with wasm just really isn't realistic anymore

[tmpfs]

@luca992 yeh that's not a sensible thing to do and doesn't reflect real world usage, for my webassembly use case I run each party in separate browser tabs and use playwright to orchestrate.

Chrome and Webkit tend to take about 2-4 minutes (including signing too) but Firefox is crazy slow.

https://github.com/mpc-sdk/framework#end-to-end-tests