Relationship between ScaleModSize and RingDimension

Library Questions
1

Hi,

I was looking into the relationship between the scaleModSize parameter and the ring dimension in CKKS. I noticed something that doesn’t make sense to me, which is that when the ring dimension increases, the minimum possible scale mod size also increases.
Please note that I am specifically ignoring the Security Level, I am trying to understand what is technically possible.

The code I used is very simple, it just generates a crypto context with a few parameters:

int main(int argc, char * argv) {
// Step 1: Setup CryptoContext
uint32_t multDepth = 1;
uint32_t scaleModSize = std::stoi(argv[2]);
uint32_t firstModSize = scaleModSize+1;
uint32_t batchSize = 8;
uint32_t ringDim = std::stoi(argv[1]);

CCParams<CryptoContextCKKSRNS> parameters;
parameters.SetMultiplicativeDepth(multDepth);
parameters.SetScalingModSize(scaleModSize);
parameters.SetFirstModSize(firstModSize);
parameters.SetBatchSize(batchSize);
parameters.SetRingDim(ringDim);
parameters.SetSecurityLevel(HEStd_NotSet);

CryptoContext<DCRTPoly> cc = GenCryptoContext(parameters);

// Enable the features that you wish to use
cc->Enable(PKE);
cc->Enable(KEYSWITCH);
cc->Enable(LEVELEDSHE);
std::cout << "CKKS scheme is using ring dimension " << cc->GetRingDimension() << std::endl << std::endl;

return 0;

}

I tried a few combinations of parameters, namely: For each ring dimension between 1024 and 131072 I tried to approach the lowest possible scaleModSize that doesn’t lead to an error. This resulted in the following:
1024: 13
2048: 15
4096: 15
8192: 16
16384: 16
32768: 16
65536: 19
131072: 19

Anything below that causes the error “LastPrime: overflow shrinking candidate” during crypto context generation.
Could you please explain what causes this?

Also, I noticed a strange phenomenon here:
For some ring dimensions, the behavior of the scaleModSize seems to be irregular:
For example, for the ringDim 32768, 16 seems to be the lowest possible scaleModSize. Anything beneath that cause an “LastPrime: overflow shrinking candidate” error. However, the values 17 and 18 again cause errors (“LastPrime: Requested 18 bits, but returned 17. Please adjust parameters.” and “LastPrime: Requested 19 bits, but returned 17. Please adjust parameters.” respectively). 19 and above are fine again.

Is there a mathematical explanation for this, or could it be a bug?
I am using the latest release of OpenFHE.

Thanks a lot!
Clemens

2

The underlying moduli are all primes. They have to satisfy certain conditions to meet functionality and implementation constraints. One condition is that any prime q-1 is divisible by 2N, where N is the ring dimension. As a consequence of this condition, q must be greater than 2N.

Note you need to generate multiple moduli depending on the multiplicative depth, hence you may run out of functional moduli in a low bit width.

The error messages you are getting tell you that there are not enough (or maybe zero) prime moduli in the range of parameters you selected.