Accelerating Secure Permutation: Application to Matrix Algebra

Homomorphic encryption (HE) is a critical tool for ensuring privacy and security in computing on sensitive data within untrusted environments. While HE offers advantages in non-interactive secure computation, it has not yet become practical for data analysis involving costly matrix operations in high-dimensional spaces. In this paper, we present an innovative approach to accelerating the extraction procedure in the permutation of matrices in vector representation, specifically addressing the challenges posed by SIMD structures within BGV-like schemes. Our work significantly accelerates matrix operations, as these operations inherently involve the permutation of matrices in the HE setting. For the extraction operation, we achieved a time complexity of O(kN + k²), a notable improvement over the traditional O(N log N), making our method particularly beneficial in scenarios with large disparities between the polynomial degree N and the number of extracting elements k. In our experiments, the proposed extraction method showed up to 7.55 × efficiency improvement, and for matrix multiplication, we achieved up to 2.39 × improvement over the classical method.