Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
Faster Secure Matrix Multiplication Using the Strassen Algorithm
Download
Dilek_Tez_son (1).pdf
Date
2023-8-29
Author
Öner Şimşek, Dilek
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
96
views
0
downloads
Cite This
In the cloud, private data is open to security problems. Homomorphic encryption of fers a solution for addressing privacy concerns by enabling calculations on encrypted data. These computations may be statistical analysis or machine learning algorithms. Matrix multiplication also can be applied to the encrypted data. This is called secure matrix multiplication. Secure matrix multiplication is one of the primary operations in many applications, including statistical analysis and machine learning algorithms. Assume that A and B are two square matrices; the secure matrix multiplication al gorithm creates packed polynomials for each matrix, encrypts them, and multiplies homomorphically. After decryption and unpacking, we find the product matrix A×B. It is hard to do homomorphic multiplication for large matrices since the degree of the packed polynomials and the encryption parameters increase. In addition, for large matrices, homomorphic encryption operations become inefficient. In this thesis, we propose using the Strassen algorithm after dividing matrices into subblocks and ap plying a secure matrix multiplication algorithm to multiply two matrices securely to improve performance. The Strassen algorithm reduces the number of homomorphic multiplications from eight to seven in one-level recursion. Moreover, the homomor phic encryptions and multiplications are performed more efficiently because of a de crease in the degree of polynomials. We implement the Strassen algorithm for secure matrix multiplication using Fan and Vercauteren (FV) and Brakerski, Gentry, and Vaikuntanathan (BGV) homomorphic encryption algorithms. The implementation results for dimensions between 8 and 128 with different submatrix sizes demonstrate significant improvements. To illustrate, when the FV homomorphic encryption is used for 128 × 128 matrix with the submatrix size of two, the algorithm is 47% faster than the standard secure block matrix multiplication method. Similarly, when using the BGV algorithm and considering a 128 × 128 matrix with a submatrix size of two, the algorithm is 44% faster than the standard secure block matrix multiplication. So, our implementation highlights the benefits of using the Strassen method for secure matrix multiplication within the homomorphic encryption framework, emphasizing its potential to improve performance, especially for bigger dimensions after divid ing matrices into subblocks. Moreover, as an application, we calculate the multiple linear regression of encrypted data using the Strassen secure block matrix algorithm and compare results with the standard secure block matrix method. According to the results, when the matrix dimension is 128, and the submatrix size is two, computing the multiple linear regression with Strassen’s secure block matrix multiplication al gorithm is 47% faster than the standard secure block matrix multiplication algorthm.
Subject Keywords
Secure Matrix Multiplication, The Strassen Algorithm, Homomorphic Encryption
URI
https://hdl.handle.net/11511/105397
Collections
Graduate School of Applied Mathematics, Thesis
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
D. Öner Şimşek, “Faster Secure Matrix Multiplication Using the Strassen Algorithm,” Ph.D. - Doctoral Program, Middle East Technical University, 2023.