# 【DEBUG】SEAL 库 CKKS 方案 “scale out of bounds” 报错分析

Published:

“scale out of bounds” 报错分析。

## 0. 参考的Issues

Issues with defining CoeffModulus for CKKS

Polynomial moduli beyond 32768

Multiply plain repeatedly and scale out of bound error

SEAL-CKKS max multiplication depth

Implementing and Accelerating Bootstrap

## 1. 初始参数如何设置

There are two encryption parameters that are necessary to set:
- poly_modulus_degree (degree of polynomial modulus);
- coeff_modulus ([ciphertext] coefficient modulus);


        +----------------------------------------------------+
| poly_modulus_degree | max coeff_modulus bit-length |
+---------------------+------------------------------+
| 1024                | 27                           |
| 2048                | 54                           |
| 4096                | 109                          |
| 8192                | 218                          |
| 16384               | 438                          |
| 32768               | 881                          |
+---------------------+------------------------------+


terminate called after throwing an instance of 'std::invalid_argument'
what():  encryption parameters are not set correctly


## 2. 为什么这么设置

### （2） 模交换 modulus switching

    Modulus switching is a technique of changing the ciphertext parameters down
in the chain. The function Evaluator::mod_switch_to_next always switches to
the next level down the chain, whereas Evaluator::mod_switch_to switches to
a parameter set down the chain corresponding to a given parms_id. However, it
is impossible to switch up in the chain.
Due to the modulus switching chain, the order of the 5 primes is significant.
The last prime has a special meaning and we call it the special prime'. Thus,
the first parameter set in the modulus switching chain is the only one that
involves the special prime. All key objects, such as SecretKey, are created
at this highest level. All data objects, such as Ciphertext, can be only at
lower levels. The special prime should be as large as the largest of the
other primes in the coeff_modulus, although this is not a strict requirement.

special prime +---------+
|
v
coeff_modulus: { 50, 30, 30, 50, 50 }  +---+  Level 4 (all keys; key level')
|
|
coeff_modulus: { 50, 30, 30, 50 }  +---+  Level 3 (highest data level')
|
|
coeff_modulus: { 50, 30, 30 }  +---+  Level 2
|
|
coeff_modulus: { 50, 30 }  +---+  Level 1
|
|
coeff_modulus: { 50 }  +---+  Level 0 (lowest level)


### （4） rescaling

rescaling 是 CKKS 方案独有的操作，正是这个操作让它不同于其他方案，可以很方便地处理浮点数，从而被 AI 等领域青睐。

    We saw in 2_Encoders.cs' that multiplication in CKKS causes scales in
ciphertexts to grow. The scale of any ciphertext must not get too close to
the total size of CoeffModulus, or else the ciphertext simply runs out of
room to store the scaled-up plaintext. The CKKS scheme provides a rescale'
functionality that can reduce the scale, and stabilize the scale expansion.

Rescaling is a kind of modulus switch operation (recall 3_Levels.cs').
As modulus switching, it removes the last of the primes from CoeffModulus,
but as a side-effect it scales down the ciphertext by the removed prime.
Usually we want to have perfect control over how the scales are changed,
which is why for the CKKS scheme it is more common to use carefully selected
primes for the CoeffModulus.

More precisely, suppose that the scale in a CKKS ciphertext is S, and the
last prime in the current CoeffModulus (for the ciphertext) is P. Rescaling
to the next level changes the scale to S/P, and removes the prime P from the
CoeffModulus, as usual in modulus switching. The number of primes limits
how many rescalings can be done, and thus limits the multiplicative depth of
the computation.

It is possible to choose the initial scale freely. One good strategy can be
to is to set the initial scale S and primes P_i in the CoeffModulus to be
very close to each other. If ciphertexts have scale S before multiplication,
they have scale S^2 after multiplication, and S^2/P_i after rescaling. If all
P_i are close to S, then S^2/P_i is close to S again. This way we stabilize the
scales to be close to S throughout the computation. Generally, for a circuit
of depth D, we need to rescale D times, i.e., we need to be able to remove D
primes from the coefficient modulus. Once we have only one prime left in the
coeff_modulus, the remaining prime must be larger than S by a few bits to
preserve the pre-decimal-point value of the plaintext.

Therefore, a generally good strategy is to choose parameters for the CKKS
scheme as follows:

(1) Choose a 60-bit prime as the first prime in CoeffModulus. This will
give the highest precision when decrypting;
(2) Choose another 60-bit prime as the last element of CoeffModulus, as
this will be used as the special prime and should be as large as the
largest of the other primes;
(3) Choose the intermediate primes to be close to each other.

We use CoeffModulus.Create to generate primes of the appropriate size. Note
that our CoeffModulus is 200 bits total, which is below the bound for our
PolyModulusDegree: CoeffModulus.MaxBitCount(8192) returns 218.

We choose the initial scale to be 2^40. At the last level, this leaves us
60-40=20 bits of precision before the decimal point, and enough (roughly
10-20 bits) of precision after the decimal point. Since our intermediate
primes are 40 bits (in fact, they are very close to 2^40), we can achieve
scale stabilization as described above.


## 3. 为什么会报错

Generally, for a circuit of depth D, we need to rescale D times, i.e., we need to be
able to remove D primes from the coefficient modulus. Once we have only one prime
left in the coeff_modulus, the remaining prime must be larger than S by a few bits
to preserve the pre-decimal-point value of the plaintext.


## 4. 应对方法

### （1） 方法一

poly_modulus_degree = 32768;
precision        = 40;
modulus_size     = 20;
default_value    = 40;
sentenial_value  = 50;

vector<int> mod(modulus_size, default_value);
mod[0] = sentenial_value;
mod[modulus_size-1] = sentenial_value;

EncryptionParameters parms(scheme_type::ckks);
parms.set_poly_modulus_degree(poly_modulus_degree);
parms.set_coeff_modulus(CoeffModulus::Create(poly_modulus_degree, mod));


### （2） 方法二

github-HEAAN

HEAAN is software library that implements homomorphic encryption (HE) that supports
fixed point arithmetics. This library supports approximate operations between
rational numbers. The approximate error depends on some parameters and almost
same with floating point operation errors. The scheme in this library is on the paper
"Homomorphic Encryption for Arithmetic of Approximate Numbers"
(https://eprint.iacr.org/2016/421.pdf).