Eidolon: Perform Noise-Aware Fuzzing on FHE Libraries via Equivalence Expression Transformation

Ensuring data privacy during computation is a critical challenge in many security systems. Fully Homomorphic Encryption (FHE) addresses this gap by enabling multiple operations on encrypted data without decryption, thus ensuring privacy is preserved throughout computation. However, existing cryptographic testing tools are unable to test the core functionality of FHE, which is the execution of computations on encrypted data. They are expertly designed to generate structured data for testing cryptographic algorithms. This structural mismatch, combined with a lack of awareness of FHE-specific noise management, leads them to generate invalid test inputs that fail to probe FHE libraries' core logic.

To address this gap, we propose Eidolon, a noise-aware fuzzer. It directs mutations toward arithmetic expressions that explore the computational space defined by the noise budget. As its test oracle, Eidolon leverages Equivalence Expression Transformation, which transforms a standard arithmetic expression into two mathematically identical but structurally different forms (e.g., Factored, Horner) to detect inconsistencies in their outputs. We evaluated Eidolon on SEAL, OpenFHE, HElib, and TFHE. Compared with existing cryptographic and grammar-based fuzzers, Eidolon achieves 28.7%, 45.5%, 75.6%, and 37.6% higher final code coverage than CLFuzz, Cryptofuzz, CDF, and Peach, respectively. In total, Eidolon uncovered 20 previously unknown bugs, 10 of which have been fixed and 12 assigned CVEs.

CCS Concepts: • Software and its engineering → Software testing and debugging.