Welcome to the resource topic for 2025/1892
Title:
Optimizing FHEW-Like Homomorphic Encryption Schemes with Smooth Performance-Failure Trade-Offs
Authors: Deokhwa Hong, Yongwoo Lee
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%.
ePrint: https://eprint.iacr.org/2025/1892
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .