Paper 2026/845

Compressed FHE: Accelerating Encrypted Matrix Multiplication in CKKS with Precision-Balanced Low-Rank Factor Chains

Maryam Sabzevari, Nokia Bell Labs, Finland

Abstract

This work establishes cFHE (compressed FHE), a unified analytical and empirical framework that integrates low-rank matrix factorization techniques into the CKKS homomorphic encryption scheme. Theoretical bounds are derived for the accumulation of relative error across sequences of factorized matrices, leading to an explicit expression for the attainable computation depth as a function of target accuracy, norm amplification behavior, and per-layer approximation quality. Extensions to tree-based evaluation structures are also formulated, allowing depth to scale logarithmically with the number of factors. The analytical results are linked to CKKS arithmetic through a precision-balancing model that connects low-rank approximation errors and ciphertext noise. This connection is at the core of cFHE; it enables the automatic selection of CKKS parameters (polynomial modulus degree, modulus chain, and scaling factor) for a desired accuracy, ensuring that low-rank tolerances and cryptographic precision are jointly optimized. Experimental evaluations demonstrate that encrypted low-rank matrix multiplications achieve both significant runtime improvements and reduction of ciphertext sizes over direct or tree-based encrypted multiplications while maintaining the prescribed accuracy. cFHE is agnostic to other CKKS optimizations and can be combined with them for further gains.