Investigating Non-Linear Scaling of CKKS Evaluation Keys and Crypto Context Size in OpenFHE

Library Questions
1

Hi everyone!

I have a question regarding the size of CKKS evaluation keys and crypto context in memory. I initially thought the size of the keys would scale linearly with the ring dimension, but after conducting some measurements, I observed something different.

For ring dimensions from 2^13 to 2^18 with the following parameters:

  • SPARSE_TERNARY
  • HEStd_NotSet
  • FLEXIBLEAUTO
  • dcrt_bits = 59
  • first_modulus = 60
  • levels_available_after_bootstrap = 15
  • level_budget = [4, 4]
  • Enabled: PKE, KEYSWITCH, LEVELEDSHE, ADVANCEDSHE, FHE
  • Bootstrapping precomputed, along with several rotation keys

I measured the memory usage before and after precomputing, and here are the results in log-log scale:

memory_usage
memory_usage540×360 24.7 KB

At lower dimensions, the size of the keys scales almost linearly, but for 2^18, the size is 95 GiB compared to 28 GiB for 2^17—definitely not linear. I’ve verified that my measurements seem to be accurate.

Could someone help explain why the dependency isn’t linear? Is it supposed to be linear, or if not, what should the scaling look like?

Thanks in advance!

2

One of the reasons you observe this is because of bootstrapping. I assume you are using fully packed ciphertexts? In that case, the homomorphic encoding and homomorphic decoding performed for bootstrapping require more rotation keys. The implementation is quite complex, especially when using multiple levels. How many more keys depends on the number of levels used, on the baby/giant step used, on the exact ring dimension etc (because some of the needed keys will repeat, but you will only generate one). As a ballpark estimate, when there is a single level used in homomorphic encoding and decoding, the number of required keys is of the order of 2\sqrt{N}. Therefore when you go from N to 2N, the storage for rotation keys grows by at least 2\sqrt{2}, which is closer to what you observe.

3

Thanks a lot! Yes, I am using a full packing, it looks like what I was looking for!