A Multi-Key Homomorphic Scheme Based on Multivariate Polynomial Look-Up Tables Evaluation

Multi-key homomorphic encryption (MKHE) is crucial for secure collaborative computing, yet it suffers from high multiplicative depth and computational overhead during Look-Up Table (LUT) evaluations, particularly for large input domains. To address these challenges, this paper proposes an optimized LUT evaluation method based on multivariate polynomial approximation. Specifically, we partition the high-dimensional input space into several lower-dimensional variables to design low-depth multivariate polynomials. By integrating blockwise encoding and tensor-based transformations, we construct a parallelizable evaluation framework that maps multivariate functions into a high-dimensional polynomial-coefficient space. This approach allows for efficient parallel processing and effective noise management. Theoretical analysis demonstrates that our method significantly reduces the multiplicative depth from O(l) to O(l/α), indicating its robustness and efficiency in large-scale LUT scenarios.