Memory Allocation Failure During Bootstrapping with Large Ring Dimensions in FHE

Library Questions
,
1

I’m encountering an issue when attempting to run bootstrapping on large ring dimensions and batch sizes.
Specifically, when using a level budget of [1,1], a ring dimension of 2^16, and a batch size of 2^14, the process completes successfully but consumes a significant amount of memory (>1.4 TB).
However, when scaling up to a ring dimension of 2^17 and a batch size of 2^16, memory usage exceeds 2.2 TB, after which the program crashes with the following error:

terminate called recursively
terminate called recursively
terminate called after throwing an instance of 'std::bad_alloc'
line 15: 585689 Aborted                 (core dumped) python3 -m "$module_path"

Running in debug mode, I traced the issue to this line in the file ckksrns-fhe.cpp:

NativeVector nativeVec(N, nativeParams[i]->GetModulus());

I’d appreciate any advice, insights, or suggestions for this issue.

2

Full-packing bootstrapping should not be run with a level budget [1,1] as this requires a large number of keys and has a high computational complexity (this can be easily shown both theoretically and practically). The collapsed FFT mode is always suggested for full packing, e.g., level budget of [4,4]. Early works on CKKS bootstrapping that used [1,1], e.g., Bootstrapping for Approximate Homomorphic Encryption, could not even support full packing until the collapsed FFT mode was proposed in Improved Bootstrapping for Approximate Homomorphic Encryption.

3

Thanks, I was able to significantly reduce memory usage (from TBs to GBs). However, I’m now encountering another issue related to output correctness after bootstrapping.

When running experiments on input values in the range (-1, 1) with a ring dimension of 2^17 and batch size 2^16, the bootstrapped outputs return nan values. I tested this across multiple level budgets ([4,4], [3,3], and [2,2]), all yielding the same result.

Interestingly, using a smaller ring dimension (2^16) and batch sizes of 2^14 or 2^15 works fine, producing correct outputs with level budgets [1,1] and [2,2].

4

Could you post the minimal working example that recreates the issue? Do you get nan every time or only sometimes?

5

Thank you for helping on this. Here is the simple python script i used for it:

from openfhe import *
import random

ring_dim = 2**17
batch_size = ring_dim // 2

if get_native_int() == 128:
    rescale_tech = ScalingTechnique.FIXEDAUTO
    dcrt_bits = 78
    first_mod = 89
else:
    rescale_tech = ScalingTechnique.FLEXIBLEAUTO
    dcrt_bits = 59
    first_mod = 60
secret_key_dist = SecretKeyDist.UNIFORM_TERNARY

parameters = CCParamsCKKSRNS()
parameters.SetScalingModSize(dcrt_bits)
parameters.SetFirstModSize(first_mod)
parameters.SetScalingTechnique(rescale_tech)
parameters.SetNumLargeDigits(3)
parameters.SetSecretKeyDist(secret_key_dist)
parameters.SetSecurityLevel(SecurityLevel.HEStd_128_classic)
parameters.SetRingDim(ring_dim)
parameters.SetBatchSize(batch_size)
parameters.SetKeySwitchTechnique(HYBRID)

level_budget = [4, 4]
levels_available_after_bootstrap = 20
num_slots = batch_size
depth_bootstrap = FHECKKSRNS.GetBootstrapDepth(level_budget, secret_key_dist)
depth = levels_available_after_bootstrap + depth_bootstrap

parameters.SetMultiplicativeDepth(depth)

cryptocontext = GenCryptoContext(parameters)
cryptocontext.Enable(PKESchemeFeature.PKE)
cryptocontext.Enable(PKESchemeFeature.KEYSWITCH)
cryptocontext.Enable(PKESchemeFeature.LEVELEDSHE)
cryptocontext.Enable(PKESchemeFeature.ADVANCEDSHE)
cryptocontext.Enable(PKESchemeFeature.FHE)

key_pair = cryptocontext.KeyGen()
cryptocontext.EvalMultKeyGen(key_pair.secretKey)
cryptocontext.EvalBootstrapSetup(level_budget, slots=num_slots)
cryptocontext.EvalBootstrapKeyGen(key_pair.secretKey, num_slots)

x = [random.uniform(-1.0, 1.0) for _ in range(batch_size)]
print(f"`Input` Result:\n {x[:10]}")
print()

ptx = cryptocontext.MakeCKKSPackedPlaintext(x, level=depth - 1)
ctx = cryptocontext.Encrypt(key_pair.publicKey, ptx)

lvl = ctx.GetLevel()
print(f"Mul-Depth: {lvl}")
print(f"Initial number of levels remaining: {depth - lvl}")
print()

ctx_refreshed = cryptocontext.EvalBootstrap(ctx)

res_ptx = cryptocontext.Decrypt(key_pair.secretKey, ctx_refreshed)
res_ptx.SetLength(batch_size)
res_vec = res_ptx.GetRealPackedValue()
res_vec = [round(val, 2) for val in res_vec]
print(f"Decrypted `Bootstrapp` Result:\n {res_vec[:10]}")

The issue happens when running this on the latest version of openfhe-python v1.3.0.0.20.4 installed directly by pip3.8 and pip3.10. It also produces consistently the same nan result when built from source. And here is a sample of the output:

`Input` Result:
 [0.17675434979084526, -0.37504098062076374, 0.4796583872715898, 0.937460265167543, -0.7410684847721298, 0.8124632153799727, 0.714340313325494, -0.013021436593108726, -0.25327522311343964, 0.6103009698880677]

Mul-Depth: 41
Initial number of levels remaining: 1

Decrypted `Bootstrapp` Result:
 [nan, nan, nan, nan, nan, nan, nan, nan, nan, nan]

I so happened to have a docker version somewhere with an older build and here is the output of pip show openfhe on the docker

Name: openfhe
Version: 0.8.4
Summary: Python wrapper for OpenFHE C++ library.
Home-page: https://github.com/openfheorg/openfhe-python
Author: OpenFHE Team
Author-email: contact@openfhe.org
License: BSD-2-Clause
Location: /openfhe-python
Editable project location: /openfhe-python
Requires: pybind11, pybind11-global, pybind11-stubgen

This version seems to work as expected and here is the output for the same script above:

`Input` Result:
 [0.8923063639960698, -0.13170292096094283, 0.821223452909841, 0.15983270791434356, 0.14807709174686567, -0.6526677159492442, -0.5970628388908674, -0.1773637033776172, -0.0922501974693466, 0.9817870849703605]

Mul-Depth: 41
Initial number of levels remaining: 1

Decrypted `Bootstrapp` Result:
 [0.89, -0.13, 0.82, 0.16, 0.15, -0.65, -0.6, -0.18, -0.09, 0.98]
6

Another question about bootstrapping while we are at it, is there any support in openfhe to Serialize/Deserialize bootstrapping keys?

I have checked an old topic related to this Bootstrapping Serialization Discourse and it seems that they referenced an issue #353 which doesn’t seem to be resolved yet.

7

Another question about bootstrapping while we are at it, is there any support in openfhe to Serialize/Deserialize bootstrapping keys?

Please ask this question in a different topic as it is unrelated to the original question.

1 Like
8

Thank you. I will do some testing on my side to see if I can recreate the issue.