In the article (https://eprint.iacr.org/2009/571.pdf, pag 8) of Smart and Vercauteren, it is mentioned that the recovery of the private key is an instance of the small principal ideal problem. But I dont see how this is possible, since this implies that we know the ring in which we work, i.e. we know the polynomial $F$ chosen in the KeyGen() algorithm. But this is not public information. Am I getting this the wrong way ?

  • $\begingroup$ The polynomial $$F$$ defining the ring must be public, or an encrypter can't do the operations required to encrypt. $\endgroup$ – Chris Peikert Jan 17 '15 at 13:34
  • $\begingroup$ Can you be more specific? From what I understand the encryption only requires $p$ and $\alpha$: $$c=C(\alpha) \mod p$$ The only place where $F$ appears is in the KeyGen(), and I think the encryptor must not know its parameters $\endgroup$ – Radu Titiu Jan 19 '15 at 9:23
  • $\begingroup$ To run Mul requires knowing F, because one must reduce the product of ciphertexts modulo F. Also, one cannot encrypt without knowing the degree of F. It is definitely intended that the ring is public. $\endgroup$ – Chris Peikert Jan 19 '15 at 13:53
  • $\begingroup$ Actually you only need to know $p$ in order to run Mul and Add.Please check the pdf above. You are right about the degree of $F$, but $F$ could be kept secret and still get a correct scheme. $\endgroup$ – Radu Titiu Jan 20 '15 at 8:20
  • $\begingroup$ No, you really need to know F, they just aren't explicit about it in the notation. The reason is that you need to reduce mod F when you multiply, or the degree blows up and the scheme is not compact. $\endgroup$ – Chris Peikert Jan 21 '15 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.