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!
|
| _version_ | 1849219837942824960 |
|---|---|
| author | Jiwon Heo Joonsoo Yoo Baekyung Song Jiwon Yoon |
| author_facet | Jiwon Heo Joonsoo Yoo Baekyung Song Jiwon Yoon |
| author_sort | Jiwon Heo |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-2f7b69225488443d86c1437f5b3e95f3 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-2f7b69225488443d86c1437f5b3e95f32025-01-01T00:01:32ZengIEEEIEEE Access2169-35362024-01-011219815619816610.1109/ACCESS.2024.352240010816018Accelerating Secure Permutation: Application to Matrix AlgebraJiwon Heo0https://orcid.org/0009-0005-1716-9237Joonsoo Yoo1https://orcid.org/0000-0001-6377-2348Baekyung Song2https://orcid.org/0000-0002-3625-9925Jiwon Yoon3https://orcid.org/0000-0003-2123-9849Graduate School of Quantum Science and Technology, Korea Advanced Institute of Science and Technology, Yuseong-gu, Daejeon, Republic of KoreaSchool of Cybersecurity, Korea University, Seongbuk-gu, Seoul, Republic of KoreaSchool of Cybersecurity, Korea University, Seongbuk-gu, Seoul, Republic of KoreaSchool of Cybersecurity, Korea University, Seongbuk-gu, Seoul, Republic of KoreaHomomorphic 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.https://ieeexplore.ieee.org/document/10816018/Homomorphic encryptionextractionpermutationmatrix algebra |
| spellingShingle | Jiwon Heo Joonsoo Yoo Baekyung Song Jiwon Yoon Accelerating Secure Permutation: Application to Matrix Algebra IEEE Access Homomorphic encryption extraction permutation matrix algebra |
| title | Accelerating Secure Permutation: Application to Matrix Algebra |
| title_full | Accelerating Secure Permutation: Application to Matrix Algebra |
| title_fullStr | Accelerating Secure Permutation: Application to Matrix Algebra |
| title_full_unstemmed | Accelerating Secure Permutation: Application to Matrix Algebra |
| title_short | Accelerating Secure Permutation: Application to Matrix Algebra |
| title_sort | accelerating secure permutation application to matrix algebra |
| topic | Homomorphic encryption extraction permutation matrix algebra |
| url | https://ieeexplore.ieee.org/document/10816018/ |
| work_keys_str_mv | AT jiwonheo acceleratingsecurepermutationapplicationtomatrixalgebra AT joonsooyoo acceleratingsecurepermutationapplicationtomatrixalgebra AT baekyungsong acceleratingsecurepermutationapplicationtomatrixalgebra AT jiwonyoon acceleratingsecurepermutationapplicationtomatrixalgebra |