The relationship between polynomial degree and HE performance

It's difficult to succinctly answer this, as understanding this question is the bulk of research into Fully Homomorphic Encryption (i.e. there are many papers). Still, the following is the beginning of an answer.

At a high level, fully homomorphic encryption starts with a "cryptosystem with linear decryption". This is some cryptosystem such that to decrypt, one computes $(C, \mathsf{sk})\mapsto C^t\mathsf{sk}$. I'll discuss two basic examples of this first, but the paradigm is everywhere in the field.

1. LWE-based encryption. Ciphertexts are $C:= (A, A\vec s + (q/2)\vec m + \vec e)\in\mathbb{Z}_q^{m\times n}\times \mathbb{Z}_q^m$. Relative to the secret key $\mathsf{sk} := [-\vec s, 1]\in\mathbb{Z}_q^{n+1}$, these satisfy $C^t\mathsf{sk} = (q/2)\vec m + \vec e$

2. RLWE-based encryption. Ciphertexts are $C: = (a(x), a(x)s(x) + (q/2)m(x) + e(x))\in(\mathbb{Z}_q[x]/(x^{2^k}+1))^2$. Relative to the secret key $\mathsf{sk} := [-s(x), 1]$, these satisfy $C^t\mathsf{sk} = (q/2)m(x) + e(x)$.

One can write similar formula for things like NTRU, or Mersenne prime cryptosystems, or Module-LW(R), etc. Note that in these formula, upon decryption you recover a "message"|

$$(q/2)\vec m + \vec e,$$

where $\vec m\in\{0,1\}^m$ we care about, and $\vec e$ (which is hopefully $\lVert \vec e\rVert_\infty < q/4$) is garbage that we will remove via some error-correction process. While it may be tempting to think $\vec m$ should be the result of decryption, things are conceptually much easier if this noisly-encoded message is the result.

Anyway, give such a cryptosystem, there are roughly three ways we can define multiplication (and two are quite similar honestly). They all have different noise-growth characteristics.

Tensoring: Given linear-algebraic objects (generalizations of vectors and matrices), we can define the tensor product. For matrices this is is the block matrix

$$A\otimes B = \begin{pmatrix}a_{11}B & a_{12}B & \dots &a_{1n}B \\ a_{21} B & a_{22}B & \dots & a_{2n}B \\ \vdots &&\ddots&\vdots \\ a_{m1}B & a_{m2}B & \dots & a_{mn}B\end{pmatrix}$$

Tensor products satisfy the useful "mixed product property", meaning that $(A\otimes B)(C\otimes D) = (AB)\otimes (CD)$, at least when the dimensions of the matrices line up so all of the products are well-defined.

It follows that if we have

$$C_0^t \mathsf{sk}_0 := (q/2)\vec m_0 + \vec e_0,\qquad C_1^t \mathsf{sk}_1 := (q/2)\vec m_1 + \vec e_1,$$

Taking tensor products and applying the mixed-product property, we get that

$$(C_0\otimes C_1)^t (\mathsf{sk}_0\otimes \mathsf{sk}_1) = (C_0^t\mathsf{sk}_0)\otimes (C_1^t\mathsf{sk}_1) = ((q/2)\vec m_0 + \vec e_0)\otimes ((q/2)\vec m_1+\vec e_1) = (q/2)^2 (\vec m_0\otimes \vec m_1) + (q/2)(\vec m_0\otimes \vec e_1 + \vec e_0+\vec m_1) + \vec e_0\otimes \vec e_1.$$

So, by taking tensor products of ciphertexts, we can recover tensor products of matrices, plus some "error terms". This technique has a number of issues, fvor example

1. These tensor products increase the size of ciphertexts. For example, if $C_0, C_1$ have "dimension" $n$, then $C_0\otimes C_1$ has "dimension" $n^2$. To multiply together $k$ things you end up with dimension $n^{k}$. As $n\approx 1000$ for security reasons, this is bad. One can fix it with a technique called "relinearization", but it requires doing an additional computation, and including some encrypted key materials in queries.

2. These tensor products increase the size of the garbage terms $\vec e$. Our starting error was $\vec e_0, \vec e_1$, and our ending error was (after "modulus switching" down by $q/2$, which is common) $\vec m_0\otimes \vec e_1 + \vec e_0\otimes \vec m_1 + \frac{\vec e_0\otimes \vec e_1}{q/2}$. One can use standard techniques (bootstrapping) to reset the error, but it takes a decent amount of compute, and even more encrypted key material.

Anyway, this multiplication technique is at the core of things like BGV, B/FV, and CKKS.

Gadgets

The alternative way of dealing with errors use what are known as gadgets. The definition of these are technical, but essentially they allow us to have a trade-off between

1. the dimension of an object, and
2. the size of coefficients of an object.

The main idea is writing an element $x$ of $\mathbb{Z}_q$ in its base-2 decomposition $x = \sum_i x_i2^i$. This allows us to use a $\log_2 q$-dimensional representation of $x$ that

1. behaves well with linear operations (that FHE is generally good at handling), and

2. has $\max_i |x_i|$ small (FHE is only good at linear operations that involve multiplications with "small coefficients").

How do we get multiplications from these objects? It is somewhat technical. Fortunately, it has already been writing up pretty coherently in Bootstrapping in FHEW-like cryptosystems, so I'll omit rewriting a worse version of that here.

Regardless of the technical details, the performance of multiplications using gadgets is quite different than that from tensoring. For example

1. the dimension no longer grows rapidly with repeated operations, i.e. you don't need relinearization keys, but

2. the noise growth depends on the size of the messages, i.e. it is hard to use for things other than computing on small messages (say $m\in\{0,1\}$). This is what GSW uses to provide FHE for binary circuits.

3. For appropriate settings, (messages constrained to $\{0,1\}$) the noise growth is additive rather than multiplicative, i.e. much slower.

Still, cryptographers get quite a lot of use from these small messages $m\in\{0,1\}$, by encoding messages in the exponent of polynomials, i.e. writing $m'(x) = \sum_{i} x^{m_i}$. The coefficients of the polynomials are all small (in $\{0,1\}$), regardless of their degree $m_i$ (which may be large). This encoding technique is the basis of cryptosystems like FHEW, TFHE, and FINAL. It yields good performance, but makes it difficult to encode large messages --- encrypting $m\in\mathbb{Z}/2^{32}\mathbb{Z}$ would require working with polynomials of degree $2^{32}$, i.e. objects that take $2^{32}\log q$ bits to store (where $q\approx 3000$ is typical, although in extreme settings $q\approx 256$ is the lowest that can be used). This is to say we take on the order of gigbytes to encode a 32-bit integer. Fortunately the story is better for 8 bit integers, where we instead take on the order of ~1 kilobyte maybe.

The short answer is then that

1. BGV and B/FV (and CKKS) use tensoring for multiplication. This is very bad at computing high-degree polynomials, due to a combination of ciphertext size blowup (which can be controlled with relinearization, at a cost), and error blowup (which can be controlled with bootstrapping, again at a cost)

2. GSW use gadgets for multiplication. These can compute large-degree polynomials, though one is quite constrained by the intermediate size of the encrypted messages during the computation to control noise-growth. Additionally, the computational time (to control noise growth) scales linearly in $N$ (one can write a $\log N$-depth circuit to compute the product $x\mapsto x^N$. This does not behave well for GSW-type multiplication).

3. FHEW/TFHE/FINAL, which are built using GSW, can compute arbitrary functions fairly efficiently. The issue is that these functions are functions represented as truth-tables of $b$-bit numbers, where practically $b\approx 10$ at most. So computing simple 32-bit addition and multiplication becomes more complex than it is in the previously-described schemes (but for low precision, everything is quite simple/efficient).