Geri Dön

Faster secure matrix multiplication using the strassen algorithm

Strassen algoritması ile daha hızlı güvenli matris çarpımı

  1. Tez No: 831461
  2. Yazar: DİLEK ÖNER
  3. Danışmanlar: PROF. DR. ERSAN AKYILDIZ, PROF. DR. MURAT CENK
  4. Tez Türü: Doktora
  5. Konular: Matematik, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2023
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Uygulamalı Matematik Enstitüsü
  11. Ana Bilim Dalı: Kriptografi Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. Kriptoparalarda kümeleme analizi uygulamaları

    Cluster analysis applications of cryptocurrencies

    EZGİ DOĞAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. NİZAMETTİN BAYYURT

  2. FPGA tabanlı şifreli kablosuz haberleşme sistemi

    FPGA based encrypted wireless communication system

    ILGAZ AZ

    Yüksek Lisans

    Türkçe

    Türkçe

    2014

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Disiplinlerarası Ana Bilim Dalı

    DOÇ. DR. GÖKHAN İNALHAN

  3. 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

    Türkçe

    1997

    Tekstil ve Tekstil Mühendisliğiİstanbul Teknik Üniversitesi

    Tekstil Mühendisliği Ana Bilim Dalı

    DOÇ. DR. EMEL ÖNDER

  4. İ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

    Türkçe

    2012

    Mekatronik Mühendisliğiİstanbul Teknik Üniversitesi

    Mekatronik Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. ZEKİ YAĞIZ BAYRAKTAROĞLU

  5. 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

    Türkçe

    2012

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektrik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MUSTAFA BAĞRIYANIK