.png){kind=icon}
.png){kind=icon}
Return
Accelerating Secure Permutation: Application to Matrix Algebra
.png){kind=icon}
OA
AI
DOI：10.1109/ACCESS.2024.3522400.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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<^>{2})$ , 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 \times $ efficiency improvement, and for matrix multiplication, we achieved up to $2.39 \times $ improvement over the classical method.
Keywords:
Matrices
Vectors
Polynomials
Single instruction multiple data
Time complexity
Homomorphic encryption
Data analysis
Noise
Fast Fourier transforms
Tensors
extraction
permutation
matrix algebra