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?
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]) ?
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.
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.