Large Domain Homomorphic Evaluation for BFV-like schemes via Ring Repacking

Fully homomorphic encryption allows to evaluate arbitrary functions over encrypted data. A general rule of (R)LWE-based homomorphic encryption is that when the depth of a circuit increases, the quality of the ciphertext decreases.The gate bootstrapping procedure allows to manage the noise growth through the homomorphic evaluation process. FHEW-like bootstrapping enables the evaluation of discretized arbitrary functions at some additional cost compared to gate bootstrapping. One of its major limitations is that, if one wants to keep it efficient, the precision of the message encoding functions needs to be restricted to relatively small sizes. For example, functions with domains larger than 8 bits of precision become difficult to evaluate in a reasonable amount of time. A recent line of work aims to overcome these limitations to improve the functional bootstrapping efficiency over large input domains.In this paper, we propose a different approach for the homomorphic evaluation of arbitrary functions built from ring-packing techniques that convert a set of LWE ciphertexts into a RLWE ciphertext. As an application, we propose a computational and data-efficient client-server protocol for the homomorphic evaluation of arbitrary functions defined over a large domain.We obtain a server-side amortized time of $0.12$ ms, $0.17$ ms per input over batches of 2048 inputs for functions defined over $\mathbb{Z}_{2^{14}}$ and $\mathbb{Z}_{2^{16}}$, respectively. Our solution also enables the client to retrieve many point evaluations almost for free.

Designs, Codes and Cryptography