[SPEC] missing Π-mod ZK-proof

[ivokub]

Overview

CGGMP paper defines ZK proof Π-mod (See Fig 16 https://eprint.iacr.org/2021/060.pdf#page=36) for ensuring that the Paillier modulus is a semiprime and gcd(N, phi(N)) = 1. There is an attack which assumes that N has many small factors described at https://www.fireblocks.com/blog/gg18-and-gg20-paillier-key-vulnerability-technical-report.

I tried searching for the implementation of Π-mod in the repository and wasn't able to find it. Does it seem right and if so, should we implement it? Or would it be sufficient if we test N not to have small factors? (for example primes up to 2**20?)

cc @davidsemakula, @tmpfs, @drewstone

[davidsemakula]

@ivokub I think we should implement it, the attack you linked is essentially an unpatched vulnerability for both this library and multi-party-ecdsa.

@drewstone I remember there was some kind of plan to patch it on your side (possibly for another repo if I remember correctly), not sure if that was done already and we can just pull it in?

[ivokub]

Hmm, I think the check is done transitively in FS-DKR. Here we create NiCorrectKeyProof which seems to be implementing https://eprint.iacr.org/2018/057.pdf. CGGMP paper defines PI-mod to be a simplification of 2018/057.

[davidsemakula]

Hmm, I think the check is done transitively in FS-DKR. Here we create NiCorrectKeyProof which seems to be implementing https://eprint.iacr.org/2018/057.pdf. CGGMP paper defines PI-mod to be a simplification of 2018/057.

On closer inspection, I agree, it's also checked in GG20.

So for this Fireblocks report, it looks like its only the Lindell17 implementation for multi-party-ecdsa that was vulnerable to this attack https://www.fireblocks.com/blog/lindell17-abort-vulnerability-technical-report?

On closer look again, I think it's vulnerable since this check is not for the auxiliary modulus $\tilde N$