D-5 RNS-variant FHE Schemes

The FHE parameters of BFV, BGV, or CKKS schemes, which are secure enough, sometimes require the ring size of polynomial coefficients to be 1000 bits or more, consuming significant computational resources for 64-bit CPU architectures. To make the computation efficient, we can alternatively represent the coefficients of ciphertext polynomials using the number residue system (RNS) §A-13.1, which allows for modulo addition and multiplication of elements from a large ring (e.g., 1000 bits) by combining values computed in small rings (e.g., 32$\sim$64 bits), each of which compactly fits in 64 bit CPU registers. Modern BFV, BGV, and CKKS schemes adopt this RNS approach by default for the efficient computation of large values. These are called RNS-variant FHE schemes.

While RNS can directly compute modulo addition and multiplication, it does not directly support other operations such as ModRaise or modulus switching, which are essential for all FHE schemes. This section explains how we can design such corner-case operations based on RNS to accomplish a complete design of RNS-based FHE schemes. Besides BFV, BGV, and CKKS, TFHE can also theoretically use RNS for representing its ciphertext coefficients. However, TFHE’s practically used coefficient size is less than $2^{32}$ (or $2^{64}$), which compactly fits within 32-bit (or 64-bit) modern CPU registers. Therefore, TFHE does not need RNS. Thus, this section will focus on RNS-based operations for BFV, BGV, and CKKS.

Particularly in this section, we assume that the modulo reduction $amodq=|a{|}_q$ implicitly uses a centered (i.e., signed) residue representation (§A-1.5), whose modulo overflow & underflow boundaries are ${\displaystyle \frac{q}{2}}-1$ and $-{\displaystyle \frac{q}{2}}$, respectively. This assumption is necessary to eliminate a certain modulo reduction operation when designing FastBconvEx (§D-5.8) by using the assumption of limiting the possible range of certain residue arithmetic, as discussed in §A-1.5.