Bootstrapping parameters and residual parameters in CKKS.

[MingMouSan]

For enough security, is it required that LogN must >= 16 in bootstrapping parameters?
And can the LogN in residual parameters less than 16, when the LogN in bootstrapping is set to be 16?
Will a smaller LogN in residual parameters speed up the execution of bootstrapping?

[Pro7ech]

For enough security, is it required that LogN must >= 16 in bootstrapping parameters?

Usually yes, because the bootstrapping circuit is around 800 bits (not taking into account the auxiliary modulus $$P$$) and you want something usable afterward (the residual parameters). According to the lattice estimator, a ring degree of $$N=2^{15}$$ with a uniform ternary secret and an error distribution $$\sigma=3.2$$ can support a modulus of up to $$~881$$ bits for 128-bit security, hence why $$N=2^{16}$$ is usually chosen. It is possible to squeeze the bootstrapping parameters to $$N=2^{15}$$ and still remain 128-bit secure, but precision, residual parameters, hence overall throughput, will suffer a lot (see Table 6 of https://eprint.iacr.org/2022/024.pdf). In the special case where the plaintext space is $$\mathbb{Z}_{2}$$ (i.e. bits), then this recent works shows that it is possible to have 128-bit secure bootstrapping parameters with $$N=2^{14}$$.

If you are unsure about the security, given a <bootstrapping.Parameters> struct, you can get the relevant info (ring degree, modulus, secret and error distribution) with

<bootstrapping.Parameters>.BootstrappingParameters.LogN()
<bootstrapping.Parameters>.BootstrappingParameters.LogQP()
<bootstrapping.Parameters>.BootstrappingParameters.Xs()
<bootstrapping.Parameters>.BootstrappingParameters.Xe()

This will output the necessary information to run the lattice estimator to get a security estimation.

Not that by default the secret Hamming weight of the bootstrapping parameters is $$192$$ and the sparse secret encapsulation technique of https://eprint.iacr.org/2022/024.pdf is used to improve the performance of the bootstrapping circuit.

Can the LogN in residual parameters be less than 16, when the LogN in bootstrapping is set to be 16?

Yes

Will a smaller LogN in residual parameters speed up the execution of bootstrapping?

Not automatically. By default the bootstrapping circuit is configured to support the maximum number of slots enabled by the bootstrapping parameters (i.e. $$N/2$$ complex slots), not the residual parameters. You can configure this by setting the field LogSlots in the <bootstrapping.ParametersLiteral> to be the same as the maximum number of slots enabled by your parameters literal. This will improve the timings the homomorphic DFT, but not reduce the bit consumption of the homomorphic DFT. To reduce the bit consumption of the homomorphic DFT (at the cost of increasing its complexity), you can experiment by manually setting the fields CoeffsToSlotsFactorizationDepthAndLogScales and SlotsToCoeffsFactorizationDepthAndLogScales since their default value is optimized for $$2^{15}$$ complex slots.

That being said, it is much more efficient to call BootstrapMany on many ciphertexts with smaller residual parameters than call Bootstrap on each smaller ciphertext individually with a bootstrapping configured for a smaller number of slots.

[MingMouSan]

But in lattigo-main/examples/singleparty/ckks_bootstrapping/basics/main.go, When I change the line 29 to LogN := 14 and line 44 to LogN: 13, and then run go run main.go, it says panic: cannot NewParametersFromLiteral: Q[0]=36028797018652673 != 1 mod NthRoot=32768.

[Pro7ech]

There is an 'LogNthRoot' field in the parameters literal. It needs to be set to LogN+1 of the bootstrapping parameters.