시작하기
FHE A Fast Heuristic

for Mapping Boolean Circuits to Functional Bootstrapping

불리언 회로를 함수형 부트스트래핑 명령으로 자동 매핑하는 휴리스틱으로, 수작업으로 최적화된 구현 대비 평가 시간을 45% 단축합니다.

저자

Dr. Sergiu Carpov

게시됨

August 18, 2025

주제

FHE

게재처

IACR

키워드

Functional bootstrapping, Boolean circuit mapping, Fully Homomorphic Encryption

PDF 보기
초록

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.