FHEvolve: Constraint-Guided Evolution of Efficient FHE Programs

Fully homomorphic encryption (FHE) enables computation on encrypted data, but efficient implementations require coordinated choices of approximation methods, data layouts, multiplication depth, and rotation keys. General-purpose evolutionary code search can spend evaluations on infeasible candidates or repeatedly refine one algorithmic approach. We introduce FHEvolve, a framework that guides evolutionary optimization with reusable FHE knowledge. Given a workload specification, cryptographic configuration, and initial seed programs, FHEvolve extracts constraints, filters a library of algorithm strategies, preserves different strategy families during search, and translates execution failures into repair guidance. Across eight workloads spanning CKKS and BFV, FHEvolve improves the combined accuracy–latency score over vanilla OpenEvolve on several workloads while obtaining similar scores on others. On Softmax, encrypted evaluation time decreases from 8.48 to 7.11 seconds at unchanged measured accuracy. On encrypted fraud classification, a candidate selected under an additional probability-error constraint achieves a $1.3\times$ speedup and preserves agreement on 100 fresh examples; a faster candidate selected under binary agreement alone generalizes less well, highlighting the importance of the optimization objective. Against three FHE compilers (Orion, HEIR, CHEHAB), FHEvolve is the only system that produces a within-budget program for all eight workloads without a human-written algorithm, although a hand-tuned compiler is more accurate on two of them. These results support constraint-guided search as a practical approach to improving FHE programs, with benefits that depend on the workload and evaluation requirements.