How to choose Secret Key Distribution

FHE Questions
1

There are 3 Secret Key Distributions:
GAUSSIAN
UNIFORM_TERNARY
SPARSE_TERNARY
Im original paper of CKKS or CKKS RNS there are 3 Distributions too?
why do you use for UNIFORM_TERNARY as default and GAUSSIAN for example?

1 Like
2

In LWE and RLWE, the secret key \mathbf{s} is sampled from a specific distribution over \mathbb{Z}_q^n.

The most secure distribution is uniform at random from \mathbb{Z}_q^n.

For efficiency reasons, other distributions are also used, offering a slight advantage to existing attacks but still not leading to a complete breach.

These distributions include:

  1. Gaussian: \mathbf{s} is sampled randomly from a truncated zero-mean Gaussian distribution with a specified width.

  2. Uniform Binary: \mathbf{s} is uniformly sampled randomly from the set \{0, 1\}.

  3. Uniform Ternary: \mathbf{s} is uniformly sampled randomly from the set \{-1, 0, 1\}.

  4. Sparse Ternary: \mathbf{s} is uniformly sampled from \{-1, 0, 1\} but with a specified Hamming weight that determines the number of non-zero coefficients in \mathbf{s}.

The sparse ternary distribution is the most efficient, particularly in bootstrapping operations.

In terms of security, these distributions are ranked from most secure to least secure as follows: uniform over \mathbb{Z}_q^n, Gaussian, uniform binary, uniform ternary, and sparse ternary.

Despite the differences in security, these distributions are commonly used in the literature.

Certain attacks exist for each case and the cryptographic parameters are chosen based on the secret key distribution to provide a specific security level.

For more information on this, refer to page 6 in this work.

2 Likes
3

Iā€™m wondering if I set SecretKeyDist = SPARSE_TERNARY and SetSecurityLevel(HEStd_128_classic), will the parameters still have 128-bit security?

4

As for the current state of art on this topic, the answer is yes.
Further details can be found here.

1 Like
5

The security guidelines document (as well as the prior 2018 HomomphicEncryption.org standards document) currently provides tables only for ternary uniform and Gaussian secrets. The tables for sparse secrets are not available yet (there is an open initiative to write a SoK and estimator for these). So OpenFHE by default uses the tables for uniform ternary secrets (also for sparse secrets). Note that sparse secrets should be used with care (only in research settings so far).