D-5 RNS-variant FHE Schemes

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, which consumes much computational resources for 64-bit CPU architectures. To make the computation efficient, we can alternatively represent the coefficients of ciphertext polynomials by the number residue system (RNS) §A-13.1, which allows modulo addition and multiplication of elements from a large ring (e.g., 1000 bits) by the combination of 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 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 switch, which are essential operations 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 in 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 the modulo reduction $amodq=|a{|}_q$ implicitly uses a centered (i.e., signed) residue representation (§A-1.2.3) 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.2.3.