Faster secure matrix multiplication using the strassen algorithm
Strassen algoritması ile daha hızlı güvenli matris çarpımı
- Tez No: 831461
- Danışmanlar: PROF. DR. ERSAN AKYILDIZ, PROF. DR. MURAT CENK
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Uygulamalı Matematik Enstitüsü
- Ana Bilim Dalı: Kriptografi Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 93
Özet
Bulutta, kişisel veriler güvenlik sorunlarına açıktır. Homomorfik şifreleme, şifrelenmiş veriler üzerinde hesaplamalara olanak sağlayarak gizlilik endişelerini gidermeye yönelik bir çözüm sunar. Bu hesaplamalar istatistiksel analiz veya makine ögrenme algoritmaları olabilir. Matris çarpımı şifrelenmiş verilere de uygulanabilir. Buna güvenli matris çarpımı denir. Güvenli matris çarpımı, istatistiksel analiz ve makine öğrenimi algoritmaları da dahil olmak üzere birçok uygulamadaki temel işlemlerden biridir. A ve B'nin iki kare matris olduğunu varsayalım; güvenli matris çarpım algoritması, her matris için sıkıştırılmış polinomlar oluşturur, bunları şifreler ve homomorfik olarak çarpar. Şifreyi çözdükten ve sıkıştırılmış polinomu açtıktan sonra A×B çarpım matrisini bulabiliriz. Büyük matrisler için homomorfik çarpım yapmak, sıkıştırılmış polinomların derecesinin ve şifreleme parametrelerinin artması nedeniyle zordur. Ayrıca büyük matrisler için homomorfik şifreleme işlemleri verimsiz hale gelir. Bu tezde, matrisleri alt bloklara böldükten sonra, güvenli matris çarpım algoritmasını uygulamaktayız ve iki matrisi güvenli bir şekilde çarpmak için performansı artırmak amacıyla Strassen algoritmasını kullanmayı önermekteyiz. Strassen algoritması bir seviye özyineleme kullanıldığında homomorfik şifreleme sayısını sekizden yediye düşürmektedir. Ayrıca, homomorfik şifreleme ve çarpmalar polinomların derecesindeki azalmadan dolayı daha verimli uygulanmaktadır. Güvenli matris çarpımı için Fan ve Vercauteren (FV) ve Brakerski, Gentry ve Vaikuntanathan (BGV) homomorfik şifreleme algoritmalarını uygulamaktayız. 8 ile 128 arasındaki farklı matris ve alt matris boyutları için uygulama sonuçları önemli gelişmeler göstermektedir. Örneğin, FV homomorfik şifreleme kullanıldığında 128 × 128 boyutlu matris için alt matris boyutu iki olduğunda Strassen güvenli blok matris çarpımı algoritması standart blok matris çarpımına göre %47 daha hızlıdır. Ayrıca, benzer şekilde, BGV algoritması kullanıldığında alt matris boyutu iki olan 128 × 128 boyutlu bir matris düşünüldüğünde, algoritma standart güvenli matris çarpımına kıyasla %44 daha hızlıdır. Bu nedenle, uygulamamız homomorfik şifreleme çerçevesinde güvenli matris çarpımı için Strassen yöntemini kullanmanın faydalarının altını çizerek, özellikle daha büyük boyutlar için matrisleri alt bloklara böldükten sonra performansı artırma potansiyelini vurgulamaktadır. Ayrıca, bir uygulama olarak, Strassen güvenli blok matris algoritmasını kullanarak şifrelenmiş verilerin çoklu doğrusal regresyonunu hesaplamakta ve sonuçları standart blok matris yöntemiyle karşılaştırmaktayız. Elde edilen sonuçlara göre, matris boyutu 128 ve alt matris boyutu iki olduğunda, Strassen'in güvenli blok matris çarpma algoritması ile çoklu doğrusal regresyon hesaplaması, standart güvenli blok matris çarpma algoritmasına göre %47 daha hızlıdır.
Özet (Çeviri)
In the cloud, private data is open to security problems. Homomorphic encryption offers 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 algorithm 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 applying 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 homomorphic encryptions and multiplications are performed more efficiently because of a decrease 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 dividing matrices into subblocks. Moreover, as an application, we calculate the multiple linear regression of encrypted data using the Strassen secure block matrix algorithmand 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 algorithm is 47% faster than the standard secure block matrix multiplication algorithm.
Benzer Tezler
- Kriptoparalarda kümeleme analizi uygulamaları
Cluster analysis applications of cryptocurrencies
EZGİ DOĞAN
Yüksek Lisans
Türkçe
2023
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. NİZAMETTİN BAYYURT
- FPGA tabanlı şifreli kablosuz haberleşme sistemi
FPGA based encrypted wireless communication system
ILGAZ AZ
Yüksek Lisans
Türkçe
2014
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDisiplinlerarası Ana Bilim Dalı
DOÇ. DR. GÖKHAN İNALHAN
- Makina halılarının yapısal özellikleri ile mekanik etkiler karşısındaki davranış özellikleri üzerine bir araştırma
The physics of woven carpets
ÖMER BERK BERKALP
Yüksek Lisans
Türkçe
1997
Tekstil ve Tekstil Mühendisliğiİstanbul Teknik ÜniversitesiTekstil Mühendisliği Ana Bilim Dalı
DOÇ. DR. EMEL ÖNDER
- İki ayaklı yürüyen robot için kontrol sistemi geliştirilmesi
Control system development for bipedal walking robot
NUMAN MERT TAN
Yüksek Lisans
Türkçe
2012
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ZEKİ YAĞIZ BAYRAKTAROĞLU
- Dağıtılmış üretim'e sahip elektrik dağıtım sistemlerinde, arıza akımı sınırlayıcılarının ve yerleşim yerlerinin etkilerinin incelenmesi
A study of the effects of fault current limiters and their location on power distribution system with distributed generation
GÖKHAN ÇAKAL
Yüksek Lisans
Türkçe
2012
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA BAĞRIYANIK