New Permutation Decomposition Techniques for Efficient Homomorphic Permutation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911286913138688 |
|---|---|
| author | Ma, Xirong Fang, Junling Ge, Chunpeng Duong, Dung Hoang Jiang, Yali Li, Yanbin Susilo, Willy Cui, Lizhen |
| author_facet | Ma, Xirong Fang, Junling Ge, Chunpeng Duong, Dung Hoang Jiang, Yali Li, Yanbin Susilo, Willy Cui, Lizhen |
| contents | Homomorphic permutation is fundamental to privacy-preserving computations based on batch-encoding homomorphic encryption. It underpins nearly all homomorphic matrix operations and predominantly influences their complexity. Permutation decomposition as a potential approach to optimize this critical component remains underexplored. In this paper, we propose novel decomposition techniques to optimize homomorphic permutations, advancing homomorphic encryption-based privacy-preserving computations.
We start by defining an ideal decomposition form for permutations and propose an algorithm searching for depth-1 ideal decompositions. Based on this, we prove the full-depth ideal decomposability of permutations used in specific homomorphic matrix transposition (HMT) and multiplication (HMM) algorithms, allowing them to achieve asymptotic improvement in speed and rotation key reduction. As a demonstration of applicability, substituting the HMM components in the best-known inference framework of encrypted neural networks with our enhanced version shows up to $3.9\times$ reduction in latency.
We further devise a new method for computing arbitrary homomorphic permutations, specifically those with weak structures that cannot be ideally decomposed. We design a network structure that deviates from the conventional scope of decomposition and outperforms the state-of-the-art technique with a speed-up of up to $1.69\times$ under a minimal rotation key requirement. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_21840 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | New Permutation Decomposition Techniques for Efficient Homomorphic Permutation Ma, Xirong Fang, Junling Ge, Chunpeng Duong, Dung Hoang Jiang, Yali Li, Yanbin Susilo, Willy Cui, Lizhen Cryptography and Security Homomorphic permutation is fundamental to privacy-preserving computations based on batch-encoding homomorphic encryption. It underpins nearly all homomorphic matrix operations and predominantly influences their complexity. Permutation decomposition as a potential approach to optimize this critical component remains underexplored. In this paper, we propose novel decomposition techniques to optimize homomorphic permutations, advancing homomorphic encryption-based privacy-preserving computations. We start by defining an ideal decomposition form for permutations and propose an algorithm searching for depth-1 ideal decompositions. Based on this, we prove the full-depth ideal decomposability of permutations used in specific homomorphic matrix transposition (HMT) and multiplication (HMM) algorithms, allowing them to achieve asymptotic improvement in speed and rotation key reduction. As a demonstration of applicability, substituting the HMM components in the best-known inference framework of encrypted neural networks with our enhanced version shows up to $3.9\times$ reduction in latency. We further devise a new method for computing arbitrary homomorphic permutations, specifically those with weak structures that cannot be ideally decomposed. We design a network structure that deviates from the conventional scope of decomposition and outperforms the state-of-the-art technique with a speed-up of up to $1.69\times$ under a minimal rotation key requirement. |
| title | New Permutation Decomposition Techniques for Efficient Homomorphic Permutation |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2410.21840 |