microsoft
`plain_modulus` needs to be coprime with `coeff_modulus`
While trying to use SEAL for a use case where the plain_modulus is the smallest prime of the coeff_modulus_base, I realised that the RNS optimisation implemented by SEAL seems to forbid any case where the plain_modulus and the coeff_modulus are not coprimes.
Is there a way to use SEAL with such parameters ?
~~It is insecure when plain_modulus is a factor/prime in coeff_modulus. They must be coprime.~~
Hi @WeiDaiWD,
Could you elaborate on the security issue of not choosing Q and T as coprime? If so, the standard should be updated because it only specifies that Q and T should be integers. If I am not mistaken, this would have larger ramifications than BFV, such as key-switching keys generated with the RNS gadget decomposition, the base-2 CKKS/BFV scheme, and some scales for the RNS version of CKKS being insecure.
@Pro7ech Thank you so much for pointing that out. @tbrezot Sorry for the confusion. Please ignore that statement. I was wrong and was considering a different kind of "insecure" than leaking message or key.
My thought was that when plain_modulus is a factor of coeff_modulus. I can easily perform modulo Q/T reduction on a ciphertext to wipe the message -- setting it to zero. Now that I think of it, you can always multiply a ciphertext with an encryption of zero to achieve the same.
After checking the code, I believe this coprime requirement is inherited from legacy code. I can try to drop this requirement in a future release.
@WeiDaiWD This is very reassuring :) I suppose however that this requirement remains true for BGV, since in this case the error is multiplied by T.
That's right. SEAL never had BGV before. So I don't really know where this requirement in SEAL came from.
Thanks for these comments.
I think it would be nice to remove this requirement, or at least to talk about it somewhere in the examples or the SEAL documentation. Indeed the only documented requirement for t is that it should be an integer.
This requirement could come from the implementation of the RNS from this paper: https://eprint.iacr.org/2016/510.pdf. It says (cf Lemme 1) that in order to decrypt, a RNS base conversion is done. But this requires the base elements to be pairwise corpime. Hence, since we need to convert from mod q to mod t, t and q need to be coprime.
I found where this requirement is implemented. As you can see, the notation in the comment is quite similar to the one of the article. https://github.com/microsoft/SEAL/blob/88bbc51dd684b82a781312ff04abd235c060163e/native/src/seal/util/rns.cpp#L672
@tbrezot Actually, if T and Q are not coprime then the division by Q/T is easier, since the division by all the primes except T can be done with the generic rescaling/moddown operation. But it is correct that if the technique you refer to is used then it won't work if T and Q are not coprime (Q has to be replaced by Q/T).
You are both right. If I dropped the requirement, I would need to deploy a second mechanism to perform division by Q/T and let SEAL choose either of them at runtime. This is a good suggestion. Please leave this issue open for now.