Get started
FHE A Fast Heuristic

for Mapping Boolean Circuits to Functional Bootstrapping

A heuristic that automatically maps Boolean circuits to functional bootstrapping instructions, achieving a 45% reduction in evaluation time over hand-optimized implementations.

Authors

Dr. Sergiu Carpov

Published

August 18, 2025

Topic

FHE

Published in

IACR

Keywords

Functional bootstrapping, Boolean circuit mapping, Fully Homomorphic Encryption

View PDF
Abstract

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