Abstract. Functional bootstrapping in FHE schemes such as FHEW and TFHE allows theevaluation of arbitrary functions on encrypted data, while simultaneously reducingnoise. Implementing programs that directly use functional bootstrapping is challengingand error-prone. In this paper, we propose a heuristic that automatically mapsBoolean circuits to functional bootstrapping instructions. Unlike prior approaches,our method does not limit the encrypted data plaintext space to a power-of-twosize, allowing the instantiation of functional bootstrapping with smaller parameters.Furthermore, the negacyclic property of functional bootstrapping is exploited toextend the plaintext effective space. Despite the inherently greedy nature of theheuristic, experimental results show that the mapped circuits exhibit a significantreduction in evaluation time. Our heuristic demonstrates a 45% reduction in evaluationtime when compared to hand-optimized Trivium and Kreyvium implementations.

Abstract. Functional bootstrapping in FHE schemes such as FHEW and TFHE allows theevaluation of arbitrary functions on encrypted data, while simultaneously reducingnoise. Implementing programs that directly use functional bootstrapping is challengingand error-prone. In this paper, we propose a heuristic that automatically mapsBoolean circuits to functional bootstrapping instructions. Unlike prior approaches,our method does not limit the encrypted data plaintext space to a power-of-twosize, allowing the instantiation of functional bootstrapping with smaller parameters.Furthermore, the negacyclic property of functional bootstrapping is exploited toextend the plaintext effective space. Despite the inherently greedy nature of theheuristic, experimental results show that the mapped circuits exhibit a significantreduction in evaluation time. Our heuristic demonstrates a 45% reduction in evaluationtime when compared to hand-optimized Trivium and Kreyvium implementations.