[Crypto] How to get exact number of slots in HElib? Such as 256, 4096

Solution 1:

The number of slots is $\varphi(m)/\text{ord}(p)$, where $\varphi(m)$ is the totient of $m$ and $\text{ord}(p)$ is the multiplicative order of $p$ mod $m$ (and hence divides $\varphi(m)$).

In order for the number of slots to be 256, it must be the case that $\varphi(m)$ is divisible by 256. Recall that $\varphi(m)$ is the product of the totients of all the maximal prime powers that divide $m$, i.e., $\varphi(m) = \prod_i (p_i-1)p_i^{e_i-1}$ where $m=\prod p_i^{e_i}$ is the factorization of $m$ into powers of distinct primes $p_i$.

To make $\varphi(m)$ divisible by $256=2^8$, observe that for odd $p_i$, the corresponding term $(p_i-1)$ in $\varphi(m)$ is divisible by some power of two, and these powers combine across the primes. However, higher powers of such primes don’t give us any high powers of two (nor do they hurt). Alternatively, if one of the $p_i=2$, then it contributes a factor of $2^{e_i-1}$ to the totient. As an extreme example, we could take $m=512$ and immediately get $\varphi(m)=256$.

The divisibility condition is necessary but not sufficient; we also need to choose a prime modulus $p$ whose order is $\varphi(m)/256$, i.e., the cyclic subgroup of $\mathbb{Z}_m^*$ generated by $p$ should have that order. This is a bit more subtle. One method that can work is to use the Chinese Remainder Theorem: we know that $\mathbb{Z}_m^*$ is isomorphic to the product of the groups $\mathbb{Z}_{p_i^{e_i}}^*$, so we can find a suitable condition in each component and then use CRT to find a suitable prime $p$.

An extreme example is when $m=512$ (so $\varphi(m)=256$). Then it is necessary and sufficient to take a prime $p$ of order 1, i.e., $p=1 \pmod m$. More generally, for odd $p_i$ the component $\mathbb{Z}_{p_i^{e_i}}^*$ is cyclic, so we can find an element $g_i$ of any order that divides the order of the component, and we want the product of these orders (of the $g_i$) to be 256. Finally, then, we can seek a prime $p$ that is congruent to $g_i \pmod{p_i^{e_i}}$ for all $i$. This may give us what we want overall, but beware that the order of $p$ may not be the product of its orders in each CRT component, so some trial and error may be needed.

---

Solution 2:

You have to consider the following things:

1. Bit length of the ciphertext moduli chain ($Q := q_1 \cdot ... \cdot q_\ell$) that provides enough multiplicative levels for your application (you are using 778 in your example).
2. Minimal $m$ that guarantees 80 bits of security for such bit length of $Q$.
3. You need $m$ such that $\phi(m)$ is divisible by 256 (as Chris Peikert explained in his answer).
4. You need a plaintext modulus $p$ such that $\phi(m) / d = 256$, where $d$ is the multiplicative order of $p$ modulo $m$.

These four items are actually interdependent and circular (for example, increasing $m$ and $p$ also reduces the number of levels you have to operate homomorphically, so you may have to increase $Q$, which reduces the security, so you may have to increase $m$...). But even so, it is not hard to find parameters at the end.

For example, an easy way to satisfy item (3.) is to choose $m = 512 \cdot k$ for some $k$. In particular, $m$ can be a power of two. For 80 bits of security and moduli chain with 778 bits, $m = 512 \cdot 95$ or $m = 2^{15}$ should be enough (but you have to verify it!). What is left then is finding $p$. For this, you can run a "brute force" search.

For example, by running the following Sage script on SageMath Cell, you get $p = 193$.

m = 512 * 95 
p = 3
NUMBER_OF_TRIES = 2**13
for _ in range(NUMBER_OF_TRIES):
    if 0 != m % p: # p divides m, skip
        d = Mod(p, m).multiplicative_order()
        if euler_phi(m) == d * 256:
            print("p = %d" % p)
            break
    p = next_prime(p)