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 hig...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10816018/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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 <inline-formula> <tex-math notation="LaTeX">$O(kN + k^{2})$ </tex-math></inline-formula>, a notable improvement over the traditional <inline-formula> <tex-math notation="LaTeX">$O(N \log N)$ </tex-math></inline-formula>, 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 <inline-formula> <tex-math notation="LaTeX">$7.55 \times $ </tex-math></inline-formula> efficiency improvement, and for matrix multiplication, we achieved up to <inline-formula> <tex-math notation="LaTeX">$2.39 \times $ </tex-math></inline-formula> improvement over the classical method. |
|---|---|
| ISSN: | 2169-3536 |