Performance of safe prime generation order of magnitude worse than openssl

[robinhundt]

First, thanks for the nice library! I'm using it to implement a threshold variant of paillier (code is here https://github.com/robinhundt/pht-crypto but still under construction).
I've noticed that my key generation takes a considerable amount of time due to the generation of safe primes being slow (taking minutes for safe primes of size 2048 bits on my machine). I've noticed that openssl is considerably faster in generating safe primes (using https://docs.rs/openssl/0.10.36/openssl/bn/struct.BigNumRef.html#method.generate_prime ).
If there is interest, I could send a PR with benchmarks comparing the openssl implementation and this one :) Maybe there are some easy improvements which could bring the performance closer to the one offered by openssl.

[mikelodder7]

Consider using https://crates.io/crates/unknown_order
And
https://crates.io/crates/libpaillier

Which already implements paillier commonly used for threshold signing and can switch between OpenSSL and rusts BIGINT library

[mikelodder7]

OpenSSLs big num library is heavily optimized and runs many operations in assembly. I’ve tried to get close to OpenSSL but the problem lies in using rusts big number library not running as fast.

I’m also helping to work on crypto-bigint which should help.

[robinhundt]

Oh, crypto-bigint looks nice, haven't seen that yet!

Ah, I thought that maybe OpenSSL does something different algorithmically to achieve a better performance.. If it's due to the big number implementation, then I guess there is not much that can be done.
I've actually already seen unknown_order and libpallier. I didn't use the first, since I mostly rewrote libhcs threshold paillier implementation which uses gmp, so I went for rug. I might change it to unknown_order though, since I'm not that happy with gmp. As far as I can tell, your paillier implementation can't be used for threshold encryption which is what I need for a project.

Thanks for your reply! 😊

[mikelodder7]

Unknown order can also switch between gmp as well

[mikelodder7]

I’m happy to add threshold capabilities. Just haven’t needed it. There’s better threshold with ECC and faster which is why I haven’t yet

[robinhundt]

Unfortunately I need additively homomorphic threshold encryption for a multi-party protocol. As far as I know, Paillier is the only option (please correct me if I'm wrong 😅).
If you're interested in adding threshold encryption to libpallier, I could maybe write a PR for that. I'll open an issue in the repository for that.

[mikelodder7]

Yes please do. Happy to add it to lib paillier