1
$\begingroup$

I have been reading journals about FHE schemes and I keep encountering the term "batching". What does it mean to batch in homomorphic encryption in a simple way?

$\endgroup$
1
  • $\begingroup$ What sources did you read and what is confusing you? like this one encrypting and homomorphically processing a vector of plaintext bits as a single ciphertext. from abstract of this 363 times cited article! $\endgroup$ – kelalaka Nov 13 '20 at 10:01
2
$\begingroup$

In simple terms, batching means "encrypt many messages into a single ciphertext so that one homomorphic operation acts on many messages simultaneously".

This is typically done by representing the message space in a "tuple" 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...

$\endgroup$
1
$\begingroup$

Purpose of batching

Batching is a way to improve the performance of homomorphic encryption, essentially making it faster. But it does (as far as I know) not in any way improve the security aspect of homomorphic encryption.

Homomorphic encryption is still a performance-heavy procedure (see this previous question "Why are homomorphic algorithms slow?" for further information).

As explained in the abstract of the paper "On-the-fly Homomorphic Batching/Unbatching":

We introduce a homomorphic batching technique that can be used to pack multiple ciphertext messages into one ciphertext for parallel processing. One is able to use the method to batch or unbatch messages homomorphically to further improve the flexibility of encrypted domain evaluations. In particular, we show various approaches to implement Number Theoretic Transform (NTT) homomorphically in FFT speed. [...] The advantage of this method is we are able to batch independent homomorphic NTT evaluations and achieve better amortized time.


Security of batching

The previously mentioned paper apparently may even decrease the level of security, while still guaranteeing some level of security. Section 6 - Implementation Results:

The security level of the experiments varies on the settings, but each setting has at least 100-bit security.

I also found this paper "Batch Fully Homomorphic Encryption over the Integers", where at least semantic security is apparently provided.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.