2
$\begingroup$

The secret key of BFV, BGV schemes is generated as a random ternary polynomial from R2 ( R2 is the key distribution used to sample polynomials with integer coefficients in {−1,0,1}) Is there any specific reason for it to be a ternary polynomial? can we have it as polynomial from Rq i.e integer coefficients from {0, 1, 2, 3, ..q-1} and still have all the guarantees of being post quantum secure?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Actually, if you sample the secret key (sk) from larger sets, you increase the security of the underlying problem (RLWE).

You can test it by yourself on the Lattice estimator, by keeping N and q fixed, then trying several distributions for sk.

So, it would be better to have an FHE scheme that uses sk sampled uniformly from $\mathcal{R}_q$. However, for schemes like BGV, CKKS, FV, in some operations, we have to divide the ciphertexts by some integer and round, and these operations increase the noise in a way that depends on the norm of sk.

For example, in BGV, there is the modulus switching. You can see that the noise after this operation depends on $||sk||$.

So, to reduce the noise growth due to these operations, we just set $||sk|| = 1$, which we can do by having ternary sk.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you. just realized in original FV paper, they were not using ternary sk but just {0.. q-1}. Seems this development came later. $\endgroup$
    – Kaneez sk
    Dec 22, 2022 at 18:54
  • $\begingroup$ @Kaneezsk Where did you see that FV used uniform secret keys? I will be very surprised if this is correct... $\endgroup$
    – Hilder Vitor Lima Pereira
    Dec 23, 2022 at 21:41
  • $\begingroup$ not exactly {0,..q-1} but eprint.iacr.org/2012/144.pdf 2.2 and 3.2 indicate that it is uniform in [-B, B] $\endgroup$
    – Kaneez sk
    Dec 24, 2022 at 22:02
  • $\begingroup$ @Kaneezsk yes, that is fine. They are just saying that they assume the secret key to have small norm, bounded by B (for the reasons I explained here, since the noise depends on the norm of the key). But they even say that as an optimization, one can set $|||sk|| = 1$ $\endgroup$
    – Hilder Vitor Lima Pereira
    Dec 26, 2022 at 7:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.