What is batching in homomorphic encryption? I have been reading journals about FHE schemes and I keep encountering the term &quot;batching&quot;. What does it mean to batch in homomorphic encryption in a simple way?
In simple terms, batching means &quot;encrypt many messages into a single ciphertext so that one homomorphic operation acts on many messages simultaneously&quot;.
This is typically done by representing the message space in a &quot;tuple&quot; format (via an isomorphism).
For instance, by the Chinese remainder theorem (CRT), we know that any tuple
$(m_1, m_2, m_3) \in \mathbb Z_2 \times \mathbb Z_3 \times \mathbb Z_5$
can be written as a single integer $m \in \mathbb Z_{30}$.
Thus, if you have a homomorphic scheme whose message space is $\mathbb Z_{30}$,
we can encrypt tuples
$(m_1, m_2, m_3)$
and each homomorphic operation will actually operate on three values.
In this scenario, you would start from $(m_{1,i}, m_{2,i}, m_{3,i})$,
then obtain $m_i$ via CRT, then encrypt $m_i$ into $c_i$.
Now, if you multiply two ciphertexts $c_1$ and $c_2$ homomorphically,
you obtain an encryption of
$m_1 \cdot m_2 \bmod 30$,
but this is actually equivalent to
$$(m_{1,1}\cdot m_{1,2}\bmod 2,
 \,m_{2,1}\cdot m_{2,2}\bmod 3,
 \,m_{3,1}\cdot m_{3,2}\bmod 5).$$
So, one homomorphic multiplication is multiplying three messages in parallel. Of course, instead of 3, you want a tuple with many entries.
Things work essentially in the same way for polynomials, i.e., you represent a tuple of polynomials of low degree as a single polynomial of high degree, then you encrypt it...