CKKS scaleModSize <= 60

When setting the CKKS parameters, the following lines:

uint32_t scaleModSize = 61;
CCParams<CryptoContextCKKSRNS> parameters;
parameters.SetScalingModSize(scaleModSize);

Gives the following error message:
.../src/core/include/math/nbtheory-impl.h:l.333:FirstPrime(): FirstPrime: Requested bit length 61 exceeds maximum allowed length 60

I know that the moduli chain we use is approximately the scale size we requested, and we need to be careful not to cause overflows (assuming 64-bit precision). However, 60-bit upper bound seemed like an overkill. Why can’t we use, say, scaleModSize = 62?

One of the underlying modular multiplication algorithms (modified Barrett modular multiplication) supports only moduli up to 2^{60}-1. This is why moduli are restricted to 60 bits. OpenFHE does not impose any restrictions on the selection of moduli, i.e., any modulus that is congruent to 1 \bmod 2 N is supported.

It is theoretically possible to support 62-bit moduli on 64-bit architectures, but the complexity of modular multiplication algorithms becomes higher (search for “62-bit” in A Tour of NTL: Summary of Changes or look at https://www.shoup.net/papers/akl-chapter.pdf for Victor Shoup’s discussion of this topic), or special (invariant) primes have to be used to achieve lower complexity (as in NFLlib: https://core.ac.uk/download/pdf/50531552.pdf). We decided not to support 62-bit primes in OpenFHE to maintain the flexibility of using an arbitrary prime (especially in RNS settings, when many moduli are needed and generated on the fly).

1 Like