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

Abstract

Privacy-preserving machine learning and encrypted statistics increasingly require evaluating long chains of matrix products directly on ciphertexts. In the CKKS homomorphic encryption scheme, however, every multiplication amplifies noise and enlarges ciphertexts, so the available precision budget is exhausted after only a few products. This work establishes c F H E (compressed FHE), a unified analytical and empirical framework that integrates low-rank matrix factorization techniques into the CKKS homomorphic encryption scheme. Its central idea is a co-design: instead of tuning the low-rank approximation and the cryptographic parameters in isolation, c F H E balances the two error sources against each other so that neither wastes precision. 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. Concretely, this co-design is realized as a precision-balancing model that, for a target accuracy, automatically selects the CKKS parameters: the polynomial modulus degree, the modulus chain, and the scaling factor. 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. c F H E is agnostic to other CKKS optimizations and can be combined with them for further gains.