CKKS Composite Scaling

[fdiasmor]

Composite Scaling CKKS

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

• By design, the assumption is that, when operating with the composite scaling mode, the target hardware platform has fixed word size smaller than 64 bits.

 

• Current composite scaling implementation may not cover all crypto functionalities that OpenFHE may offer using the CKKS scheme; for example, multiparty computation support and scheme switching.

• In cryptocontext.h, LevelReduce base class call always assume number of input levels is within single scaling concept; however, this could cause confusion; for example, compare lines 711 and 684 of ckksrns-advancedshe.cpp. Calling cc-> will invoke the base class implementation, which applies the composite degree as a multiplying factor on the input number of levels.

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

[du1204]

NOTE: PR#4 issue is related to the re-factoring process. compositeDegree=3 also worked fine in HERACLES-openfhe-development repo.