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