Firstly, could you recommend any good resources on the mathematical aspects of batching/packing techniques in FHE?
First, I would recommend the original paper that introduced SIMD (batching/packing) techniques: Fully Homomorphic SIMD Operations
Another classical introduction is Design and implementation of HElib: a homomorphic encryption library (Plaintext algebra section)
Note that in practice we often work with power-of-two cyclotomic rings and choose prime moduli that are congruent to 1\mod 2N, where N is the ring dimension, which leads to the so-called CRT decomposition into linear terms (one coefficient is used for one slot).
I’m curious about the distinction between batching and packing. Are they interchangeable terms, or do they represent different concepts in FHE?
In most situations, they are used interchangeably. The classical packing is CRT packing, which supports component-wise multiplication of vectors of numbers. The high-level idea is similar to the use of FFT/NTT for efficient polynomial multiplication. The vector of numbers is encoded using an inverse FFT/NTT and injected in the ciphertext space.
Some works refer to batching when numbers are encoded as polynomial coefficients. However, this supports batched operations only for addition and scalar multiplication (no component-wise multiplication is supported; the multiplication in this case refers to polynomial multiplication), hence it is a limited form of batching.
In OpenFHE, the CRT encoding in BGV/BFV is called Packed and the coefficient encoding as CoefPacked. The latter has no constraints for selecting the plaintext modulus.
How do batching techniques vary across FHE schemes like CKKS and BGV/BFV? Is the approach the same, or are there differences?
In CKKS, the encoding is done using a special form of FFT (over complex numbers). In BGV/BFV, the encoding is done using NTTs (over finite fields). Conceptually the approach is the same.
I’m wondering why batching is not possible in TFHE. Could you shed some light on the reasons behind this limitation?
In classical TFHE, the ring structure is used internally for bootstrapping (the secret key and other values are encoded into a native ciphertext polynomial when working with Ring GSW ciphertexts). Hence there is no room left for batching.
Lastly, does the batch size in OpenFHE impact the ciphertext size or the performance of operations?
To some extent. In the SIMD setting, rotations are more expensive (they rely on the operation of automorphism). Rotations in in the non-SIMD setting are trivial (ciphertexts are simply rearranged). Typically the maximum batch size is the ring dimension. We often desire the highest batch size to maximum the throughput (do more operations in parallel).