Since all evaluation in BGV scheme is on polynomials it seems that it does not really matter if the coefficients of the polynomials are within $q$ range or not. All must be okay for the congruent values.

I have the following questions:

  1. If there are no specific optimizations (e.g. RNS) for BGV, can we work in modulo $Kq$, where $K$ is some arbitrary number? Let us ignore encryption/decryption and focus only on adversary side evaluations: additions/multiplications.

  2. If the answer to question 1 is yes, then what optimizations can be affected or broken by working in $Kq$?

  3. Is it the same for BFV scheme?

  • $\begingroup$ Oddy has indicated that the Q is fine now. And yes, this is just a message to bump it up after 3 days of being hidden. $\endgroup$
    – Maarten Bodewes
    Mar 23, 2023 at 10:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.