A question about safe primes

[xcshuan]

Due to performance issues in the browser environment, it is not practical to use safe primes in wasm, and all tss-ecdsa schemes recommend safe primes, but I have seen some discussions that safe primes do not seriously affect security.

https://security.stackexchange.com/questions/73505/use-of-safe-prime-in-rsa-digital-signature-scheme
https://acsc.cs.utexas.edu/libpaillier/
https://crypto.stackexchange.com/questions/47729/safe-primes-in-rsa

Not sure what you guys think about this, given that wasm environments can only use schemes that are not safe primes.

[tmpfs]

Hi @xcshuan,

I think those links show there is not yet consensus amongst cryptographers regarding safe primes and ultimately we are constrained by the WASM runtime environment.

It would be worth benchmarking with and without safe primes to see how much it impacts performance; if you want to create a benchmark you could try the library we use for gg20, the code is here: https://github.com/ZenGo-X/multi-party-ecdsa/blob/master/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L138-L140.

The function for generating a Paillier keypair using safe primes is here: https://docs.rs/kzen-paillier/latest/kzen_paillier/traits/trait.KeyGeneration.html#method.keypair_safe_primes

Currently, we had to use several workarounds to support threads and ideally we would like to remove threads so we can run in single-threaded environments where Worker is not available so if you do try some benchmarks I suggest running them on a single thread.

Let us know if you learn anything about the performance impact of safe primes and thanks for raising the issue!

[tmpfs]

Also, the note here indicates it is recommended by ZenGo:

https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L179-L199

However it's interesting to notice that create_safe_prime() calls generate_h1_h2_N_tilde() which in turn is not using the safe prime function from Paillier so I think it is worth asking Zengo about that.

[tmpfs]

Created an issue to learn more about this inconsistency, see: ZenGo-X/multi-party-ecdsa#178