Add CKKS Composite Scaling

[fdiasmor]

CKKS Composite Scaling

This issue concerns the implementation of the composite scaling technique for CKKS presented in https://eprint.iacr.org/2023/1462.pdf. It enables high-precision RNS-CKKS when the hardware architecture word size is smaller than the scaling factor.

The enablement of the composite scaling CKKS as a feature into the OpenFHE library:

CKKS composite scaling is designed to achieve high-precision RNS-CKKS encrypted computation with scaling factors greater than the target hardware architecture's register word size. For example, with composite scaling, we can configure the RNS scaling factor to be 58 bits, i.e. choosing prime moduli with 58 bits of precision, and compute on an accelerator whose architecture's register size is 32 bits. This feature is introduced into the OpenFHE API as a new scaling technique. This new scaling technique mode is architected into 4 Pull Requests, each of which entails specific parts of the composite scaling technique enablement, as depicted in the diagram below. This includes generating composite prime moduli, where each level is represented by the product of d primes that fit in XX-bit registers (e.g., 32-bit registers), and d is greater than or equal to 2, known as the composite degree. Our new mode also extends its support to both the conventional bootstrapping algorithm and the most recently proposed Meta-BTS bootstrapping algorithm.

It is introduced as a new scaling technique in OpenFHE. There are two ways to enable CKKS composite scaling:

• By setting the scaling technique to COMPOSITESCALINGAUTO: This is the most suitable choice for any developer trying out or not familiar with the intricate details of composite scaling.

• By setting the scaling technique to COMPOSITESCALINGMANUAL: This mode is meant for developers that wish to experiment with untested/unlikely combinations of composite scaling parameters that may only be functional under special circumstances. In those special cases, the program may be more sensitive to runtime errors due to insufficient availability of prime moduli for given certain values for the tuple <register word size, multiplicative depth, ring size>.

Composite Modulus Chain Generation

• All prime moduli are NTT-friendly (tested up to 2^16).

• All primes in the modulus chain are distinct from each other.

• q_i = p_1 x ... x p_ d ~ 2 ^\delta, where \delta is the scaling factor, q_i is the composite coefficient modulus comprised of the prime moduli {p_1, ..., p_d}, and d is the composite degree that characterizes the composite scaling approach.

• p_i is chosen to be very close 2^( (scalingModSize) / (composite degree) )

Composite Scaling Bootstrapping

• Current implementation supports single-iteration CKKS bootstrapping.

• Current implementation supports Meta-BTS (or multiple-iteration) CKKS bootstrapping.

Current Constraints

• This current CKKS composite scaling implementation only supports single-key CKKS.

• By design when operating on composite scaling mode (i.e., COMPOSITESCALINGAUTO), the target hardware platform is assumed to have fixed word size smaller than 64 bits. However, in general, it still works under the scenario where scaling factors greater than 64 bits running on hardware architectures having 64-bit register word size (this capability is still under refactoring).

• Regardless of the target architecture word size, the OpenFHE library needs to be compiled using NATIVEINT=64 compilation flag.

• COMPOSITESCALING<AUTO/MANUAL> scaling technique mode only works with the CKKS scheme.

• The secret key distribution needs to be set to UNIFORM_TERNARY.