Geri Dön

Rotation tree: Accelerating homomorphic encryption common input rotations

Döndürme ağacı: Homomorfik şifrelemede ortak girişli döndürme işlemlerinin hızlandırılması

  1. Tez No: 919387
  2. Yazar: MEHMET EYMEN ÜNAY
  3. Danışmanlar: DOÇ. DR. NİL BANU TARIM, DR. ÖĞR. ÜYESİ AYŞE YILMAZER METİN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Elektrik ve Elektronik Mühendisliği, Computer Engineering and Computer Science and Control, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2025
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Lisansüstü Eğitim Enstitüsü
  11. Ana Bilim Dalı: Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Elektronik Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 123

Özet

Tam Homomorfik Şifreleme (FHE), şifreli veriler üzerinde çalışarak gizlilik korumalı hesaplamayı mümkün kılan bir teknolojidir. FHE, kullanıcı verilerinin hassas olduğu bağlamlar ile büyük servis sağlayıcıları bir araya getirme potansiyeline sahiptir. Örneğin, medikal veya finans alanlarındaki veriler, FHE sayesinde veri sahiplerinin gizliliğini ihlal etmeden bulut sağlayıcıları tarafından işlenebilmektedir. Günümüz teknolojisinde veri depolama ve veri haberleşmesi için güvenli çözümler mevcuttur, ancak veriyi işlemek için verinin işlem yapan makineye erişilebilir hale getirilmesi ve deşifre edilmesi gerekmektedir. Veriyi deşifre etmeden işleme sorusuna çözüm arayan Tam Homomorfik Şifreleme (Fully Homomorphic Encryption), güvenli veri işlemeyi sağlamak ve gizlilik korumalı makine öğrenmesi, veri analizi ve benzeri uygulamaları mümkün kılmak için yüksek bir potansiyeli olan aktif bir araştırma alanıdır. Ancak günümüzde FHE'nin önündeki ana engel, geleneksel hesaplamadan onlarca kat daha yavaş olmasıdır. Bu çalışmanın da ana odağı FHE performansının iyileştirilmesi ve gelişimine katkıda bulunulmasıdır. FHE, kriptografiyi ve hesaplamayı, veri işleyicisinin veriye erişimi olmayacak şekilde birleştirir. Bir FHE senaryosunda veri, istemci tarafından şifrelenir; körleme bir şekilde işlemler gerçekleştiren bir sunucuya gönderilir ve sunucu da başka bir şifrelenmiş sonuç üretir. Sunucu tarafından elde edilen sonuç, çözülmek üzere istemciye geri gönderilir. Bu döngü boyunca yalnızca istemci verinin içeriğini çözebilir ve görebilirken, sunucu sadece şifrelenmiş bir girdi ile işlemler gerçekleştirip şifrelenmiş bir çıktı elde edebilir. FHE sistemi, öyle şifrelenmiş bir veriyi girdi olarak almalı ve başka bir şifrelenmiş veri çıkarmalıdır ki; bu çıktı deşifre edildiğinde girdinin işlenmiş haline eşdeğer olmalıdır. Başka bir bakış açısıyla, açık veri yerine şifreler üzerinde aynı hesaplamayı gerçekleştiren homomorfik bir yöntem aranmaktadır. FHE, aktif bir araştırma alanıdır ve şifreli veriler üzerinde hesaplama yapmanın birden fazla yolu vardır. FHE şemaları üç kategoriye ayrılabilir: Birinci kategori bitler ve ikili mantık üzerinde çalışırken, ikincisi tam sayılar üzerinde ve üçüncüsü reel sayılar üzerinde çalışır. Son kategori, toplu işleme ve hassasiyet kaybının güvenlik gürültüsü ile birleşimi sayesinde performans ve verimlilik açısından en umut verici olanıdır. Bu kategori FHE'de çoğunlukla CKKS şeması ile ilişkilendirilir. 4. nesil bir şema olan CKKS, sabit noktalı aritmetik (fixed point arithmetic) üzerinde çalışan yeni bir yaklaşık FHE şemasıdır. CKKS, karmaşık uzay üzerinde tanımlanır, kullanıcı gerçek ve sanal kısımları kullanabilir. Her işlemden sonra, diğer şemalarda olduğu gibi şifreye belirli miktarda gürültü eklenir. Ancak CKKS, sabit nokta sayısının doğruluğunu düşürerek en az anlamlı bitleri (least significant bits) gidererek gürültüyü azaltabilir. Tam sayılar veya reel sayılar üzerinde çalışan şemalar, temel bir polinom ile veri grupları (batch) halinde çalışır. Toplu işleme, bir FHE işlemi SIMD (Tek Komut Çoklu Veri) düzeninde çalıştığı için uygulamanın hızını ve verimliliğini artırır. Her bir grup yuvalar (slot) içerir, ancak sistemin altında yatan temel polinom her zaman gruplar halinde çalıştığı için yuva değerlerine doğrudan erişilemez. Bunun yerine, döndürme (rotation) işlemi sayesinde bazı yuvaları belli bir indeks miktarı kadar kaydırarak yuvaların dairesel permütasyonu elde edilebilir. Bu nedenle, veri grubu işleyen şemalar toplama, çarpma ve döndürme olmak üzere üç temel işleme sahiptir. CKKS şeması, bütün grup üzerinde çalışan basit bir çevrimsel döndürme işlemine sahiptir. Program konumuna bağlı olarak, bir döndürme işlemi program için zaman ve bellek açısından çok maliyetli olabilir. Özellikle bir program yüksek çarpımsal derinliğe ve polinom halkası güvenlik gereksinimlerini karşılamak için büyük bir boyuta sahipse, programın başındaki tek bir döndürme işlemi, uygulamadan bağımsız olarak oldukça maliyetli olabilir. Polinom hesaplama gibi diğer ağır işlemlerin SIMD yürütülmesi de tercih edildiğinden, FHE programlamada ağır işlemleri azaltmak için daha verimli toplu işleme kullanma eğilimi vardır. Ancak toplu işleme, bir değeri yuvalara yaymak için aynı şifreli metin üzerinde birden fazla döndürme kullanımını içerir. Bu, çoğu programın yüksek performans ve verimlilik elde etmek için programın ağır işlemler öncesinde ortak girişli döndürmeleri kullanma eğiliminde olduğu, ancak artan döndürmeler için bir maliyet oluşturduğu anlamına gelir. Özellikle bu toplu işleme için odaklanılan polinom hesaplama gibi ağır işlemler yüksek çarpımsal derinlik maliyetine sahipse öncesindeki döndürme işlemleri daha fazla zaman ve bellek tüketimine neden olmaktadır. Döndürme işlemlerinin bellek maliyetinin birincil kaynağı döndürme anahtarlarıdır. Her döndürme indeksi, bellekte depolanan ayrı bir döndürme anahtarı gerektirir. Gerekli indeks sayısı büyüdüğünde, döndürme anahtarları önemli bir bellek maliyetine neden olmaktadır. Bu nedenle pratikte, program tarafından gerekli olan tüm indekslerin döndürme anahtarları bellekte tutulmamaktadır. Az miktarda döndürme anahtarı bellekte tutulmakta ve bunlar programdaki hedef döndürme indekslerine ulaşmak için toplanarak birleştirilebilmektedir. En genel tanımıyla, döndürme işlemi problemi, programın gerektirdiği hedef indekslere ulaşmak için makul miktarda döndürme anahtarını az sayıda bileşke döndürmeyle bulmaya çalışır. Genel döndürme işlemi probleminin bir alt problemi olan genel ortak girişli döndürme işlemi problemi de bu çalışmada tanıtılmıştır. Ayrıştırmadan bağımsız bir şekilde sadece döndürme anahtarlarına bağlı olarak, ortak girişli hedeflerin birbiri cinsinden elde edilebildiği ve bir hedef indeksin başka bir hedef indeks için ara basamak olabileceği gösterilmiştir. En genel şekilde tarif edilmiş bu optimizasyon, çalışmanın ana konusu olan döndürme ağacı optimizasyonun da teorik altyapısını oluşturmaktadır. Hedef indekslere ulaşmak için döndürme işlemlerinin birleştirilmesi çeşitli şekillerde gerçekleştirilebilir. Bu çalışmada İkili (Binary), Bitişik-Olmayan Form (NAF), Radix NAF ve Bebek-Adımı/Dev-Adım (BSGS) ayrıştırmaları (decomposition) analiz edilmiş ve karşılaştırılmıştır. Ayrıştırmalar, döndürme anahtarlarının sayısında ve bunların ayrıştırmalarındaki eleman sayılarında belirleyici rol oynamaktadır. Literatürde önemli bir yere sahip olan BSGS, bu çalışmada ikiden fazla basamağa genelleştirilmiş ve daha az bellek tüketimi yapan varyasyonları bu çalışmada üretilmiştir. Döndürme anahtarlarının bellekte oluşturduğu yükü azaltmak için bu ayrıştırma metotları sıklıkla FHE programlarında kullanılmaktadır. Özellikle NAF ayrıştırması, sağladığı ayrıştırma performansı ve eklediği düşük bellek maliyeti bakımından FHE yazılım kütüphanelerinde tercih edilmektedir. Her bir hedef için bağımsız ayrıştırmaların elde edilmesi ve bağımsız döndürme işlemlerinin çalıştırılması Bileşke Döndürme olarak adlandırılmıştır. Ancak her ne kadar genel döndürme problemi bu şekilde çözülmekteyse de ortak girişli döndürmelere özel bir optimizasyon geliştirilmemiştir. Bu çalışma, SIMD FHE programlaması nedeniyle farklı uygulamalarda karşımıza çıkan bir döndürme işlemi sınıfının hızlandırılmasına odaklanmaktadır. Sıkça görülen ortak girişli döndürme işlemlerinde aynı şifreli veriye farklı indekslerle döndürme işlemi uygulanmaktadır. Ortak girişli döndürme işlemlerine sahip bütün FHE programlarında uygulanabilecek Döndürme Ağacı adı verilen yeni bir veri yapısı sunularak FHE programlarının performansının artırılması amaçlanmaktadır. Döndürme Ağacı, bir döndürme işleminin daha küçük indekse sahip döndürme işlemlerinin bileşkesi olarak ifade edilebilmesine ve hedeflerin elde edilmiş başka hedefler üzerinden ulaşılabilmesine dayanmaktadır. Farklı son hedefler için oluşturulmuş ayrıştırmaların ortak döndürmeleri birleştirilmekte ve ortak adımlarda yalnızca bir defa döndürme işlemi çalıştırılmaktadır. Elde edilen ortak döndürme sonuçları Döndürme Ağacı düğümlerinde saklanarak çalıştırılan toplam döndürme işlemleri azaltılmaktadır. Bileşke Döndürme yerine Döndürme Ağacı kullanmanın bir başka avantajı da, yalnızca ortak girişli döndürmeler durumunda kullanılabilen bir FHE optimizasyonunu kullanma imkanı sağlamasıdır. Ağacın ara düğümlerine de birden fazla döndürme işlemi uygulanabildiği için, bileşke döndürmenin aksine, ara aşamalarda da ortak girişli döndürmeler bulunmaktadır. Yalnızca ortak girişli döndürmelerde kullanılabilen bir FHE optimizasyonu olan amortize döndürmeler (hoisted rotation) ortak hesaplama kısımlarını birleştirmekte ve ön hesaplamayı diğer her döndürme için yeniden kullanmaktadır. Böylece toplam yürütme süresi iyileşmektedir. Döndürme ağacı ayrıca, ayrıştırma fonksiyonundan bağımsız olduğundan dolayı ağaç yapısı için dinamik bir platform sağlar. Bahsedilen ayrıştırmalar ile oluşturulmuş Döndürme Ağaçları bu çalışmada değerlendirilmiş ve yürütme süreleri, bellek kullanımları ve paralelleştirme yetenekleri sunulmuştur. Bu çalışmanın akademik literatüre sağladığı katkılar şöyle özetlenebilir: - Homomorfik Şifrelemede döndürme işlemlerinin ve ortak girişli döndürme işlemlerinin genel problemi kümeler açısından tanımlanmıştır. Genelleştirilmiş problemlerde tamamen küme teorisi ve ayrıştırma perspektifinden bir yaklaşım sunulmuştur. - Bebek-Adımı/Dev-Adım yöntemi bir sayı sistemi olarak genelleştirilmiş ve azaltılmış bellek kullanımı için ikiden fazla adıma genişletilmiştir. - Ortak girişli döndürme işlemleri için Döndürme Ağacı veri yapısı ortaya atılmış ve farklı ayrıştırma türleriyle performans analizi yapılmıştır. Döndürme Ağacı optimizasyonunun uygulamalardaki faydasının gösterimi için örnek olarak Sıralama ve Matris-Vektör çarpımı uygulamalarında Bileşke Döndürme yerine Döndürme Ağacı kullanılmış ve sırasıyla %30 ve %50'ye varan hızlandırma elde edilmiştir. Döndürme Ağacının, döndürme işlemi optimizasyonları için kritik bir platform sağlayacağına ve ortak girişli döndürmeler için gelecek araştırmaların bir parçası olacağına inanılmaktadır.

Özet (Çeviri)

Fully Homomorphic Encryption (FHE) is a privacy-preserving computation technology that enables processing of encrypted data. FHE has the potential to bridge between contexts where on the one side user data is sensitive and on the other side there are large computational service providers. For example, data in medical or financial sectors can be used with cloud providers without violating the privacy of the data owners. However, currently the main obstacle for using FHE practically is that it is orders of magnitudes slower than conventional computing. This work's main focus is on improving FHE performance and thus contributing to its development. FHE is an active research area and it provides multiple ways of achieving computation over encrypted data. The FHE schemes can be categorised into three groups. The first category works on bits and binary logic, the second works on integers and the third works on real numbers. The last category is the most promising in performance and efficiency, due to batching and the smart combination of precision loss with security noise. This category is mostly associated with CKKS scheme in FHE. Schemes working on integers or real numbers work in batches of data thanks to the underlying polynomial ring. The batched processing improve the speed and efficiency of the application since an FHE operation works in SIMD (Single Instruction Multiple Data) fashion in the FHE mathematical domain. A batch is an array of slots which cannot be accessed individually since the underlying polynomial is designed to work in batches. Instead, the slots can be rotated by performing a cyclic permutation which will allow inter-slot operations. For this reason, most batched schemes include three primitive operations as addition, multiplication and rotation. The CKKS scheme has a simple rotation operation which is applied to the complete batch. Depending on the program location, a rotation operation can be highly costly in terms of time and memory. Especially, if a program has high multiplicative depth and the polynomial ring has large dimension to satisfy the security requirements, a single rotation operation in the beginning of the program can be highly costly in time and memory, independent of the specific application. Since SIMD execution of other heavy operations such as polynomial evaluations are favoured for performance, in FHE programming there is a tendency to create efficient batching to reduce the number of heavy operations. The SIMD batching however involves multiple uses of rotations on the same ciphertext, to spread the value in the slots. This means, most programs tend to make use of common input rotations in the beginning of the program to achieve high performance and efficiency while incurring a cost for increased rotations. Common input rotations are also commonly observed in computations that have inter-slot data dependencies. Sorting and Matrix-Vector Multiplication are applications that include a high number of common input rotations and they are optimised in this work. However, the optimisation is applicable to any FHE program with the common input rotation pattern. The memory cost of rotations stems primarily from the rotation keys. Every rotation index requires a unique rotation key which is stored in memory. When the index ranges get large, the rotation keys can cause a significant memory cost. For this reason, in practice, not all indices required by the program have their rotation keys in memory. Only a small amount of rotation keys is kept which can then be composed additively to reach the target rotations in the program. In its most general definition, the rotation problem tries to find a reasonable amount of rotation keys with a small number of composed rotations to reach the target indices required by the program. The composition of rotations to reach target indices can be performed in various ways. In this work, decompositions of Binary, Non-Adjacent Form (NAF), Radix NAF and Baby-Step/Giant-Step (BSGS) are analysed and compared. The decompositions are crucial in deciding the number of rotation keys and the element numbers in their decompositions. In this work, BSGS is generalised to support more than two digits. The work presented here is based on a pattern of the rotation operations observed due to SIMD FHE programming. It aims to increase the performance of every FHE program with the common input rotation pattern by presenting a novel data structure for FHE called the Rotation Tree. The tree structure is based on the idea that a rotation can be expressed as a composition of smaller rotations. Rotations with same indices are combined for targets and stored in nodes of the tree to enable reuse and reduce the total rotation operations executed. Another advantage of utilising a tree is the ability to use a more efficient version of rotation called the hoisted rotation. Hoisted rotation is an FHE optimisation which can be used only in the cases of common input rotations. It combines the common parts of computation for the same cipher and reuses the precomputation for every other rotation which improves the execution time. The rotation tree provides a dynamic platform for its structure since it is decomposition agnostic. Rotation Trees with the mentioned decompositions have been evaluated and their execution times, memory utilisations and parallelisation capabilities are presented in this work. This work makes several novel contributions to the literature: - The general problem of rotations and common input rotations are defined in terms of sets. We have provided several ways of approaching them purely from the set and decomposition perspective. - The State-of-the-Art Baby-Step/Giant-Step method is generalised as a number system and is extended into steps of more than two to reduce memory usage at the cost of slower speed. - Rotation Tree data structure is introduced for the common input rotations and evaluated with different types of decompositions as a code optimisation. The Rotation Tree optimisation was used in practice and significant speed-ups were obtained. It is believed that the rotation tree will provide a critical platform for rotation optimisations and will drive further advances in common input rotation optimisations.

Benzer Tezler

  1. Tez No

    840875

    A comparative study of machine learning classification alorithms on acceleration data

    Hızlanma verileri üzerinde makine eğitimi sınıflandırma aloritmalarının karşılaştırmalı bir çalışması

    MUHAMMAD AHMED MAJEED

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÜsküdar Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    Assist. Prof. Dr. NURİ BİNGÖL

    DR. ÖĞR. ÜYESİ FAYYAZ AHMAD

  2. Tez No

    22035

    ADIM: Üç boyutlu canlandırma sistemi

    ADIM: A 3D animation system

    A.GÖKHAN ERKMAN

    Yüksek Lisans

    Türkçe

    Türkçe

    1992

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    DOÇ. DR. FÜSUN TUNALI

  3. Tez No

    268599

    Tekirdağ ilinde yeni tesis meyve bahçelerinde görülen abiyotik hastalıklar ve mücadele önlemleri üzerine araştırmalar

    Abiotic fruit tree diseases and their control on newly established orchars in Tekirdag province

    ŞERİFE YAVAŞ GÖREN

    Yüksek Lisans

    Türkçe

    Türkçe

    2009

    ZiraatNamık Kemal Üniversitesi

    Bitki Koruma Ana Bilim Dalı

    PROF. DR. AHMET ÇITIR

  4. Tez No

    689722

    İzmit-Kerpe yöresindeki sahil çamı ağaçlandırmalarının topraktaki karbon ve besin maddesi stoklarına etkisi

    Effect of maritime pine plantations on soil carbon and nutrient stocks Izmit-Kerpe district

    SELİN ÖZBAY

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    Ormancılık ve Orman Mühendisliğiİstanbul Üniversitesi-Cerrahpaşa

    Orman Mühendisliği Ana Bilim Dalı

    PROF. DR. DOĞANAY TOLUNAY

  5. Tez No

    856072

    Türkiye'de orman yangınlarının güneş lekeleri ile olası ilişkisinin araştırılması

    Investigation of possible relation of forest fires with sunspots in Türkiye

    NEZİHA ANĞINOĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    2024

    Ormancılık ve Orman MühendisliğiSakarya Üniversitesi

    Afet Yönetimi Ana Bilim Dalı

    PROF. DR. MURAT UTKUCU

Geri Dön