# CKKS Security Parameters Randomization appears when generating secret and public keys, and during encryption. ## Secret key Secret key is sampled uniformly from the subset of $\{0,\pm1\}^N$ with Hamming weight $h$ i.e., the number of non-zero element is exactly $h$. ## Public key Public key is constructed by $pk=(a\cdot s+e, a)$ where the coefficients of $a$ are sampled uniformly in $\mathbb{Z}_q$. The error $e$ is sampled from $DG(\sigma^2)$ where $DG$ is the discrete Gaussian distribution. ## Encryption Encryption of $m$ using public key. sample $v$ from ZO distribution over $\{0,\pm1\}^N$ with probability of $1/4$ of $1$ and $1/4$ of $-1$ and $1/2$ for $0$. Then, sample $e_1,e_2\leftarrow DG(\sigma^2)$. output $v\cdot pk+(m+e_1,e_2)$. These methods are described the same in the three main CKKS papers[^7] [^8] [^9] ## Error sampling with standard deviation $\sigma$ The $\sigma$ for error is recommended to be 3.2 for 128-bit security[^1]. This is the value used in [Heaan](https://github.com/snucrypto/HEAAN/blob/98e0205e5b15d13b3652064f4191104b632c2682/HEAAN/src/Params.h#L19) . From the HE-standard: "it is sufficient to choose each coefficient from a Discrete Gaussian distribution (or even rounded continuous Gaussian distribution) with a small constant standard deviation 𝜎. Selecting the error according to a Discrete Gaussian distribution is described more often in the literature, but choosing from a rounded continuous Gaussian is easier to implement (in particular when timing attacks need to be countered)."[^1] ## Hamming weight in HE standard paper The HE standard papers states: "The security reductions ensure that choosing the key from the same distribution as the error does not weaken the scheme. However, for many homomorphic encryption schemes (including BGV and BFV), choosing an even smaller secret key has a significant performance advantage. For example, one may choose the secret key from the ternary distribution (i.e., each coefficient is chosen uniformly from {−1,0,1}). In the recommended parameters given below, we present tables for three choices of secret distribution: uniform, the error distribution, and ternary...In some extreme cases, there is a reason to choose an even smaller secret key, e.g., one with sparse coefficient vector. However, we will not present tables for sparse secrets because the security implications of using such sparse secrets is not well understood yet"[^1] ## Hamming weights values in literature - 64 for n=32K and n=64K in [^8] section 6.1, page 17. - 64 for n=32K in [HEAAN-public github](https://github.com/snucrypto/HEAAN/blob/98e0205e5b15d13b3652064f4191104b632c2682/HEAAN/src/Params.h#L19). - 64 for any n in [Full-RNS-HEAAN github](https://github.com/KyoohyungHan/FullRNS-HEAAN/blob/515f6414076ca387996cb12e0798b4e3fcee653e/src/Context.h#L119) - 120 for any n according to Shai Halevi & Victor Shoup discussion with Allon Adir. - 192 for n=32K in [Bossuat's paper](https://eprint.iacr.org/2020/1203.pdf) - 192 for n=64K in cryptolab - 128/64 for n=32K/16K in [Chen's paper](https://eprint.iacr.org/2018/067.pdf) - References related to Sparse secret key [^2] [^3] [^4] [^5] [^6] [^10] [^11] ## Modulo max bit size per hamming weight=192 - 1533 bits in [^5], (Bossuat 2020) ![[Pasted image 20250127173935.png]] - 1553 bits (note: not 1533 bits) in [^12], (2022, Minki), should be less as the attack's complexity is 127.1 which is a bit less than 128. ![[Pasted image 20250422122533.png]] - Did not find many works on $n=2^{16}$. - [^13] does not have $h=192$ only $h=128$. for $n=2^{16}$, $\log Q=1450$ bits. (2022, Cheon) Tag: #tech ## Created 2024-11-18 14:28 [^1]: [[@Homomorphic Encryption Standard]], section 2.1.5 [^2]: https://eprint.iacr.org/2018/067.pdf [^3]: https://dl.acm.org/doi/pdf/10.1145/3338469.3358940?casa_token=T_-cRYYpRqcAAAAA:1fy786-N5tNQl4hPU8PVZMq9DqUNBvqeVgWVRNrf7fLmaUbj6ssUfENzydTF8DhVgW5oADNtxeDX [^4]: https://eprint.iacr.org/2024/463.pdf [^5]: https://eprint.iacr.org/2020/1203.pdf [^6]: https://eprint.iacr.org/2022/024.pdf [^7]: [[@original ckks paper - Homomorphic Encryption for Arithmetic of Approximate Numbers]] [^8]: [[@Bootstrapping for Approximate Homomorphic Encryption]] [^9]: [[@A Full RNS Variant of Approximate Homomorphic Encryption]] [^10]: https://dl.acm.org/doi/pdf/10.1145/3338469.3358941?casa_token=kiTBOZ-7u3AAAAAA:cX8-ip32ICSKDeQ2P_W3F5wWRgD8b0Ypw0MdSwyaA7_q6Pm5v_c_pCDaS7dBQb_mEIZ_BAZJAbTc [^11]: https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8747481 [^12]: [Let’s Meet Ternary Keys on Babai’s Plane: A Hybrid of Lattice-reduction and Meet-LWE](https://eprint.iacr.org/2022/1473.pdf) [^13]: [Practical FHE parameters against lattice attacks](https://eprint.iacr.org/2021/039.pdf)