Security Parameters

FHE Questions
1

I am somewhat familiar with post-quantum cryptography and lattices. I am also currently beginning to research FHE. The documentation (i.e. CRYSTALS-Kyber: Kyber) can be dense so maybe someone here can help?

  1. Why is there such a difference in parameters between Kyber and FHE schemes? For example Standard – Homomorphic Encryption Standardization suggests for 128 bit quantum security with error distribution (-1,1)
    n = 1028 and log(q) = 25 (larger n offered too)
    While Kyber requires
    n = 256 and q = 3329

I know Kyber uses some form of compression but isn’t that just for the keys? I also know Kyber is based on Module-LWE and most FHE uses Ring-LWE, is this a factor? I also (somewhat) understand Kyber is IND-CCA2 and by definition FHE cannot be (my understanding) but I thought this is just some obfuscation/hashing at the end, does that affect? Also in FHE q is a product of 3+ primes whereas 3329 is prime itself? Both documents seem to reference similar hardness problems (SVP using BKZ, etc) but then these parameters (n and q) seem completely unrelated. Any guidance in my confusion would be greatly appreciated.

2

The tables in the Standard – Homomorphic Encryption Standardization were generated using the LWE estimator for the ranges of parameters that are useful for FHE applications. Kyber targets a different application, and hence, works with different parameters (a smaller ring dimension n).

To estimate the work factor for the Kyber setup, you can use Lattice Estimator, which has replaced the LWE estimator as the main community tool for selecting LWE parameters.

To get more familiar with how the estimator works, I suggest looking at On the concrete hardness of Learning with Errors