Paper 2025/1892

Optimizing FHEW-Like Homomorphic Encryption Schemes with Smooth Performance-Failure Trade-Offs

Abstract

FHEW-like homomorphic encryption (HE) schemes, introduced by Ducas and Micciancio (Eurocrypt 2015), represent the most efficient family of HE schemes in terms of both latency and key size. However, their bootstrapping noise is highly sensitive to parameter selection, leaving only a sparse set of feasible parameters. Because bootstrapping noise directly affects security and performance, existing approaches tend to choose parameters that drive noise excessively low—resulting in large key sizes and high latency. In this paper, we propose a new bootstrapping modification that permits an almost continuous spectrum of parameter choices. In our best knowledge, this is the first practical HE scheme for which the evaluation failure probability is precisely determined without requiring any information about the message distribution. We further show that, under our method, the parameter‐optimization task reduces to a generalized knapsack problem solvable in polynomial time. As a result, the traditionally cumbersome process of selecting parameters for FHEW‐like schemes becomes tractable. Experimental results show that our method improves bootstrapping runtime by approximately 17% and reduces key size by about 45%.