Faster Secure Matrix Multiplication Using the Strassen Algorithm

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

503
views

111
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