Score:2

Does the secret key in homomorphic encryption schemes like BFV, BGV schemes have to be from {-1,0,1}?

gw flag

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?

Score:0
us flag

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.

Kaneez sk avatar
gw flag
Thank you. just realized in original FV paper, they were not using ternary sk but just {0.. q-1}. Seems this development came later.
Hilder Vitor Lima Pereira avatar
us flag
@Kaneezsk Where did you see that FV used uniform secret keys? I will be very surprised if this is correct...
Kaneez sk avatar
gw flag
not exactly {0,..q-1} but https://eprint.iacr.org/2012/144.pdf 2.2 and 3.2 indicate that it is uniform in [-B, B]
Hilder Vitor Lima Pereira avatar
us flag
@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$
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.