Optimized Homomorphic Permutation From New Permutation Decomposition Techniques

Homomorphic permutation is fundamental to privacy-preserving computations based on batch-encoding homomorphic encryption. It underpins nearly all homomorphic matrix operation algorithms and predominantly influences their complexity. Permutation decomposition as a potential approach to optimize this critical component remains underexplored. In this paper, we enhance the efficiency of homomorphic permutations through novel decomposition techniques, advancing homomorphic encryption-based privacy-preserving computations. We start by estimating the ideal effect of decompositions on permutations, then propose an algorithm that searches depth-1 ideal decomposition solutions. This helps us ascertain the full-depth ideal decomposability of permutations used in specific secure matrix transposition and multiplication schemes, allowing them to achieve asymptotic improvement in speed and rotation key reduction. We further devise a new method for computing arbitrary homomorphic permutations, considering that permutations with weak structures are unlikely to be ideally factorized. Our design deviates from the conventional scope of decomposition. But it better approximates the ideal effect of decomposition we define than the state-of-the-art techniques, with a speed-up of up to $\times 2.27$ under minimal rotation key requirements.