Geri Dön

Privacy preserving representation of high-entropy data using non-uniquely decodable code

Yüksek entropili veriıleriın tekiıl çözümlenemeyen kodlarla mahremiıyet korunumlu gösteriımiı

PDF İndir

  1. Tez No: 647490
  2. Yazar: YASİN ÖZTÜRK
  3. Danışmanlar: PROF. DR. MUHAMMED OĞUZHAN KÜLEKCİ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2020
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Bilişim Enstitüsü
  11. Ana Bilim Dalı: Bilişim Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Bilimleri Bilim Dalı
  13. Sayfa Sayısı: 95

Özet

Son zamanlarda teknolojide yapılan gelişmeler gittikçe hızlanmakta, bu ilerlemeler elektronik cihazların hem günlük hem de iş hayatında daha fazla yer kaplamasını sağlamaktadır. Kullanılan cihazların ve işlemci güçlerinin artmasıyla gittikçe daha fazla veri üretilmektedir. Üretilen verinin kaynağı ne olursa olsun, ister çekilen bir fotoğraf isterse bir sensörden alınan değerler kümesi, depolanması gerekmektedir. Veri boyutu çok büyük olmaya başlarsa, tek bir depolama aygıtında tüm verilerin depolanması mümkün olmamaya başlar. Eğer ki üretilen veri önemli ve hassas içerik barındırıyorsa, gizliliği korunacak bir şekilde saklanması gerekmektedir. Gizliliği korumak için bir çok farklı şifreleme algoritması ve metodolojisi olmasına rağmen, bu yöntemlerin çoğu önek içermeyen (prefix-free) veya sabit uzunluklu (fixed-length) kodlama teknikleri ile gerçekleştirilmektedir. Bunun yanında ortaya çıkardıkları şifrelenmiş son ürün tek bir dosyadan oluşmaktadır ve tek bir lokasyonda depolanması gerekmektedir. Bu çalışmada, çok geniş araştırmaların yapılmadığı bir yöntem araştırılmış olup, önek içeren (non-prefix-free) kodlama yöntemi kullanılmış ve önek içeren kodların doğasından gelen mahremiyeti koruma özelliğine sahip bir yöntem önerilmiştir. Önerilen yöntem sonucunda ortaya çıkartılan veri iki farklı bölümden oluşmaktadır ve bu özellik, gizliliği muhafaza edilen verinin paylaştırılmış depolama alanlarında saklanabilmesini olanak tanımaktadır. Bu çalışma daha çok sıkıştırılmış dosyalar, kodlanmış video dosyaları ve benzer multimedya dosyaları gibi büyük boyutlu ve yüksek entropi içeren dosyalar üzerine odaklanmıştır. Önek içermeyen kodlar, kod kelimerinin uzunluklarını bilmeye ihtiyaç duymadan benzersiz bir şekilde çözümlenebilir. Bu kodların bu özelliği sahip olmasının nedeni, bir kod kelimesinin başka bir kod kelimesinin öneki olamamasından kaynaklanmaktadır. Önek içeren kodlarda bu benzersiz çözümlenebilme özelliği bulunmaz, bu nedenle kod kelimelerinin uzunluklarının daha önceden bilinmesi gerekmektedir. Bu nedenle bu kodlar belirsiz kodlar olarakta adlandırılmaktadır. Önek içeren kodlar ile oluşturulmuş bir veri akışının kelime sınırlarını bilmeden eşsiz bir şekilde çözülmesi mümkün değildir. Bu eşsiz çözümlenememe özelliği nedeniyle bu alanda fazla araştırma gerçekleştirilmemiştir. Önek içeren kod düzenlerinde eşsiz çözümlenebilme sorununu gidermek için kod sınırlarını efektif bir şekilde betimleyecek bir yöntem bulunmalıdır. Bu alanda daha önceden sıra ve seçim (rank and select) işlemleri için ek bir sıkıştırılmış bit dizisinin tutulması, wavelet ağaçlarının oluşturulması gibi çalışmalar gerçekleştirilmiştir. Bu alanlarda yapılan deneysel çalışmalar önek içeren kodların Huffman kodlarına yakın hatta bazen daha da iyi sonuç veren sıkıştırmalar sağlayabileceğini göstermiştir. Belirsiz kodların benzersiz çözümlenebilme problemlerini gidermeye yönelik harcanan eforlara rağmen, bu çalışmada önek içeren kodların sağlamış olduğu güvenlik ve gizlilik konuları üzerine odaklanılmıştır. Yüksek hacimli verilerin güvenliği sağlanırken daha az şifreleme işlemi gerçekleştirerek güvenliği sağlamak, şifreleme işlem maliyetinin belli bir ölçüme göre yüksek olduğu platformlarda mantıklı olmaktadır. Örneğin taşınabilir cihazlar, sensör ağları veya insansız hava araçları gibi pil ömrü limiti platformlarda az şifreleme işleminde bulunmak batarya ömrünün uzamasını sağlayabilmektedir. Bu çalışma bir kaynak verisinin daha az şifrelemeye ihtiyaç duymasına olanak tanıyan alternatif bir yaklaşımı tanımlamaktadır. Sunulan tekniğin ana fikri $n$ bit uzunluğundaki bağımsız ve özdeşçe dağıtılmış girdi bit dizisini, önceden belirlenmiş genellikle 6 ve 20 arasında değer alan $d$ bit uzunluğundaki bloklara bölüp işlemektir. Önek olmayan $2^d$ kod kelimeleri $[1\ldots 2^d]$ sayılarının permütasyonu ile oluşturulur, ve daha sonra girdideki her bir $d$ bit uzunluğundaki sembol kendisine karşılık gelen 1 ve d bit uzunluğu arasındaki NPF kod kelimesi ile değiştirilir. Permütasyon oluşturup, $2^d$ olası girdi kümesinin çıktı kümesine haritalanması, beraberinde ayrı bir güvenliği daha getirmektedir. Girdi ile çıktı arasında yapılan haritalanmanın bilinememesi durumunda, kod kelimeleri sınırlarının bilinmesi durumunda dahi, orjinal veriye geri dönüş işlemi kolay olmayacaktır. Yapılan permütasyon ile aynı girdi, $2^d!$ farklı çıktı ile sonuçlanabilmektedir. Üretilen bit akışı asıl içeriği barındırdığından \textit{faydalı yük} olarak adlandırılmıştır. Bu sekans, NPF kodların kendine has belirsizliği nedeniyle kod kelimelerinin sınırları bilinmeden eşsiz bir şekilde deşfirlenemez. Bu nedenle, kod kelimelerinin sınırlarını tutmak üzere efektif bir gösterime ihtiyaç duyulmaktadır. Bu çalışma boyunca ortaya çıkan ikinci bit akışı \textit{belirginleştirme bilgisi} olarak anılmıştır. Önerilen kod dizgisinde, faydalı yük ve belirginleştirme bilgisi tarafından kullanılan toplam alan her orijinal bit başına $2(d-1)/d\cdot 2^d \approx \frac{1}{2^{d-1}}$ miktarınca fazla yük oluşturmaktadır. Bu fazla yük $d$ sayısı yükseldikçe ihmal edilebilecek düzeye düşmektedir, örneğin $d=8$ olduğunda her bin bit başına 7 bitten az fazla yük oluşmaktadır. Ortaya çıkan son gösterim üzerinden faydalı yükün $\approx \frac{(d-2)}{d}$ ve belirginleştirme bilgisinin $\approx \frac{2}{d}$ oranınca yer kapladığı ispatlanmıştır. Toplamda iki bölümün toplamının neredeyse girdi verisiyle aynı miktarda yer kapladığı gösterilmiştir. Yer kaplama analizini takriben, belirginleştirme bilgisinden payload hakkında ne kadar bilgi edilebileceği ve tam tersi durum incelenmiştir. İnceleme sonucunda bir elementin şifrelenmesinin ve diğer parçanın olduğu gibi bırakılmasının, verinin gizliliği konusunda bir açıklık oluşturmayacağı gözlemlenmiştir. Belirginleştirme bilgisi daha az yer kapladığından dolayı, bu bölümün şifrelenip faydalı yükün olduğu gibi bırakılması daha ideal olmaktadır. Fakat aynı zamanda faydalı yükün şifrelenip, belirginleştirme bilgisinin olduğu gibi bırakılması da, toplamda şifrelenmesi gereken veri miktarını azaltmaktadır. Unutulmamalıdırki yapılan çalışma, girdi bit akışının bağımsız ve özdeşçe dağıtılmış olduğunu var saymaktadır ve ilk bakışta bu durumun kısıtlayıcı olduğu düşünülebilir. Ancak bahsedilen methodun hedeflediği veri tipleri; mpeg4 formatında video dosyaları, mp3 formatındaki ses dosyaları ve benzer formatlar gibi önceden entropi kodlanmış dosyalar olabilmektedir. Herhangi bir kayıpsız veri sıkıştırma yöntemi, her bir sembol Shannon'un teoremine göre sembolün entropisine olabildiğince yakın sayıda bit ile ifade edilmesi durumunda, entropi kodlanmış olarak ifade edilmektedir. Bu tarz sıkıştırma işleminden geçirilip entropisine kadar küçültülebilen dosyalar önerilen yöntem için ideal girdiyi sağlamaktadır. Bu gözlem, farklı tipteki sıkıştırılmış veri tipleri üzerinde yapılan deney sonuçlarının tekdüze, bağımsız ve özdeşçe dağıtılmış olarak kabul edilen verinin teorik limitine çok yakın sonuç vermesiyle desteklenmiştir. Bu sebepten ötürü, teklif edilen kodlama yöntemi sıkıştırılmış verilerin gizliliğini korumak için de kullanılabilecek bir yöntem olarak göze çarpmaktadır.

Özet (Çeviri)

Technological advancements made in the last decades are getting increasingly faster. These progressions allow electronic devices to involve in people's daily lives more and more, whether it is personal or business. More data is generated progressively with the increase of used equipment and processing power. Whatever the source of the generated data, which can be a photograph taken or a signal generated from a sensor, needs to be stored. When the data gets too large, it starts to become infeasible to store in a single device. If the generated data is sensitive, it needs to be stored in a way that preserves privacy as well. Although there are several algorithms and methods to encrypt data, most of these take advantage of prefix-free or fixed-length coding techniques. In this study, a path that has not been explored widely is researched, and a coding scheme that uses non-prefix-free (NPF) coding is proposed to preserve privacy. This study mainly focuses on massive high entropy data, such as compressed files, encoded video or similar multimedia files. Prefix-free codes can be determined uniquely without prior knowledge of the keyword length. The reason these codes have this property is, a codeword cannot be a prefix of another codeword. Non-prefix-free codes lack this unique decodability, and therefore their codeword lengths must be known beforehand. A stream of non-prefix-free codes cannot be decoded without knowing the keyword boundaries of each codeword. Due to the non-unique decodability feature, not much research has been performed on this field. The proposed coding scheme in this study suggests splitting giving data into two elements, one of them being the payload and the other one being the disambiguation information. The payload is a file that stores NPF code-words of given data according to the proposed NPF coding scheme. Disambiguation information stores the keyword boundaries of each code-words stored in the payload. Disambiguation information must be uniquely decodable for NPF decoder to read the codeword boundaries. Finding an efficient way of representing this information is essential in NPF coding schemes. After codeword boundaries are read from the disambiguation information, the payload can be uniquely decodable. Investigated research avenue led to storing massive high-entropy data in a distributed fashion while preserving privacy. Instead of traditional ways of approaching security by encrypting the whole data, with the proposed approach of encrypting only a small portion of the data, mainly the disambiguation information, decreases the time and operational power taken to secure massive loads. Even though if disambiguation information is not encrypted and stored in different storage than the payload, the security of the data is still achieved.

Benzer Tezler

  1. Tez No

    220664

    Privacy protecting biometric authentication systems

    Kişisel gizliliği sağlayan biyometrik doğrulama sistemleri

    ALİSHER KHOLMATOV

    Doktora

    İngilizce

    İngilizce

    2008

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı Üniversitesi

    Bilgisayar Mühendisliği Bölümü

    DOÇ. DR. BERRİN YANIKOĞLU

  2. Tez No

    774189

    Answering spatial density queries under local differential privacy

    Konumsal yoğunluk sorgularının lokal diferansiyel mahremiyet korumalı cevaplanması

    EKİN TİRE

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ MEHMET EMRE GÜRSOY

  3. Tez No

    558562

    Practical and fully secure multi keyword ranked search over encrypted data with lightweight client

    Şifrelenmiş veri üzerinde tümüyle güvenli, uygulanabilir, derecelendirilmiş ve çoklu anahtar kelime destekleyen arama methodu

    TOLUN TOSUN

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    PROF. DR. ERKAY SAVAŞ

  4. Tez No

    898239

    Training and modelling with privacy in network data using machine learning

    Makine öğrenimini kullanarak ağ verilerinde gizlilikle eğitim ve modelleme

    ONAT CAN BABA

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    Elektrik ve Elektronik MühendisliğiMarmara Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ENGİN MAŞAZADE

  5. Tez No

    875268

    Rastgele bozma yaklaşımlarının öneri algoritmalarının popülerlik yanlılığına etkisinin incelenmesi ve sahte oy enjeksiyonuna dayalı yenilikçi çözümler geliştirilmesi

    Analyzing effects of random perturbation approaches on the popularity bias issue of recommendation algorithms and developing novel fake rating injection-based solutions

    MERT GÜLSOY

    Doktora

    İngilizce

    İngilizce

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAkdeniz Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ALPER BİLGE

    DOÇ. DR. EMRE YALÇIN

Geri Dön