# Sparse Secret Keys in the Literature

**URL:** <https://openfhe.discourse.group/t/sparse-secret-keys-in-the-literature/1948>\
**Category:** FHE Questions\
**Created:** [March 20, 2025, 2:09pm UTC](https://openfhe.discourse.group/t/sparse-secret-keys-in-the-literature/1948 "2025-03-20T14:09:25Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![seyda](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/seyda/32/397_2.png) [@seyda](https://openfhe.discourse.group/u/seyda)\
**Post date:** [March 20, 2025, 2:09pm UTC](https://openfhe.discourse.group/t/sparse-secret-keys-in-the-literature/1948/1 "2025-03-20T14:09:25Z")

</div>

Hi all,

I have a question on the [Efficient Bottstrapping with Non-sparse Keys](https://eprint.iacr.org/2020/1203.pdf) (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](https://eprint.iacr.org/2024/463.pdf) does not include the sparse secret keys. Yet, some recent papers in the literature (ex. [llm](https://openreview.net/pdf?id=pbre0HKsfE)) still use h = 192 or 256 for the Hamming weight of their secret key distribution. Does anyone know how this is possible?

---

<div class="post-metadata">

**Author:** ![Caesar](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/caesar/32/63_2.png) [@Caesar](https://openfhe.discourse.group/u/Caesar)\
**Post date:** [March 20, 2025, 3:04pm UTC](https://openfhe.discourse.group/t/sparse-secret-keys-in-the-literature/1948/2 "2025-03-20T15:04:44Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![seyda](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/seyda/32/397_2.png) [@seyda](https://openfhe.discourse.group/u/seyda)\
**Post date:** [March 20, 2025, 3:17pm UTC](https://openfhe.discourse.group/t/sparse-secret-keys-in-the-literature/1948/3 "2025-03-20T15:17:54Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![narger](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/narger/32/420_2.png) [@narger](https://openfhe.discourse.group/u/narger)\
**Post date:** [March 20, 2025, 6:25pm UTC](https://openfhe.discourse.group/t/sparse-secret-keys-in-the-literature/1948/4 "2025-03-20T18:25:19Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![seyda](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/seyda/32/397_2.png) [@seyda](https://openfhe.discourse.group/u/seyda)\
**Post date:** [March 20, 2025, 7:40pm UTC](https://openfhe.discourse.group/t/sparse-secret-keys-in-the-literature/1948/5 "2025-03-20T19:40:46Z")

</div>

It affects the bootstrapping polynomial evaluation range as explained in [Section 5.4 & 6.2 here](https://eprint.iacr.org/2020/1203.pdf). 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](https://eprint.iacr.org/2020/1118.pdf).

---

<div class="post-metadata">

**Author:** ![Pro7ech](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/pro7ech/32/301_2.png) [@Pro7ech](https://openfhe.discourse.group/u/Pro7ech)\
**Post date:** [March 20, 2025, 8:23pm UTC](https://openfhe.discourse.group/t/sparse-secret-keys-in-the-literature/1948/6 "2025-03-20T20:23:17Z")

</div>

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.