search

axelarnetwork / tofn

A threshold cryptography library in Rust
Apache License 2.0
112 stars 23 forks source link

Implement combined sieve optimization for safe prime generation #141

Closed milapsheth closed 4 months ago

milapsheth commented 3 years ago

Our safe prime generation implementation independently finds a prime q and then checks whether 2q + 1 is also prime. It's known that this is not optimal since various primes q lead to 2q + 1 being divisible by a small prime (for e.g. if q = 1 mod 3). A combined sieve as described here can optimize this: https://eprint.iacr.org/2003/186.pdf The main issue to implement this is that we currently rely on nextprime function provided by GMP, so this optimization would require modifying GMP or rewriting parts of it in Rust.

tarcieri commented 3 years ago

It might be worth checking out glass_pumpkin:

https://github.com/mikelodder7/glass_pumpkin

It implements safe prime generation in pure Rust (backed by num-bigint) using a method similar to OpenSSL, also applying recommendations from the "Prime and Prejudice" paper.

milapsheth commented 3 years ago

Yep, I adapted our implementation from unknown_order and glass_pumpkin. I found that the GMP backend is significantly faster than the pure Rust implementation, so we decided to stick with GMP for now. And since we aren't in an adversarial setting, the recommendations in the Prime and Prejudice paper aren't too concerning.

But, I would certainly like to switch to a pure Rust implementation if we can get close in performance.

tarcieri commented 3 years ago

Good to know.

FYI, I'm collaborating with some people on a @RustCrypto crate for cryptography-oriented big numbers which has been built from the ground up using const generics (i.e. all bignums are fixed-width and stack-allocated) and aggressively leverages const fn to support computing constant values at compile time:

https://github.com/RustCrypto/utils/tree/master/crypto-bigint

It's probably not immediately relevant to your needs and only implements some baseline functionality needed for the elliptic-curve and rsa crates, but if you have any "wishlist" items you'd like to see out of a cryptography-oriented bignum library, we'd love to ensure they're captured:

https://github.com/RustCrypto/utils/issues/453

It seems like perhaps prime and safe prime generation is one we should prioritize, possibly leveraging some code from glass_pumpkin.

milapsheth commented 3 years ago

That would certainly be useful for us. I'm also happy to contribute to it wherever possible.