This project provides an implementation of CKKS bootstrapping based on Microsoft SEAL. Both non-sparse and sparse secret key variants are supported.
In version 2.0, the non-sparse key variant achieves 16~17 bits of precision with a runtime of 31~34 seconds, while the sparse key variant shows similar precision with a faster runtime of 26~28 seconds.
Compared to version 1.x, this reflects an improvement of approximately 6~7 bits in precision and a 39~53% reduction in runtime. Detailed results can be found in the Test section.
(Note: We previously claimed a precision of 12~17 bits due to a calculation error, although the actual precision was around 10 bits. We apologize for the mistake.)
The bootstrapping process consists of the following core steps:
- Modulus reduction (ql -> q0)
- Modulus raising (q0 -> Q)
- Coefficient-to-Slot using BSGS (CTS)
- Approximate modulus reduction using Taylor series (Eval Mod q0)
- Slot-to-Coefficient using BSGS (STC) After bootstrapping, a ciphertext at level qL is obtained.
This code is designed for testing and analyzing the CKKS bootstrapping pipeline with configurable parameters and performance measurements.
For any inquiries or feedback, please use the GitHub Issues tab or contact us at:
Email:
java_script@kakao.com
- Provides CKKS bootstrapping operations to refresh and reduce noise in CKKS ciphertexts.
- Implements core functions for bootstrapping, including modulus extension, CTS, STC, approximate modulus reduction, and correction factor, among others.
- Source files:
- Raises the modulus of a ciphertext to the highest (bootstrapping) modulus level in the modulus switching chain.
- Source files:
- Validate or set the bootstrapping depth based on circuit parameters.
- Source files:
- Defines entry_context and entry_parms_id.
- Checks whether the encryption parameters are secure under the HomomorphicEncryption.org security standard, taking bootstrapping depth into account.
- Creates an RNSTool instance required for bootstrapping.
- Source files:
- Allows generating a sparse secret key (h = 64) using additional parameters.
- Source files:
- Computes precision by decrypting ctorigin and ctboot, then measuring the average error between the resulting vectors.
- Source files:
- CPU: Intel Core i5-8500 @ 3.00GHz
- RAM: 32 GB
- OS: Windows 11 Pro (Version 24H2, Build 26100.4349)
- Architecture: 64-bit, x64-based processor
- Compiler: Microsoft Visual Studio (MSVC), C++17
- Build Configuration: Release
| Test | Secret Key | d_0 | r | log2(N) | log2(q0) | log2(Q) | log2(scale) | log2(Δ) | Depthboot | Precision | Time (s) |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Test 1 | Non-Sparse | 15 | 11 | 12 | 60 | 1602 | 51 | 60 | 23 | ≈2-16.78 | 34.797 |
| Test 2 | Non-Sparse | 15 | 9 | 12 | 60 | 1482 | 51 | 60 | 21 | ≈2-17.08 | 31.145 |
| Test 3 | Sparse (h=64) | 15 | 7 | 12 | 60 | 1362 | 51 | 60 | 19 | ≈2-16.43 | 28.234 |
| Test 4 | Sparse (h=64) | 15 | 6 | 12 | 60 | 1302 | 51 | 60 | 18 | ≈2-16.64 | 26.971 |
#include <seal/seal.h>
#include <random>
using namespace seal;
using namespace std;
int main()
{
// Parameters.
size_t poly_modulus_degree = 4096;
int q_0_bit_size = 60;
int P_bit_size = q_0_bit_size;
int scale_bit_size = 51;
int delta_bit_size = 60;
double_t scale = pow(2.0, scale_bit_size);
double_t delta = pow(2.0, delta_bit_size);
size_t encrypted_level = 0;
size_t d_0 = 15;
size_t r = 9;
// CKKS context.
EncryptionParameters parms(scheme_type::ckks);
parms.set_poly_modulus_degree(poly_modulus_degree);
parms.set_bootstrapping_depth(CKKSBootstrapper::get_bootstrap_depth(delta_bit_size, encrypted_level, d_0, r));
parms.set_coeff_modulus(CKKSBootstrapper::create_coeff_modulus( // create coefficient modulus for bootstrapping.
poly_modulus_degree,
{ q_0_bit_size, scale_bit_size, scale_bit_size, P_bit_size },
delta_bit_size, encrypted_level, d_0, r));
SEALContext context(parms, true, sec_level_type::none);
print_parameters(context);
cout << endl;
// Keys.
//KeyGenerator keygen(context, true); // use sparse secret key.
KeyGenerator keygen(context); // use non-sparse secret key.
SecretKey secret_key = keygen.secret_key();
PublicKey public_key;
keygen.create_public_key(public_key);
RelinKeys relin_keys;
keygen.create_relin_keys(relin_keys);
GaloisKeys galois_keys;
keygen.create_galois_keys( // create Galois keys for bootstrapping.
CKKSBootstrapper::create_galois_steps(poly_modulus_degree), galois_keys);
// Algorithms.
Encryptor encryptor(context, public_key);
Evaluator evaluator(context);
Decryptor decryptor(context, secret_key);
CKKSEncoder encoder(context);
CKKSBootstrapper bootstrapper(context); // create bootstrapper instance.
// Random data.
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<double> dist(0.0, 1.0);
vector<complex<double_t>> vector_1, res_vector;
vector_1.reserve(encoder.slot_count());
for (size_t i = 0; i < encoder.slot_count(); i++)
{
vector_1.push_back({ static_cast<double_t>(dist(gen)) });
//vector_1.push_back({ static_cast<double_t>(dist(gen)) * 10 });
}
cout << "Input vector: " << endl;
print_vector(vector_1, 3, 7);
Plaintext plain_1, plain_res;
encoder.encode(vector_1, scale, plain_1);
//encoder.encode(complex<double>(1, 1), scale, plain_1);
Ciphertext cipher_1, cipher_res;
encryptor.encrypt(plain_1, cipher_1);
print_ciphertext<double_t>(context, cipher_1, encoder, decryptor, 20, 7);
// Evaluate (ct^4).
evaluator.square_inplace(cipher_1);
evaluator.relinearize_inplace(cipher_1, relin_keys);
evaluator.rescale_to_next_inplace(cipher_1);
evaluator.square_inplace(cipher_1);
evaluator.relinearize_inplace(cipher_1, relin_keys);
evaluator.rescale_to_next_inplace(cipher_1);
print_ciphertext<double_t>(context, cipher_1, encoder, decryptor, encoder.slot_count(), 15);
// Bootstrap.
bootstrapper.bootstrapping(cipher_1, encoder, evaluator, relin_keys, galois_keys, delta_bit_size, encrypted_level, d_0, r, cipher_res, true);
print_ciphertext<double_t>(context, cipher_res, encoder, decryptor, encoder.slot_count(), 15);
return 0;
}