Optimized Homomorphic Vector Permutation From New Decomposition Techniques

Homomorphic vector permutation is fundamental to privacy-preserving computations based on batch-encoded homomorphic encryption, underpinning nearly all homomorphic matrix operation algorithms and predominantly influencing their complexity. A potential approach to optimize this critical component lies in permutation decomposition, a technique we consider as not yet fully explored. In this paper, we enhance the efficiency of homomorphic permutations through novel decomposition techniques, thus advancing privacy-preserving computations. We start by estimating the ideal performance of decompositions on permutations and proposing an algorithm that searches depth-1 ideal decomposition solutions. This enables us to ascertain the full-depth ideal decomposability of specific permutations in homomorphic matrix transposition (SIGSAC 18) and multiplication (CCSW 22), allowing these privacy-preserving computations to achieve asymptotic improvement in speed and rotation key reduction. We further devise a new method for computing arbitrary homomorphic permutations, aiming to approximate the performance of ideal decomposition, as permutations with weak structures are unlikely to be ideally factorized. Our design deviates from the conventional scope of permutation decomposition. It outperforms state-of-the-art techniques (EUROCRYPT 12, CRYPTO 14) with a speed-up of up to $\times2.27$ under the minimum requirement of rotation keys.