Bir süre önce Stanford'da CS355 (İleri Kriptografi) dersini aldım. Dan'in üç doktora öğrencisi Dima Kogan, Florian Tramer ve Saba Eskandarian'dan eğitim aldık. Üç doktora öğretim üyesinin her birinin kendine has özellikleri vardır ve araştırma yönleri de oldukça farklıdır. Dima gizlilik koruma teknolojisi PIR'e (Özel Bilgi Retri), Florian makine öğrenimi ve blockchain araştırmasına, Saba ise sıfır bilgi kanıtına odaklanıyor.
CS355 kursu, antik çağlardan günümüze kriptografi alanındaki hemen hemen tüm içeriği kapsamaktadır. En eski tek yönlü fonksiyondan (Tek Yönlü Fonksiyon), eliptik denklemlere (ECC) ve Eşleştirmeye ve son olarak daha popüler MPC, sıfır bilgi, özel bilgi alımı (PIR), tamamen homomorfik algoritmalara vb. kadar. Son yıllarda. Ders iki gün önce bittiğinden beri, bilgi içeriği henüz sığ hafızamdayken bir dizi not düzenledim. Kursun içeriği çok ilgi çekici, geri kalan içeriği daha sonra vakit buldukça sizlerle paylaşacağım~
Bu sayımızda son dönemde popüler olan Tam Homomorfik Şifreleme (FHE) ve buna eşlik eden Kafes Tabanlı Şifreleme teknolojisinden bahsedeceğiz.
Tamamen homomorfik şifreleme nedir?
Pek çok arkadaşın Tam Homomorfik Şifreleme (FHE) adını duyduğunu düşünüyorum. Son yıllarda, kişisel gizliliğin korunmasına ilişkin giderek daha fazla konu ortaya çıktı ve homomorfik şifrelemeyi de içeren bir dizi kriptografi uygulama teknolojisi de geniş çapta popüler hale geldi.
Bu konunun daha iyi anlaşılabilmesi için tam homomorfik şifrelemenin tanımına kısaca değinmek istiyorum.
Şifreleme sistemi incelemesi
Başlamadan önce en geleneksel şifreleme sistemini inceleyelim.
Hepimiz bir şifreleme sistemi oluşturmak istiyorsanız genellikle bir anahtara ihtiyacınız olduğunu biliyoruz. Bu anahtar aracılığıyla, bir uçta düz metin bilgisini şifreli metne dönüştürebilir ve diğer uçta şifreli metni orijinal görünümüne döndürmek için anahtarı kullanabiliriz. Bu Anahtar olmadan başkalarının hangi bilgileri aktardığımızı bilmesi zor olurdu.
Yukarıdaki çizim temel olarak tüm yaygın şifreleme sistemlerinin genel resmini göstermektedir. Daha resmi bir açıklama yöntemi kullanırsak, tüm şifreleme sistemleri şüphesiz üç şey yapar:
Şifreleme algoritmaları hakkında bir şeyler bilen arkadaşlar, yaygın olanları kesinlikle bilecektir. AES, RSA vb. gibi şifreleme algoritmaları. Ayrıca herkesin genel olarak şifreleme sistemlerinin iki türe ayrıldığını bilmesi gerekir: simetrik şifreleme sistemleri ve asimetrik şifreleme sistemleri. Burada anlattığımız üç adım aslında her şifreleme sistemine uygulanabilir. Simetrikse, şifreleme ve şifre çözme için kullanılan anahtar aynıdır. Asimetrik bir sistem ise şifreleme için genel anahtar, şifre çözme için farklı bir özel anahtar kullanılır.
Kriptografi araştırmalarında yeni bir sistemin tanımını gördüğümüzde çoğu zaman sistemin sahip olması gereken özellikleri belirtmek zorunda kalırız.
Anlamsal güvenliğin temel önemi, izleyicinin iki şifrelenmiş mesajı birbirinden ayıramamasıdır. Yani eğer bir davetsiz misafir ağı gizlice dinler ve gönderdiğim şifreli bilgiyi görürse, kullandığım şifreleme sistemi anlamsal olarak güvenli olduğu sürece, davetsiz misafirin şifreli metinden şifrelenmiş içerik hakkında herhangi bir bilgi alamayacağından emin olabilirim.
Yukarıdaki iki özelliğin sağlanmasından sonra şifreleme sistemi sağlam hale gelir.
### Homomorfik Şifreleme: Kazara Özel Özellikler
Şifreleme sisteminin ne olduğunu anladıktan sonra, rastgele oluşturulmuş bozuk koda benzeyen bu şifreli metne dikkat edebiliriz. Sadece şifreli metnin kendisine bakarak herhangi bir bilgi elde edemeyeceğimizi hepimiz biliyoruz. Peki bu, anahtar yoksa ve yalnızca şifreli metin varsa hiçbir şey yapamayacağımız anlamına mı geliyor?
Cevabı hepimiz biliyoruz: pek değil.
Bu özellik için buna toplamsal homomorfizm diyoruz. Bu, şifrelenmiş şifreli metnin önceki orijinal metinle ince bir cebirsel ilişkiyi koruduğu anlamına gelir. Şifreli metni toplarsak orijinal metni toplayarak şifrelenmiş yeni şifreli metni elde edebiliriz. Aynı şekilde eklemeli homomorfik şifreleme algoritmalarının da var olduğu sonucuna varılabilir. Çarpımsal homomorfik bir algoritma tarafından oluşturulan şifreli metni çarpabilir ve ardından orijinal metinlerin çarpılması sonucuna karşılık gelen şifreli metni elde edebiliriz. Tüm süreçte anahtarla ilgili herhangi bir bilgi bilmemize gerek yok, sadece rastgele bozuk kod gibi görünen şifreli metni birleştiriyoruz.
Örneğin: Anonim oylama sistemi
Şimdi homomorfik şifrelemenin pratikliğini canlı bir şekilde açıklamak için bir örnek verelim.
Çevrimiçi oylamanın nasıl bir şey olduğunu hepimiz biliyoruz; eğer bir şirketin patronu bir oylama dalgası başlatmak istiyorsa, şirketin 996 sistemini benimseyip benimsemeyeceğini seçin. Daha sonra patron BT'den bir sunucu kurmasını isteyebilir ve çalışanların seçimlerini göndermelerine izin verebilir: istemedikleri anlamına gelen 0 oyu ve istedikleri anlamına gelen 1 oyu. Son oylama döneminden sonra patron tüm oyları toplayabilir. Tüm oyların nihai toplamı çalışan sayısının yarısını aşarsa şirket 996 ile başlayacak.
Bu oylama mekanizması çok basit görünüyor, ancak büyük bir gizlilik sorunu var: Eğer patron tüm çalışanların 996 olmasını istiyorsa ve bu oylamayı yalnızca hangi çalışanın fazla mesai yapmak istemediğini görmek için kolluk kuvvetleri bulmak amacıyla kasıtlı olarak başlatıyorsa, o zaman patron Küçük kardeşini interneti gizlice dinlemesi, her çalışanın sunduğu tercihleri kaydetmesi ve sonunda kimin 0 oy verdiğini görmesi için görevlendirdi. Bunun sonucunda çalışanlar çok korkuyor ve duygularını ifade etmeye cesaret edemiyor.
Eğer eklemeli homomorfik şifreleme algoritması kullanabilirsek bu sorun kolayca çözülebilir.
Elbette bu sistem hala çok eksik. Örneğin, BT departmanı doğrudan patronun herkesin oylarının şifresini çözmesine ve bunları bir belgeye kaydetmesine yardımcı olabilir. Bu sorunu çözmemize yardımcı olabilecek başka şifreleme araçları da var. Yer sıkıntısı nedeniyle burada daha fazla açıklama yapılmayacaktır.
Ancak bu noktada homomorfik şifreleme algoritmasının gücünü hissedebilmemiz gerekiyor. Bunu şu şekilde anlayabiliriz: Homomorfik şifreleme algoritması aracılığıyla kullanıcılar, güvenilmeyen bir uzak sunucu (bulut) ile bir tür güvenli proxy hesaplaması (Güvenli Yetkilendirilmiş Hesaplama) gerçekleştirebilirler. Kullanıcılar homomorfik şifreleme teknolojisini kullanarak hassas özel girişlerini şifreleyebilir ve buluta emanet edebilirler.Daha sonra bulut, şifrelenmiş veriler üzerinde belirli bir düzeyde hesaplama gerçekleştirebilir ve son olarak kullanıcının istediği şifrelenmiş sonucu elde edip buluta geri gönderebilir. bulut.kullanıcı. Son olarak kullanıcı sonucu açmak için şifre çözme anahtarını kullanabilir. Anlaşmanın tamamı boyunca, yetki verilen taraf (bulut), özel girdilerle ilgili hiçbir yararlı bilgiyi asla göremez.
En temel iki homomorfik özelliği kabaca anladıktan sonra diğer kavramların anlaşılması da çok kolay hale gelir. Sistematik bir perspektiften bakıldığında, homomorfik şifreleme sistemleri kabaca dört kategoriye ayrılır: kısmi homomorfizm, yaklaşık homomorfizm, sonlu seri tam homomorfizm ve tam homomorfizm.
Şimdi sırasıyla her kategorinin spesifik tanımlarına göz atalım.
Kısmen Homomorfik Şifreleme
Homomorfik şifrelemenin en temel aşaması, şifreli metnin yalnızca bir homomorfik özelliğe sahip olması olarak tanımlanan, kısmen homomorfik şifreleme olarak adlandırılır. Bu aşama, yukarıda tanımladığımız iki toplamsal homomorfizm ve çarpımsal homomorfizm modunu içerir.
Bu iki mesajın çarpımına karşılık gelen şifreli metni elde ediyoruz! Bu, çarpımsal homomorfizm özelliğidir.Bu şifreli metinlerin üzerine yeni şifreli metinleri yerleştirmeye devam edebiliriz, böylece şifreli metinler arasında herhangi bir çarpım elde edebiliriz.
Yaklaşık Homomorfik Şifreleme (Biraz Homomorfik Şifreleme)
Önceki paragrafta da söylediğimiz gibi, eğer özel girişleri çoğaltıp aralarında doğrusal bir kombinasyon elde etmek istiyorsak, basit bir kısmen homomorfik şifreleme algoritması (RSA, ElGamal) tamamlanamaz. O halde bir sonraki aşamaya geçmemiz gerekiyor.
Kısmen homomorfik şifrelemenin bir sonraki aşaması yaklaşık olarak homomorfik şifrelemedir ve bu, elde etmek istediğimiz tamamen homomorfik şifrelemeye bir adım daha yakındır. Yaklaşık olarak homomorfik bir şifreleme algoritmamız varsa, şifreli metin üzerinde toplama ve çarpma işlemlerini aynı anda hesaplayabiliriz. Ancak şunu belirtmek gerekir ki bu aşama yaklaşık olarak homomorfik (Biraz Homomorfik) olduğundan yapılabilecek toplama ve çarpma sayısı oldukça sınırlıdır, hesaplanabilen F fonksiyonu da sınırlı bir aralıktadır.
Yaklaşık olarak homomorfik şifrelemenin bu aşamada pek yaygın örneği yoktur, en iyi anlaşılan örneği dersek eşleştirmeye dayalı döngüsel grup şifreleme algoritması olsa gerek.
Yukarıda sıradan döngüsel gruplara dayanan ElGamal şifreleme algoritmasını kısaca tartıştık. Hepimiz bu algoritmanın eklemeli olarak homomorfik olduğunu biliyoruz, bu da rastgele şifreli metinler arasında doğrusal kombinasyonlar elde edebileceği anlamına geliyor. Aslında bazı özel döngüsel gruplarda bazı zayıf çarpımsal homomorfizm özelliklerini de bulabiliriz.
Bu sınırlama sistemin yaklaşık olarak homomorfik olduğunu kanıtlar çünkü keyfi mantık ve derinlik F fonksiyonunu hesaplayamıyoruz.
Tam Seviyeli Homomorfik Şifreleme
Bir sonraki aşamaya ulaştıktan sonra tam homomorfizm hedefine bir adım daha yaklaşıyoruz.
Bu aşamaya sonlu seri tam homomorfik şifreleme adı verilir. Bu aşamada zaten şifreli metin üzerinde herhangi bir sayı sınırlaması olmaksızın herhangi bir toplama ve çarpma kombinasyonunu gerçekleştirebiliyoruz.
Tam Homomorfik Şifreleme (FHE)
Pek çok çağrının ardından nihayet görmeyi beklediğimiz tam homomorfik şifrelemeye (FHE) geliniyor.
Adından da anlaşılacağı gibi, tamamen homomorfik bir şifreleme sisteminin hesaplama yöntemleri üzerinde hiçbir kısıtlaması yoktur.Şifreli metinleri, anahtar olmadan yeni şifreli metinler oluşturmak için keyfi olarak birleştirebiliriz ve yeni şifreli metin Metni, hesaplama karmaşıklığına bakılmaksızın, orijinal metne mükemmel bir şekilde geri yüklenebilir.
Bu aşamaya geldiğimizde daha önce bahsettiğimiz güvenli ajan hesaplaması mümkün hale gelir. Daha verimli, tamamen homomorfik bir şifreleme sistemi bulabilirsek, herhangi bir veri sızıntısı olmadan tüm yerel hesaplamaları güvenli bir şekilde buluta aktarabiliriz!
Tamamen homomorfik şifreleme sisteminin tanımı
Aşağıda tamamen homomorfik sistemlerin tarihinin tartışılmasına başlamadan önce, tamamen homomorfik sistemlerin resmi tanımını sistematik olarak tanımlayabiliriz. Tamamen homomorfik bir şifreleme sisteminin toplam dört algoritması vardır:
## Tamamen homomorfik şifrelemenin tarihsel incelemesi
Tam homomorfik şifreleme algoritmasının nasıl uygulandığını öğrenmeye başlamadan önce, tam homomorfik şifreleme kavramının nasıl ortaya çıktığına bir göz atsak iyi olur.
FHE (tamamen homomorfik) kavramı aslında 1970'lerin sonlarında önerildi. 1978 yılında, kriptografinin birçok büyük ismi olan Rivest, Adleman ve Dertouzos, ilk kez Veri Bankaları ve Gizlilik Homomorfizmleri Üzerine makalelerinde, şifreli metin üzerinde belirli hesaplamaları gerçekleştirebilen ve dolaylı olarak orijinal metin üzerinde çalışabilen bir sistem fikrinden bahsetmişlerdir. Daha sonra bu fikir yeniden özetlendi ve tamamen homomorfik şifreleme olarak adlandırıldı.
Tamamen homomorfik şifreleme kavramının uzun süredir önerildiği görülmektedir. Şaşırtıcı bir şekilde, 1976'da, yani makalenin yayınlanmasından iki yıl önce, Diffle-Hellman anahtar değişim protokolü henüz teklif edilmişti! Bu da kriptografi uzmanlarının hayal gücünün hala çok zengin olduğunu gösteriyor.
FHE kavramı önerildiğinde, tüm akademik topluluk bundan etkilendi ve tamamen homomorfik özelliklere sahip mükemmel bir algoritma bulmaya çalışarak onlarca yıl süren bir araştırmaya başladı. Ancak son birkaç on yılda insanlar akla gelebilecek tüm seçenekleri denediler, ancak tamamen homomorfik olmanın tüm koşullarını karşılayan ve güvenliği kolayca kanıtlanabilen bir seçenek bulamıyorlar.
2009 yılına kadar Stanford'da eğitim gören PhD Craig Gentry'nin aklına bir fikir geldi ve FHE algoritmasının zorluklarını aştı. Doktora tezinde ilk kez makul ve güvenli bir tam homomorfik şifreleme sistemi ortaya koydu! Bu sistem ideal kafes varsayımına dayanmaktadır. Gentry09 tarafından önerilen tamamen homomorfik sisteme genellikle birinci nesil tamamen homomorfik şifreleme sistemi denir.
Gentry'nin makalesinde Bootstrapping adı verilen çok önemli bir kavramdan da bahsetti. Önyükleme, şifreli metin için özel bir işleme tekniğidir. İşlemden sonra, kritik değere yakın gürültüye sahip bir şifreli metni, çok düşük gürültülü yeni bir şifreli metne "yenileyebilir". Bootstrapping sayesinde sonlu serili bir sistemin gürültüsü hiçbir zaman kritik değeri aşamaz, böylece tamamen homomorfik bir sistem haline gelir. Bu şekilde herhangi bir boyuttaki F'yi homomorfik olarak hesaplayabiliriz.
Gentry'nin büyük atılımından sonra, tüm kriptografi çemberi yeniden çılgına döndü ve herkes, Gentry'nin önerdiği fikirlere dayanan, daha verimli ve çok yönlü, tamamen homomorfik bir sistem bulmak için çabalamaya başladı.
2011 yılında, iki büyük adam, Brakerski ve Vaikuntanathan, kafes şifrelemenin bir başka varsayımı olan Hatalarla Öğrenmeye (LWE) dayanan yeni bir tamamen homomorfik şifreleme sistemi önerdiler. Aynı yıl Brakerski, Gentry ve Vaikuntanathan sistemi tamamlayarak resmi olarak yayınladı. İcat ettikleri tamamen homomorfik sisteme kısaca BGV sistemi adı verilmektedir. BGV sistemi sınırlı düzeyde homomorfik bir şifreleme sistemidir ancak Bootstrapping yoluyla tamamen homomorfik bir sisteme dönüştürülebilir. Gentry09 tarafından önerilen sistemle karşılaştırıldığında BGV sistemi daha gerçekçi bir LWE varsayımı kullanır. Genel anlamda BGV sistemine ikinci nesil tam homomorfik şifreleme sistemi diyoruz.
2013 yılında Gentry geri dönüş yaptı. Gentry, Sahai ve Waters yeni bir GSW tamamen homomorfik şifreleme sistemini piyasaya sürdü. GSW sistemi, sonlu seriler tamamen homomorfik özelliklere sahip olması bakımından BGV'ye benzer. Daha basit LWE varsayımına dayanır ve Bootstrapping yoluyla tamamen homomorfik olabilir. GSW sistemini genel olarak üçüncü nesil tamamen homomorfik şifreleme sistemi olarak adlandırıyoruz.
2013'ten sonra kripto dünyası temelde gelişti. Orijinal üç nesil tamamen homomorfik sistemi temel alan, BGV ve GSW sistemlerinin çalışma verimliliğini optimize etmeye ve hızlandırmaya adanmış çeşitli yeni tasarımlar ortaya çıkmıştır. IBM, BGV sistemini temel alan açık kaynaklı, tamamen homomorfik bir bilgi işlem kitaplığı HElib geliştirdi ve bunu büyük mobil platformlara başarıyla nakletti. Aynı zamanda dikkat çeken bir başka açık kaynak projesi olan TFHE daha var. TFHE, çeşitli optimizasyonlar ve hızlandırmalar eklenmiş GSW sistemini temel almaktadır ve artık çok ünlüdür.
Geleneksel tamamen homomorfik kitaplıklar geliştirmenin yanı sıra, birçok ekip aynı zamanda GPU, FPGA ve ASIC gibi heterojen donanımlar aracılığıyla tamamen homomorfik şifreleme algoritmalarının hesaplanmasının nasıl daha iyi hızlandırılabileceğini de araştırıyor. Örneğin cuFHE, iyi bilinen CUDA tabanlı GPU hızlandırmalı, tamamen homomorfik bir şifreleme sistemidir.
Bugünün perspektifinden bakıldığında Gentry'nin tam homomorfik sistemin kapısını çalmasının üzerinden 11 yıl geçti. Günümüzde FHE ile ilgili araştırmalar sektörde patlama yaşıyor ve birçok kişi tamamen homomorfik sistemleri farklı perspektiflerden ve uygulama gereksinimlerinden inceliyor. Bugüne kadar zaten çeşitli uygulanabilir FHE uygulama yöntemlerimiz var, ancak herkesin hâlâ peşinde olduğu şey FHE sisteminin işleyişinin verimliliğidir. Mevcut son teknoloji ürünü FHE kütüphanesini örnek alırsak, mobil bir platformda nispeten basit bir mantığın homomorfik olarak hesaplanması, onlarca milisaniye kadar kısa ve onlarca saniye kadar sürebilir. Bu zaman birimleri bilgisayar sistemleri için son derece yavaştır.
FHE sisteminin heterojen platformlarda daha verimli çalışmasının nasıl sağlanacağı hala çözülmemiş bir gizemdir. Bu sorun bir kez çözülürse, tüm bilgisayar hesaplamalarını tamamen homomorfik hale getirmek ve aracıların hesaplamaları üçüncü taraf bulutlarda gerçekleştirmesini sağlamak kolay bir gelecek olacaktır.
FHE ve MPC arasındaki ilişki
Yazıyı bitirmeden önce FHE ile MPC arasındaki ilişkiye dair birkaç söz eklemek istiyorum. MPC, güvenilir çok taraflı hesaplama anlamına gelen Güvenli Çok Taraflı Hesaplama anlamına gelir. Bu genellikle birden fazla tarafın kendi özel girdilerine sahip olduğu ve bunları başkalarına açıklamak istemedikleri, ancak bir F fonksiyonunu birlikte hesaplamak ve hesaplamanın sonuçlarını paylaşmak için kendi girdilerini kullanmak istedikleri anlamına gelir.
MPC aslında çok iyi bilinen ve uzun süredir üzerinde çalışılan bir alan. Kriptograf Yao Qizhi'nin geçtiğimiz yüzyılda Bozuk Devreleri piyasaya sürmesinden bu yana, MPC alanı geniş çapta tanındı ve birçok atılım gerçekleşti. Artık kullanılabilecek çok sayıda MPC kitaplığımız var ve bunların belirli bir çalışma verimliliği de var.
MPC'yi bilen arkadaşlar, tamamen homomorfik şifreleme sistemlerinin zorlu geçmişini gördükten sonra birçok soru sorabilir: Neden tamamen homomorfik şifrelemenin yerini doğrudan bir MPC protokolü alamaz?
Gerçekten de bir MPC protokolü, bir FHE protokolünün yerini tamamen alabilir. Yalnızca kullanıcıyı ve özel girişi bir protokolde taraf olarak kullanmamız ve ardından MPC protokolünün yürütülmesi için gerekli koşulları karşılayan uzak proxy bilgi işlem sunucusunu başka bir taraf olarak kullanmamız gerekir.Proxy hesaplama yalnızca belirli etkileşimler yoluyla yapılabilir. Ve sunucu özel girişi göremiyor.
Ancak gözden kaçırdığımız çok önemli bir nokta var: MPC etkileşimli olduğundan, protokolü tamamlamak için kullanıcı ve sunucunun birlikte hesaplama yapması ve iletişim kurması gerekir. Bu, FHE aracı bilişiminin en temel gerekliliğiyle çelişmektedir. Kullanıcının sözleşmeyi tamamlamak için her zaman çevrimiçi kalması ve ayrıca bilgi işlem gücünün bir kısmını ödemesi gerekiyorsa, o zaman aslında hesaplama hiçbir şekilde "proxy" yapılmaz ve her iki taraf da yalnızca bilgi güvenliği adına daha fazla hesaplama yapar. . Bu aynı zamanda MPC alanının neden büyük atılımlar yaptığını da açıklıyor ancak FHE alanı hala bilinmiyor çünkü iki sistem tamamen farklı sorunları çözüyor.
## Sonraki durak: GSW tamamen homomorfik şifreleme sistemi
Bunu gören herkesin tam homomorfik şifreleme sistemini çok iyi anlamış olması gerekir.
Bir sonraki durakta yukarıda bahsettiğimiz GSW tam homomorfik şifreleme sistemi hakkında bilgi edinebiliriz. Her ne kadar bu tamamen homomorfik sistemlerin üçüncü nesli olsa da Gentry09, BGV ve GSW'nin üç sistemi arasında en az varsayıma sahip, en basit yapıya sahip ve anlaşılması en kolay olanın GSW olduğunu düşünüyorum. Ve şimdi GSW sistemi temel alınarak oluşturulmuş birçok açık kaynak kütüphane (TFHE gibi) var.
Yer sıkıntısı nedeniyle bu yazımızı burada sonlandıracağız. Bir sonraki makalede ilk olarak GSW sisteminin temellerini öğrenebiliriz: kafes tabanlı şifreleme sistemi ve LWE problemi. LWE sorunu anlaşıldıktan sonra GSW'nin çözdüğü sorun çok açık hale gelir.
View Original
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
Tamamen homomorfik şifrelemenin ön incelemesi: FHE'nin tanımı ve tarihsel incelemesi
Yazar: Steven Yue
Bir süre önce Stanford'da CS355 (İleri Kriptografi) dersini aldım. Dan'in üç doktora öğrencisi Dima Kogan, Florian Tramer ve Saba Eskandarian'dan eğitim aldık. Üç doktora öğretim üyesinin her birinin kendine has özellikleri vardır ve araştırma yönleri de oldukça farklıdır. Dima gizlilik koruma teknolojisi PIR'e (Özel Bilgi Retri), Florian makine öğrenimi ve blockchain araştırmasına, Saba ise sıfır bilgi kanıtına odaklanıyor.
CS355 kursu, antik çağlardan günümüze kriptografi alanındaki hemen hemen tüm içeriği kapsamaktadır. En eski tek yönlü fonksiyondan (Tek Yönlü Fonksiyon), eliptik denklemlere (ECC) ve Eşleştirmeye ve son olarak daha popüler MPC, sıfır bilgi, özel bilgi alımı (PIR), tamamen homomorfik algoritmalara vb. kadar. Son yıllarda. Ders iki gün önce bittiğinden beri, bilgi içeriği henüz sığ hafızamdayken bir dizi not düzenledim. Kursun içeriği çok ilgi çekici, geri kalan içeriği daha sonra vakit buldukça sizlerle paylaşacağım~
Bu sayımızda son dönemde popüler olan Tam Homomorfik Şifreleme (FHE) ve buna eşlik eden Kafes Tabanlı Şifreleme teknolojisinden bahsedeceğiz.
Tamamen homomorfik şifreleme nedir?
Pek çok arkadaşın Tam Homomorfik Şifreleme (FHE) adını duyduğunu düşünüyorum. Son yıllarda, kişisel gizliliğin korunmasına ilişkin giderek daha fazla konu ortaya çıktı ve homomorfik şifrelemeyi de içeren bir dizi kriptografi uygulama teknolojisi de geniş çapta popüler hale geldi.
Bu konunun daha iyi anlaşılabilmesi için tam homomorfik şifrelemenin tanımına kısaca değinmek istiyorum.
Şifreleme sistemi incelemesi
Başlamadan önce en geleneksel şifreleme sistemini inceleyelim.
Hepimiz bir şifreleme sistemi oluşturmak istiyorsanız genellikle bir anahtara ihtiyacınız olduğunu biliyoruz. Bu anahtar aracılığıyla, bir uçta düz metin bilgisini şifreli metne dönüştürebilir ve diğer uçta şifreli metni orijinal görünümüne döndürmek için anahtarı kullanabiliriz. Bu Anahtar olmadan başkalarının hangi bilgileri aktardığımızı bilmesi zor olurdu.
Kriptografi araştırmalarında yeni bir sistemin tanımını gördüğümüzde çoğu zaman sistemin sahip olması gereken özellikleri belirtmek zorunda kalırız.
Anlamsal güvenliğin temel önemi, izleyicinin iki şifrelenmiş mesajı birbirinden ayıramamasıdır. Yani eğer bir davetsiz misafir ağı gizlice dinler ve gönderdiğim şifreli bilgiyi görürse, kullandığım şifreleme sistemi anlamsal olarak güvenli olduğu sürece, davetsiz misafirin şifreli metinden şifrelenmiş içerik hakkında herhangi bir bilgi alamayacağından emin olabilirim.
Yukarıdaki iki özelliğin sağlanmasından sonra şifreleme sistemi sağlam hale gelir.
Şifreleme sisteminin ne olduğunu anladıktan sonra, rastgele oluşturulmuş bozuk koda benzeyen bu şifreli metne dikkat edebiliriz. Sadece şifreli metnin kendisine bakarak herhangi bir bilgi elde edemeyeceğimizi hepimiz biliyoruz. Peki bu, anahtar yoksa ve yalnızca şifreli metin varsa hiçbir şey yapamayacağımız anlamına mı geliyor?
Cevabı hepimiz biliyoruz: pek değil.
Bu özellik için buna toplamsal homomorfizm diyoruz. Bu, şifrelenmiş şifreli metnin önceki orijinal metinle ince bir cebirsel ilişkiyi koruduğu anlamına gelir. Şifreli metni toplarsak orijinal metni toplayarak şifrelenmiş yeni şifreli metni elde edebiliriz. Aynı şekilde eklemeli homomorfik şifreleme algoritmalarının da var olduğu sonucuna varılabilir. Çarpımsal homomorfik bir algoritma tarafından oluşturulan şifreli metni çarpabilir ve ardından orijinal metinlerin çarpılması sonucuna karşılık gelen şifreli metni elde edebiliriz. Tüm süreçte anahtarla ilgili herhangi bir bilgi bilmemize gerek yok, sadece rastgele bozuk kod gibi görünen şifreli metni birleştiriyoruz.
Örneğin: Anonim oylama sistemi
Şimdi homomorfik şifrelemenin pratikliğini canlı bir şekilde açıklamak için bir örnek verelim.
Çevrimiçi oylamanın nasıl bir şey olduğunu hepimiz biliyoruz; eğer bir şirketin patronu bir oylama dalgası başlatmak istiyorsa, şirketin 996 sistemini benimseyip benimsemeyeceğini seçin. Daha sonra patron BT'den bir sunucu kurmasını isteyebilir ve çalışanların seçimlerini göndermelerine izin verebilir: istemedikleri anlamına gelen 0 oyu ve istedikleri anlamına gelen 1 oyu. Son oylama döneminden sonra patron tüm oyları toplayabilir. Tüm oyların nihai toplamı çalışan sayısının yarısını aşarsa şirket 996 ile başlayacak.
Bu oylama mekanizması çok basit görünüyor, ancak büyük bir gizlilik sorunu var: Eğer patron tüm çalışanların 996 olmasını istiyorsa ve bu oylamayı yalnızca hangi çalışanın fazla mesai yapmak istemediğini görmek için kolluk kuvvetleri bulmak amacıyla kasıtlı olarak başlatıyorsa, o zaman patron Küçük kardeşini interneti gizlice dinlemesi, her çalışanın sunduğu tercihleri kaydetmesi ve sonunda kimin 0 oy verdiğini görmesi için görevlendirdi. Bunun sonucunda çalışanlar çok korkuyor ve duygularını ifade etmeye cesaret edemiyor.
Eğer eklemeli homomorfik şifreleme algoritması kullanabilirsek bu sorun kolayca çözülebilir.
Elbette bu sistem hala çok eksik. Örneğin, BT departmanı doğrudan patronun herkesin oylarının şifresini çözmesine ve bunları bir belgeye kaydetmesine yardımcı olabilir. Bu sorunu çözmemize yardımcı olabilecek başka şifreleme araçları da var. Yer sıkıntısı nedeniyle burada daha fazla açıklama yapılmayacaktır.
Ancak bu noktada homomorfik şifreleme algoritmasının gücünü hissedebilmemiz gerekiyor. Bunu şu şekilde anlayabiliriz: Homomorfik şifreleme algoritması aracılığıyla kullanıcılar, güvenilmeyen bir uzak sunucu (bulut) ile bir tür güvenli proxy hesaplaması (Güvenli Yetkilendirilmiş Hesaplama) gerçekleştirebilirler. Kullanıcılar homomorfik şifreleme teknolojisini kullanarak hassas özel girişlerini şifreleyebilir ve buluta emanet edebilirler.Daha sonra bulut, şifrelenmiş veriler üzerinde belirli bir düzeyde hesaplama gerçekleştirebilir ve son olarak kullanıcının istediği şifrelenmiş sonucu elde edip buluta geri gönderebilir. bulut.kullanıcı. Son olarak kullanıcı sonucu açmak için şifre çözme anahtarını kullanabilir. Anlaşmanın tamamı boyunca, yetki verilen taraf (bulut), özel girdilerle ilgili hiçbir yararlı bilgiyi asla göremez.
En temel iki homomorfik özelliği kabaca anladıktan sonra diğer kavramların anlaşılması da çok kolay hale gelir. Sistematik bir perspektiften bakıldığında, homomorfik şifreleme sistemleri kabaca dört kategoriye ayrılır: kısmi homomorfizm, yaklaşık homomorfizm, sonlu seri tam homomorfizm ve tam homomorfizm.
Şimdi sırasıyla her kategorinin spesifik tanımlarına göz atalım.
Kısmen Homomorfik Şifreleme
Homomorfik şifrelemenin en temel aşaması, şifreli metnin yalnızca bir homomorfik özelliğe sahip olması olarak tanımlanan, kısmen homomorfik şifreleme olarak adlandırılır. Bu aşama, yukarıda tanımladığımız iki toplamsal homomorfizm ve çarpımsal homomorfizm modunu içerir.
Bu iki mesajın çarpımına karşılık gelen şifreli metni elde ediyoruz! Bu, çarpımsal homomorfizm özelliğidir.Bu şifreli metinlerin üzerine yeni şifreli metinleri yerleştirmeye devam edebiliriz, böylece şifreli metinler arasında herhangi bir çarpım elde edebiliriz.
Yaklaşık Homomorfik Şifreleme (Biraz Homomorfik Şifreleme)
Önceki paragrafta da söylediğimiz gibi, eğer özel girişleri çoğaltıp aralarında doğrusal bir kombinasyon elde etmek istiyorsak, basit bir kısmen homomorfik şifreleme algoritması (RSA, ElGamal) tamamlanamaz. O halde bir sonraki aşamaya geçmemiz gerekiyor.
Kısmen homomorfik şifrelemenin bir sonraki aşaması yaklaşık olarak homomorfik şifrelemedir ve bu, elde etmek istediğimiz tamamen homomorfik şifrelemeye bir adım daha yakındır. Yaklaşık olarak homomorfik bir şifreleme algoritmamız varsa, şifreli metin üzerinde toplama ve çarpma işlemlerini aynı anda hesaplayabiliriz. Ancak şunu belirtmek gerekir ki bu aşama yaklaşık olarak homomorfik (Biraz Homomorfik) olduğundan yapılabilecek toplama ve çarpma sayısı oldukça sınırlıdır, hesaplanabilen F fonksiyonu da sınırlı bir aralıktadır.
Yaklaşık olarak homomorfik şifrelemenin bu aşamada pek yaygın örneği yoktur, en iyi anlaşılan örneği dersek eşleştirmeye dayalı döngüsel grup şifreleme algoritması olsa gerek.
Yukarıda sıradan döngüsel gruplara dayanan ElGamal şifreleme algoritmasını kısaca tartıştık. Hepimiz bu algoritmanın eklemeli olarak homomorfik olduğunu biliyoruz, bu da rastgele şifreli metinler arasında doğrusal kombinasyonlar elde edebileceği anlamına geliyor. Aslında bazı özel döngüsel gruplarda bazı zayıf çarpımsal homomorfizm özelliklerini de bulabiliriz.
Bu sınırlama sistemin yaklaşık olarak homomorfik olduğunu kanıtlar çünkü keyfi mantık ve derinlik F fonksiyonunu hesaplayamıyoruz.
Tam Seviyeli Homomorfik Şifreleme
Bir sonraki aşamaya ulaştıktan sonra tam homomorfizm hedefine bir adım daha yaklaşıyoruz.
Bu aşamaya sonlu seri tam homomorfik şifreleme adı verilir. Bu aşamada zaten şifreli metin üzerinde herhangi bir sayı sınırlaması olmaksızın herhangi bir toplama ve çarpma kombinasyonunu gerçekleştirebiliyoruz.
Tam Homomorfik Şifreleme (FHE)
Pek çok çağrının ardından nihayet görmeyi beklediğimiz tam homomorfik şifrelemeye (FHE) geliniyor.
Adından da anlaşılacağı gibi, tamamen homomorfik bir şifreleme sisteminin hesaplama yöntemleri üzerinde hiçbir kısıtlaması yoktur.Şifreli metinleri, anahtar olmadan yeni şifreli metinler oluşturmak için keyfi olarak birleştirebiliriz ve yeni şifreli metin Metni, hesaplama karmaşıklığına bakılmaksızın, orijinal metne mükemmel bir şekilde geri yüklenebilir.
Bu aşamaya geldiğimizde daha önce bahsettiğimiz güvenli ajan hesaplaması mümkün hale gelir. Daha verimli, tamamen homomorfik bir şifreleme sistemi bulabilirsek, herhangi bir veri sızıntısı olmadan tüm yerel hesaplamaları güvenli bir şekilde buluta aktarabiliriz!
Tamamen homomorfik şifreleme sisteminin tanımı
Aşağıda tamamen homomorfik sistemlerin tarihinin tartışılmasına başlamadan önce, tamamen homomorfik sistemlerin resmi tanımını sistematik olarak tanımlayabiliriz. Tamamen homomorfik bir şifreleme sisteminin toplam dört algoritması vardır:
Tam homomorfik şifreleme algoritmasının nasıl uygulandığını öğrenmeye başlamadan önce, tam homomorfik şifreleme kavramının nasıl ortaya çıktığına bir göz atsak iyi olur.
FHE (tamamen homomorfik) kavramı aslında 1970'lerin sonlarında önerildi. 1978 yılında, kriptografinin birçok büyük ismi olan Rivest, Adleman ve Dertouzos, ilk kez Veri Bankaları ve Gizlilik Homomorfizmleri Üzerine makalelerinde, şifreli metin üzerinde belirli hesaplamaları gerçekleştirebilen ve dolaylı olarak orijinal metin üzerinde çalışabilen bir sistem fikrinden bahsetmişlerdir. Daha sonra bu fikir yeniden özetlendi ve tamamen homomorfik şifreleme olarak adlandırıldı.
Tamamen homomorfik şifreleme kavramının uzun süredir önerildiği görülmektedir. Şaşırtıcı bir şekilde, 1976'da, yani makalenin yayınlanmasından iki yıl önce, Diffle-Hellman anahtar değişim protokolü henüz teklif edilmişti! Bu da kriptografi uzmanlarının hayal gücünün hala çok zengin olduğunu gösteriyor.
FHE kavramı önerildiğinde, tüm akademik topluluk bundan etkilendi ve tamamen homomorfik özelliklere sahip mükemmel bir algoritma bulmaya çalışarak onlarca yıl süren bir araştırmaya başladı. Ancak son birkaç on yılda insanlar akla gelebilecek tüm seçenekleri denediler, ancak tamamen homomorfik olmanın tüm koşullarını karşılayan ve güvenliği kolayca kanıtlanabilen bir seçenek bulamıyorlar.
2009 yılına kadar Stanford'da eğitim gören PhD Craig Gentry'nin aklına bir fikir geldi ve FHE algoritmasının zorluklarını aştı. Doktora tezinde ilk kez makul ve güvenli bir tam homomorfik şifreleme sistemi ortaya koydu! Bu sistem ideal kafes varsayımına dayanmaktadır. Gentry09 tarafından önerilen tamamen homomorfik sisteme genellikle birinci nesil tamamen homomorfik şifreleme sistemi denir.
Gentry'nin makalesinde Bootstrapping adı verilen çok önemli bir kavramdan da bahsetti. Önyükleme, şifreli metin için özel bir işleme tekniğidir. İşlemden sonra, kritik değere yakın gürültüye sahip bir şifreli metni, çok düşük gürültülü yeni bir şifreli metne "yenileyebilir". Bootstrapping sayesinde sonlu serili bir sistemin gürültüsü hiçbir zaman kritik değeri aşamaz, böylece tamamen homomorfik bir sistem haline gelir. Bu şekilde herhangi bir boyuttaki F'yi homomorfik olarak hesaplayabiliriz.
Gentry'nin büyük atılımından sonra, tüm kriptografi çemberi yeniden çılgına döndü ve herkes, Gentry'nin önerdiği fikirlere dayanan, daha verimli ve çok yönlü, tamamen homomorfik bir sistem bulmak için çabalamaya başladı.
2011 yılında, iki büyük adam, Brakerski ve Vaikuntanathan, kafes şifrelemenin bir başka varsayımı olan Hatalarla Öğrenmeye (LWE) dayanan yeni bir tamamen homomorfik şifreleme sistemi önerdiler. Aynı yıl Brakerski, Gentry ve Vaikuntanathan sistemi tamamlayarak resmi olarak yayınladı. İcat ettikleri tamamen homomorfik sisteme kısaca BGV sistemi adı verilmektedir. BGV sistemi sınırlı düzeyde homomorfik bir şifreleme sistemidir ancak Bootstrapping yoluyla tamamen homomorfik bir sisteme dönüştürülebilir. Gentry09 tarafından önerilen sistemle karşılaştırıldığında BGV sistemi daha gerçekçi bir LWE varsayımı kullanır. Genel anlamda BGV sistemine ikinci nesil tam homomorfik şifreleme sistemi diyoruz.
2013 yılında Gentry geri dönüş yaptı. Gentry, Sahai ve Waters yeni bir GSW tamamen homomorfik şifreleme sistemini piyasaya sürdü. GSW sistemi, sonlu seriler tamamen homomorfik özelliklere sahip olması bakımından BGV'ye benzer. Daha basit LWE varsayımına dayanır ve Bootstrapping yoluyla tamamen homomorfik olabilir. GSW sistemini genel olarak üçüncü nesil tamamen homomorfik şifreleme sistemi olarak adlandırıyoruz.
2013'ten sonra kripto dünyası temelde gelişti. Orijinal üç nesil tamamen homomorfik sistemi temel alan, BGV ve GSW sistemlerinin çalışma verimliliğini optimize etmeye ve hızlandırmaya adanmış çeşitli yeni tasarımlar ortaya çıkmıştır. IBM, BGV sistemini temel alan açık kaynaklı, tamamen homomorfik bir bilgi işlem kitaplığı HElib geliştirdi ve bunu büyük mobil platformlara başarıyla nakletti. Aynı zamanda dikkat çeken bir başka açık kaynak projesi olan TFHE daha var. TFHE, çeşitli optimizasyonlar ve hızlandırmalar eklenmiş GSW sistemini temel almaktadır ve artık çok ünlüdür.
Geleneksel tamamen homomorfik kitaplıklar geliştirmenin yanı sıra, birçok ekip aynı zamanda GPU, FPGA ve ASIC gibi heterojen donanımlar aracılığıyla tamamen homomorfik şifreleme algoritmalarının hesaplanmasının nasıl daha iyi hızlandırılabileceğini de araştırıyor. Örneğin cuFHE, iyi bilinen CUDA tabanlı GPU hızlandırmalı, tamamen homomorfik bir şifreleme sistemidir.
Bugünün perspektifinden bakıldığında Gentry'nin tam homomorfik sistemin kapısını çalmasının üzerinden 11 yıl geçti. Günümüzde FHE ile ilgili araştırmalar sektörde patlama yaşıyor ve birçok kişi tamamen homomorfik sistemleri farklı perspektiflerden ve uygulama gereksinimlerinden inceliyor. Bugüne kadar zaten çeşitli uygulanabilir FHE uygulama yöntemlerimiz var, ancak herkesin hâlâ peşinde olduğu şey FHE sisteminin işleyişinin verimliliğidir. Mevcut son teknoloji ürünü FHE kütüphanesini örnek alırsak, mobil bir platformda nispeten basit bir mantığın homomorfik olarak hesaplanması, onlarca milisaniye kadar kısa ve onlarca saniye kadar sürebilir. Bu zaman birimleri bilgisayar sistemleri için son derece yavaştır.
FHE sisteminin heterojen platformlarda daha verimli çalışmasının nasıl sağlanacağı hala çözülmemiş bir gizemdir. Bu sorun bir kez çözülürse, tüm bilgisayar hesaplamalarını tamamen homomorfik hale getirmek ve aracıların hesaplamaları üçüncü taraf bulutlarda gerçekleştirmesini sağlamak kolay bir gelecek olacaktır.
FHE ve MPC arasındaki ilişki
Yazıyı bitirmeden önce FHE ile MPC arasındaki ilişkiye dair birkaç söz eklemek istiyorum. MPC, güvenilir çok taraflı hesaplama anlamına gelen Güvenli Çok Taraflı Hesaplama anlamına gelir. Bu genellikle birden fazla tarafın kendi özel girdilerine sahip olduğu ve bunları başkalarına açıklamak istemedikleri, ancak bir F fonksiyonunu birlikte hesaplamak ve hesaplamanın sonuçlarını paylaşmak için kendi girdilerini kullanmak istedikleri anlamına gelir.
MPC aslında çok iyi bilinen ve uzun süredir üzerinde çalışılan bir alan. Kriptograf Yao Qizhi'nin geçtiğimiz yüzyılda Bozuk Devreleri piyasaya sürmesinden bu yana, MPC alanı geniş çapta tanındı ve birçok atılım gerçekleşti. Artık kullanılabilecek çok sayıda MPC kitaplığımız var ve bunların belirli bir çalışma verimliliği de var.
MPC'yi bilen arkadaşlar, tamamen homomorfik şifreleme sistemlerinin zorlu geçmişini gördükten sonra birçok soru sorabilir: Neden tamamen homomorfik şifrelemenin yerini doğrudan bir MPC protokolü alamaz?
Gerçekten de bir MPC protokolü, bir FHE protokolünün yerini tamamen alabilir. Yalnızca kullanıcıyı ve özel girişi bir protokolde taraf olarak kullanmamız ve ardından MPC protokolünün yürütülmesi için gerekli koşulları karşılayan uzak proxy bilgi işlem sunucusunu başka bir taraf olarak kullanmamız gerekir.Proxy hesaplama yalnızca belirli etkileşimler yoluyla yapılabilir. Ve sunucu özel girişi göremiyor.
Ancak gözden kaçırdığımız çok önemli bir nokta var: MPC etkileşimli olduğundan, protokolü tamamlamak için kullanıcı ve sunucunun birlikte hesaplama yapması ve iletişim kurması gerekir. Bu, FHE aracı bilişiminin en temel gerekliliğiyle çelişmektedir. Kullanıcının sözleşmeyi tamamlamak için her zaman çevrimiçi kalması ve ayrıca bilgi işlem gücünün bir kısmını ödemesi gerekiyorsa, o zaman aslında hesaplama hiçbir şekilde "proxy" yapılmaz ve her iki taraf da yalnızca bilgi güvenliği adına daha fazla hesaplama yapar. . Bu aynı zamanda MPC alanının neden büyük atılımlar yaptığını da açıklıyor ancak FHE alanı hala bilinmiyor çünkü iki sistem tamamen farklı sorunları çözüyor.
Bunu gören herkesin tam homomorfik şifreleme sistemini çok iyi anlamış olması gerekir.
Bir sonraki durakta yukarıda bahsettiğimiz GSW tam homomorfik şifreleme sistemi hakkında bilgi edinebiliriz. Her ne kadar bu tamamen homomorfik sistemlerin üçüncü nesli olsa da Gentry09, BGV ve GSW'nin üç sistemi arasında en az varsayıma sahip, en basit yapıya sahip ve anlaşılması en kolay olanın GSW olduğunu düşünüyorum. Ve şimdi GSW sistemi temel alınarak oluşturulmuş birçok açık kaynak kütüphane (TFHE gibi) var.
Yer sıkıntısı nedeniyle bu yazımızı burada sonlandıracağız. Bir sonraki makalede ilk olarak GSW sisteminin temellerini öğrenebiliriz: kafes tabanlı şifreleme sistemi ve LWE problemi. LWE sorunu anlaşıldıktan sonra GSW'nin çözdüğü sorun çok açık hale gelir.