Sparse Secret Keys in the Literature

FHE Questions
1

Hi all,

I have a question on the Efficient Bottstrapping with Non-sparse Keys (Bossuat et al, 2022) paper. In Table III, they use a Hamming weight of up to N/2 (N: ring dimension), and not N? Why do we have to leave at least half of the secret key polynomial coefficients zero?

Also, the security guideline does not include the sparse secret keys. Yet, some recent papers in the literature (ex. llm) still use h = 192 or 256 for the Hamming weight of their secret key distribution. Does anyone know how this is possible?

2

This is a highly controversial and minimally-explored question in LWE security.

In short: sparse secret key LWE makes bootstrapping (in most cases) more efficient.

In terms of security, sparse secret key LWE has not yet been broken (at least under the large parameters used in RLWE-based FHE schemes).

I suggest reading Section 2.3 in the security guidelines paper you referenced and checking the cited relevant resources on the topic.

1 Like
3

Hi, I had read the section you mentioned and was still unsure. I see your point on the controversy. Thank you so much.

4

Hi! Just to check if I properly understood: sparse secrets result in better accuracy because of the impact of the secret key during the modulus switching procedure(Lemma 4 of [BGV12]) ?

5

It affects the bootstrapping polynomial evaluation range as explained in Section 5.4 & 6.2 here. The larger the range is, the higher the polynomial degree to get a proper approximation, the costly it becomes.
It also affects the key-switching error, as explained in the Lemma 3.2 here.

1 Like
6

To answer the very first question, the key-space of a ternary key with h nonzero coefficients is {N\choose h}\cdot 2^{h}, and {2^{16}\choose 2^{15}}\cdot 2^{15}\approx 2^{98296} > {2^{16}\choose 2^{16}}\cdot 2^{2^{16}} = 2^{65536}. The standardized ratio of h=2/3N provides a key-space of 2^{103864}, which is \approx5.6\% greater than h=N/2 but has 33\% more non-zero coefficients.

1 Like