Sorting problem in fully homomorphic encrypted data
Tam homomorfik şifrelenmiş veriler üzerinde sıralama problemi
- Tez No: 392233
- Danışmanlar: DOÇ. DR. ERKAY SAVAŞ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Tam Homomorfik Şifreleme (THS) programları, kullanıcıların şifrelenmiş veri üzerinde her türlü işlemi yapmasına olanak verir. Bu, şifrelenmiş veri bitleri üzerinde uygulanan çarpma ve toplama, bir diğer deyişle mantıksal VE veya ÖZELVEYA işlemleri sayesinde mümkün olur. Her türlü mantıksal devre sadece ÖZELVEYA ve VE mantıksal işlemlerini gerçekleştiren mantıksal kapılar kullanılarak oluşturulabildiği için, bu iki temel THS işlemi, şifreli metinler üzerinde daha karmaşık operasyonların da hesaplanabilmesini sağlar. Bulut bilişim kullanıcıları çoğunlukla bulut sunucularına güvenmemeye meyilli olduklarından, güvenlikleri gereği, bilgilerini şifreleyerek saklama yoluna giderler. Dolayısıyla şifreli veriler üzerinde işlem yapabilmeyi olanaklı kılan homomorfik şifreleme sistemleri, özellikle bulut bilişim uygulamalarında yaygın kullanım alanı bulacaktır. THS sayesinde, bulut sunucuları artık istenilen herhangi bir işlemi, kullanıcının gizli şifresini veya açık veriyi görmeden, THS yapıtaşlarını kullanarak gerçekleyebilir. Bu tez kapsamında, bir sunucunun uygulamak isteyebileceği bu tür işlemlerden biri olan sıralama problemine odaklanılmıştır. Bu amaçla, tam homomorfik şifreleme sistemi ile şifrelenmiş¸ veriyi verimli bir şekilde sıralamaya yarayacak iki yeni sıralama algoritması sunulmuştur. Bu algoritmalar karşılaştırma sayısı gibi geleneksel ölçütlerin yanısıra, oluşacak sıralama devresinin derinliğinin en aza indirgenmesine odaklanarak tasarlanmışlardır. Derinliğin azaltılması, operasyonlar sırasında şifrelenmis¸ veri bitlerinde oluşan ve şifre çözümünü olanaksız kılan gürültünün daha yavaş bir şekilde artmasını, dolayısıyla daha küçük güvenlik parametreleriyle çalışılabilmesini sağlamış ve bu da verimin artmasını mümkün kılmıştır. Önerilen sıralama algoritmaları, NTRU temelli THS sistemi icin geliştirilmiş bir yazılım kütüphanesi kullanılarak gerçeklenmiş ve klasik sıralama algoritmalarına göre çok daha iyi sonuçlar verdiği gösterilmiştir.
Özet (Çeviri)
Fully Homomorphic Encryption (FHE) schemes allow users to perform computations over encrypted data without decrypting the ciphertext. This is possible via two operations which are bitwise addition and multiplication, namely logical XOR and logical AND operations, which can be applied over the bits individually encrypted under the fully homomorphic encryption scheme. Since any Boolean circuit can be realized using only AND and XOR gates, they can be used to build circuits for the computation of even more complicated operations over encrypted data. This property of FHE cryptosystems is especially useful in cloud computing applications, since data owners who use cloud computing for storage and computation, usually tend not to trust servers and for security reasons, they prefer storing their data in encrypted form. By using FHE cryptographic primitives, now servers are allowed to perform any desired task over the encrypted user data without the knowledge of secret key or plaintext. In this thesis, we focus on solving one such task that cloud server performs over encrypted data; sorting the elements of an integer array. We introduce two sorting schemes, both of which are capable of efficiently sorting data in fully homomorphic encrypted form. The technique is obtained by focusing on the minimization of the depth of the sorting circuit in addition to more traditional metrics such as the number of comparisons. The reduced depth of the sorting network allows a slower growth in the noise of encrypted bits and thereby makes it possible to select smaller parameter sizes for the underlying homomorphic encryption scheme resulting in much faster computation of homomorphic sorting. We present a leveled/batched implementation for the proposed sorting algorithms, using an NTRU based homomorphic encryption library, which yields significant improvements over classical sorting algorithms.
Benzer Tezler
- 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ı
MEHMET EYMEN ÜNAY
Yüksek Lisans
İngilizce
2025
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ. DR. NİL BANU TARIM
DR. ÖĞR. ÜYESİ AYŞE YILMAZER METİN
- Konut bölgelerinde parsel düzeni uygulamasının kent topraklarının rasyonel kullanımı çerçevesinde mimari açıdan değerlendirilmesi
An Architeet's Criticism of the Currently Practised method of plot formation in residential areas from the point of View of rational utilization of urban deatories
SUZAN ESİRGEN
Yüksek Lisans
Türkçe
1986
Şehircilik ve Bölge PlanlamaGazi ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
DOÇ. DR. UMUR ERKMAN
- Sıralama yöntemleri ve ikili ağaç sistemi üzerine bir araştırma
Başlık çevirisi yok
ALİ TANSEL DEMİR
Yüksek Lisans
Türkçe
1986
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Bilimleri Ana Bilim Dalı
DOÇ. DR. ŞABAN EREN
- Demiryolu yük taşımacılığında optimum katar yükü probleminin incelenmesi
Determination of the optimum train load in railway freight transportation
SADETTİN ÖZEN
- Sorption/desorption studies of cesium and neptunium on some days and soils
Başlık çevirisi yok
E.ŞEBNEM AKSOYOĞLU