This post picks up at the point of considering BGV (Brakerski, Gentry, Vaikuntanathan) encryption variants based on Ring-LWE. Thought it may seem natural to start by considering the BGV enciphering function, I will avoid discussing this since is actually quite simple in principle and essentially consists of polynomial mixing and sampling from an error distribution. Also, it is described well in a post on Windows on Theory by Boaz Barak and Zvika Brakerski that can be found here:

http://windowsontheory.org/2012/05/02/building-the-swiss-army-knife/

Instead, I’d like to delve into the plaintext algebra of the “Ring-LWE” BGV variant in order to understand the encoding / representation of plaintext bits in the scheme . In this post, we consider the idea of batched homomorphic operations and so called ‘plaintext slots’, along with some of the basic algebra that supports the specification of plaintext slots.

In particular, we consider the Ring-LWE BGV variant defined over rings of form:

\mathbb{A} = \mathbb{Z}[X] / \Phi_m(X) where  m  is a parameter and  \Phi_m(X) is the m' th cyclotomic polynomial whose roots are the primitive m 'th roots of unity.  The native plaintext space for this variant is taken to be the ring:

\mathbb{A}_2 = \mathbb{A}/2\mathbb{A}

Note that the cyclotomic polynomial factors into r  irreducible factors mod 2 (which follows partially from the fact that the cyclotomic extension \mathbb{Q}(\zeta_m)/\mathbb{Q} is Galois) :

\Phi_m(X) = F_1(X)\cdot F_2(X) \cdot \cdot \cdot F_r(X) mod 2

Lets cover some background around Chinese Remaindering and homomorphisms of rings – Consider F(X) \in \mathbb{F}_2[X], a monic polynomial of degree N that splits into r distinct irreducible factors of degree d = N/r, viz. F(X)=\prod_{i = 1}^{r}F_i(X) . (In the case of F(X) = \Phi_m(X) mod 2 we have d \times r = \phi(m)). Let A denote the ring

A = \mathbb{F}_2[X]/(F(X))

which is the quotient of \mathbb{F}_2[X] modulo the ideal generated by F(X)

By the Chinese remainder theorem, there is the isomorphism:

A \cong \Bbb{F}_2[X]/F_1(X) \otimes \Bbb{F}_2[X]/F_2(X) \otimes\dots\otimes \Bbb{F}_2[X]/F_r(X)

\cong \Bbb{F}_{2^d} \otimes \dots \otimes \Bbb{F}_{2^d}

So that A is isomorphic to r copies of \Bbb{F}_{2^d} (fields of d bit strings).

This captures central idea around the of  batching homomorphic operations -We start by encoding individual bits in the r distinct plaintext fields \Bbb{F}_{2^d}. More precisely, we are not just confined to representing bits, but any element in the ring. For example, if 8 divides d, then we can represent a byte since in this case there is an embedding of \mathbb{F}_{2^8} in \mathbb{F}_{2^d}. Then, rather than evaluating functions on the individual bits or ring elements, we use the isomorphism above and work in the ring A. Evaluating a function once in A implicitly evaluates the function in parallel over the r distinct plaintext spaces \Bbb{F}_{2^d}. The ring \mathbb{A}_2 is typically referred to as the “aggregate” plaintext space in BGV, and the sub-rings \mathbb{Z}_2[X]/F_i(X) are referred to as the “embedded” plaintext spaces or “slots”.