Question:What is the range of each number in the LogQ array?

[hionwi]

I noticed in the example ckks, LogQ: []int{55, 45, 45, 45, 45, 45, 45, 45}, how are these numbers 55,...,45 chosen and what is their range? Can I choose 28 or 29?

[lehugueni]

Hi,

Sorry for the slow answer. The parameter selection in general is a complex process and many optimizations are possible depending on the application. If you're not familiar the basics of CKKS, I'd recommend you to read the original paper and the RNS-variant.

That said, usually the moduli size given in LogQ are picked according to the precision wanted and the range of the output. The first prime $$q_0$$ (which has a size of 55 in your example) will define the range of the encoded input. That means that your encoded input can be in a range $$[0, q_0)$$.
During the encoding (that basically converts floats to integers), the input is scaled by a value $$\Delta$$ and rounded, where the log size of $$\Delta$$ is given by LogDefaultScale in Lattigo. That implies that the the baseline precision of the scheme is given by LogDefaultScale and that your input must fit into $$\log(q_0) - \log(\Delta)$$ bits. So the larger your $$\log(q_0)$$, the more precision and range you can have.

Usually, the rest of the primes are picked s.t. they are close to the scale. For instance, the values in your example (45) match the value LogDefaultScale. The reason is that after a multiplication of fresh ciphertexts, the scale of the result is $$\Delta^2$$, and you can rescale by one of these primes. If it is close to $$\Delta$$, the scale goes back to $$\approx \Delta$$.

Without going into too much detail, you also the size of the auxiliary prime(s) $$P$$ to pick, which we want to be larger than $$q_0$$.
Therefore, as we work with 64-bit integers in Lattigo, the process can be summarised as follows:

1. Pick the largest $$P$$ possible, that fit into $$64$$-bit (minus some space to avoid overflow). We pick $$\log(P) = 61$$ in one of the examples.
2. Pick the largest $$q_0$$ possible that is smaller than $$P$$. We pick $$\log(q_0) = 55$$ in your example. This defines the maximal range of your encoded input.
3. Pick the baseline decimal precision you want. This defines your LogDefaultScale you want and the rest of the $$\log(q_i)$$. In your example we have a maximal precision of $$45$$ bits and input values must roughly be in $$[0, 2^{10})$$.

TL;DR The range is $$61 \geq \log P > \log q_0 \geq \log q_i = \texttt{LogDefaultScale}$$. You can pick lower values for $$q_i$$ and the default scale, it'll give you more range but less precision.

Note that more complex techniques allowing the use of different prime sizes exist, e.g. scale management systems.

[hionwi]

Thanks for your answer. I noticed that in the params.go file,
CKKSComplexParamsPN16QP1761 = ckks.ParametersLiteral{
LogN: 16,
LogQ: []int{56, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45},
LogP: []int{55, 55, 55, 55},
LogDefaultScale: 45,
}
Since Log P > Log Q[0] is sufficient, why choose a larger LogP?

[lehugueni]

Indeed, my previous answer was a simplification. In practice in Lattigo we use a generalised version of the RNS decomposition described in this paper: https://eprint.iacr.org/2019/688.pdf. The answer to your question is in Section 3. In short, if you have $$\ell$$ primes $$p_i$$, the moduli $$q_i$$ are split into smaller products of at most $$\ell$$ primes for key decomposition. And what you need for the scheme to work is now to have $$P$$ larger than any of these products. So in your example we want $$\log P$$ to be larger than any subset of four values in $$\log Q$$.
Note that if you take the number of $$p_i$$ to be equal to 1 we fall back to my previous answer. The number of $$p_i$$ is up to you but there is a trade-off to consider. The larger $$P$$, the larger $$PQ$$ gets and it decreases the security. Thus, for a fixed security level you'd need to lower your $$Q$$ (the maximal depth of your circuit). But the smaller $$P$$ gets, the larger your decomposition and your keys are.