Speed up exponentiation when factorization is available

[adr1anh]

Modular exponentiation is one of the main bottlenecks for the cmp protocols. Using CRT, it should be possible to exploit knowledge of the prime decomposition of N=pq whenever it is available.

Use cases

Paillier

Decryption should be easy to optimize since we already have access to the factorization of N. There are instances where the prover "commits" to data using their own encryption key. Therefore, optimizing encryption would still be beneficial.

One solution would be to convert PublicKey to an interface which would then be implemented by SecretKey as well. In a Round that stores each party's Paillier PublicKey, the host's key could then be set to the SecretKey instead.

The methods that should be optimized are:

• [x] PublicKey.EncWithNonce(...)
• [x] SecretKey.Dec(...)
• [x] Ciphertext.Mul(PublicKey, ...)

ZK Proofs

The above idea would already provide a nice speed up. A similar technique could be used for the pedersen package which would speed up verification. The host's Pedersen parameters would include the factorization of N but would otherwise behave exactly like another party's parameters. For example, we could add pedersen.NewParametersWithFactorization(n,s,t *big.Int, p,q *safenum.Nat), which would return an interface type.

The only area where things may need manual tuning is the computation of the of the ZK response.

Finally, one other solution would be to directly adapt safenum.Modulus to include a factorization, but this would change the semantics of that package beyond what the author may be comfortable with.

[cronokirby]

A solution that would please said author would be to create a simple wrapper around Modulus and Exp in the internal math package, encapsulating this "optional factorization" functionality.