FHE.org Toronto

Abstract

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 bootstrapping procedure allows to manage the noise growth through the homomorphic evaluation process. FHEW-like bootstrapping has been shown to be able to evaluate discretized arbitrary functions at some additional cost compared to the gate bootstrapping. One of its major limitation 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 works aims at overcoming these limitations to enable functional bootstrapping, and more generally homomorphic evaluations over large input domains. In this work, we build on a previous work of Iliashenko et al. (PoPets 2022) and propose a computational and data efficient client-server protocol for the homomorphic evaluation arbitrary functions defined over a large domain. Compared to the previous work, we obtain a server-side amortized time of 120$\mu$ and 170$\mu$ per point over batches of 2048 points for functions $Z_{2^{14}} \rightarrow Z_{2^{14}}$ and $Z_{2^{15}} \rightarrow Z_{2^{15}}$ respectively, which is over a $2000\times$ improvement over the original approach, which needs $0.31$ and $0.39$ sec per point respectively. The client-side work remains unchanged, the response size per batch of 2048 points is 32KB and the data complexity of the key material is 1.5MB. Additionally, we propose an improvement to the original approach that reduces the number of switching keys from $\mathcal{O}(N)$ to $\mathcal{O}(\log N)$.

Jean-Philippe Bossuat

Cryptography Research Scientist & Software Specialist

My research interests include applied lattice based cryptography, privacy preserving machine learning and secure analytics.