Kriptograflar Tam Arama Gizliliği İçin Bir Yaklaşım Geliştirdi | Quanta Dergisi

Çevrimiçi olarak paylaştığımız ayrıntılar konusunda dikkatli olmamız gerektiğini hepimiz biliyoruz, ancak aradığımız bilgiler de açıklayıcı olabilir. Arabayla yol tariflerini aradığınızda konumumuzun tahmin edilmesi çok daha kolay hale gelir. Güvenliği ihlal edilmiş verilerden oluşan bir hazinede parola olup olmadığını kontrol ederseniz parolayı kendimiz sızdırma riskiyle karşı karşıya kalırız.

Bu durumlar kriptografide önemli bir soruyu tetikliyor: Eriştiğiniz şeylerle ilgili hiçbir şeyi açıklamadan, halka açık bir veri tabanından nasıl bilgi çekebilirsiniz? Bu, kütüphanecinin hangisi olduğunu bilmeden kütüphaneden bir kitabı kontrol etmeye eşdeğerdir.

Özel bilgi alımı olarak bilinen bu sorunu çözen bir strateji oluşturmanın, "gizliliği koruyan birçok uygulamada çok yararlı bir yapı taşı" olduğu belirtildi. David WuAustin Texas Üniversitesi'nden bir kriptograf. 1990'lı yıllardan bu yana araştırmacılar, veritabanlarına özel erişim stratejileri geliştirerek bu soruyu biraz daha çözdüler. Büyük veritabanlarında hala imkansız olan ana hedeflerden biri, herhangi bir ağır hesaplama yükü olmadan bir yığın veriyi anonim olarak inceleyebileceğiniz özel bir Google aramasına eşdeğerdir.

Şimdi üç araştırmacı hazırlanmış özel bilgi almanın uzun süredir aranan bir versiyonuydu ve bunu daha genel bir gizlilik stratejisi oluşturacak şekilde genişletti. Ödül alan çalışma En İyi Kağıt Ödülü Haziran ayında yıllık Hesaplama Teorisi Sempozyumu, gerçekten özel bir aramaya giden yolda büyük bir teorik engeli ortadan kaldırır.

"[Bu] kriptografide sanırım hepimizin istediği ama var olduğuna pek inanmadığı bir şey" dedi Vinod VaikuntanathanMakalede yer almayan Massachusetts Teknoloji Enstitüsü'nden bir kriptograf. "Bu dönüm noktası niteliğinde bir sonuç."

Özel veri tabanına erişim sorunu 1990'lı yıllarda şekillendi. İlk başta, araştırmacılar tek çözümün her arama sırasında veri tabanının tamamını taramak olduğunu varsaydı; bu, kitabınızla birlikte geri dönmeden önce bir kütüphanecinin her rafı taramasına benzerdi. Sonuçta, arama herhangi bir bölümü atlarsa kütüphaneci kitabınızın kütüphanenin o bölümünde olmadığını bilir.

Bu yaklaşım daha küçük ölçeklerde yeterince işe yarar, ancak veritabanı büyüdükçe onu taramak için gereken süre de en azından orantılı olarak artar. Daha büyük veritabanlarından okudukça (ve internet oldukça büyük) süreç aşırı derecede verimsiz hale geliyor.

2000'li yılların başında araştırmacılar, veritabanını "ön işleme tabi tutarak" tam tarama engelini aşabileceklerinden şüphelenmeye başladılar. Kabaca bu, veritabanının tamamının özel bir yapı olarak kodlanması anlamına gelir; böylece sunucu, bu yapının yalnızca küçük bir bölümünü okuyarak bir sorguya yanıt verebilir. Yeterince dikkatli bir ön işleme, teorik olarak, bilgileri barındıran tek bir sunucunun süreçten yalnızca bir kez geçmesi ve gelecekteki tüm kullanıcıların daha fazla çaba harcamadan bilgileri özel olarak almasına olanak sağlaması anlamına gelebilir.

İçin Daniel WichsNortheastern Üniversitesi'nde bir kriptograf ve yeni makalenin ortak yazarı, bu gerçek olamayacak kadar iyi görünüyordu. 2011 yılı civarında bu tür bir planın imkansız olduğunu kanıtlamaya çalıştı. "Bunun yapılmasının hiçbir yolu olmadığına ikna oldum" dedi.

Ancak 2017'de iki grup araştırmacı yayınlanan Sonuçlar bu onun fikrini değiştirdi. Bu tür özel bilgi alımını gerçekleştirebilecek ilk programları geliştirdiler, ancak programların güvenli olduğunu gösteremediler. (Kriptograflar, bir sistemin güvenliğini, onu kırmanın zor bir problemi çözmek kadar zor olduğunu göstererek gösterirler. Araştırmacılar bunu kanonik zor bir problemle karşılaştıramadılar.)

Dolayısıyla Wichs, umudu yenilenmiş olsa bile bu programların güvenli herhangi bir versiyonunun henüz çok uzakta olduğunu varsayıyordu. Bunun yerine, o ve ortak yazarları — Wei-Kai Lin, şu anda Virginia Üniversitesi'nde ve Ethan Mook, yine Northeastern'da - veritabanını birden fazla sunucunun barındırdığı durumları içeren, daha kolay olacağını düşündükleri sorunlar üzerinde çalıştı.

Çalıştıkları yöntemlerde veri tabanındaki bilgiler, sunucuların bilgiyi çıkarmak için değerlendirebileceği matematiksel bir ifadeye dönüştürülebilmektedir. Yazarlar, değerlendirme sürecini daha verimli hale getirmenin mümkün olabileceğini düşündüler. Diğer araştırmacıların böyle bir ifadeyi ön işleme tabi tutarak hızlı bir şekilde değerlendirmenin bir yolunu bulduğu, normal değerlendirme adımlarını atlamanıza olanak tanıyan özel, kompakt değer tabloları oluşturduğu 2011'den kalma bir fikir üzerinde çalıştılar.

Bu yöntem herhangi bir gelişme sağlamadı ve grup pes etme noktasına geldi; ta ki bu aracın çok arzu edilen tek sunuculu durumda gerçekten işe yarayıp yaramayacağını merak edene kadar. Bir polinomun yeterince dikkatli seçildiğini ve tek bir sunucunun bunu 2011 sonucuna göre ön işleme tabi tutabildiğini gördüler; bu, Wichs'in yıllardır üzerinde düşündüğü güvenli, verimli arama şemasını ortaya çıkardı. Aniden, en zor sorunu çözdüler.

Başlangıçta yazarlar buna inanmadılar. Wichs, "Bunda neyin yanlış olduğunu bulalım," diye düşündüğünü hatırladı. "Nerede bozulduğunu bulmaya çalıştık."

Ancak çözüm işe yaradı: Herkesin gizlice bilgi alabilmesi için tek sunuculu bir veritabanını önceden işlemenin güvenli bir yolunu keşfetmişlerdi. "Gerçekten umduğumuz her şeyin ötesinde" dedi Yuval İşhaiİsrail'deki Technion'da bu çalışmaya dahil olmayan bir kriptograf. Bunun bir sonucu olduğunu “istemeye bile cesaret edemedik” dedi.

Wichs, gizli arama planlarını oluşturduktan sonra yazarların gerçek dünyadaki özel internet arama hedefine yöneldiklerini ve bunun veri tabanından bilgi parçaları çekmekten daha karmaşık olduğunu söyledi. Özel arama şeması kendi başına Google benzeri özel aramanın bir versiyonuna izin verir, ancak son derece emek yoğundur: Google'ın algoritmasını kendiniz çalıştırırsınız ve gerektiğinde gizlice internetten veri çekersiniz. Wichs, bir istek gönderdiğiniz ve sunucu sonuçları toplarken arkanıza yaslandığınız gerçek bir aramanın, aslında homomorfik şifreleme olarak bilinen daha geniş bir yaklaşımın hedefi olduğunu söyledi. Bu yaklaşım, başka birisinin bu konuda hiçbir şey bilmeden verileri değiştirebilmesi için verileri gizler. .

Tipik homomorfik şifreleme stratejileri, her aramada internetin tüm içeriğini tarayarak, özel bilgi alımıyla aynı engele çarpacaktır. Ancak yazarlar, özel arama yöntemini iskele olarak kullanarak, her gün kullandığımız programlara daha çok benzeyen hesaplamaları çalıştıran, tüm interneti taramadan bilgileri gizlice çeken yeni bir şema oluşturdular. Bu, internet aramaları ve verilere hızlı erişim gerektiren tüm programlar için verimlilik artışı sağlayacaktır.

Ishai, homomorfik şifrelemenin özel arama planının yararlı bir uzantısı olmasına rağmen, özel bilgilerin alınmasını daha temel bir sorun olarak gördüğünü söyledi. Yazarların çözümü "sihirli yapı taşı"dır ve onların homomorfik şifreleme stratejisi doğal bir takiptir.

Şimdilik, her iki şema da pratik olarak kullanışlı değil: Ön işleme, veritabanı boyutunun sonsuza doğru uçtuğu uç noktalarda yardımcı oluyor. Ancak gerçekte bunu dağıtmak, bu tasarrufların gerçekleşemeyeceği ve sürecin çok fazla zaman ve depolama alanı tüketeceği anlamına gelir.

Neyse ki Vaikuntanathan, kriptografların başlangıçta pratik olmayan sonuçları optimize etme konusunda uzun bir geçmişe sahip olduğunu söyledi. Gelecekteki çalışmalar yaklaşımı kolaylaştırabilirse, dev veritabanlarından özel aramaların ulaşılabilir olabileceğine inanıyor. "Hepimiz orada sıkışıp kaldığımızı düşündük" dedi. "Daniel'in sonucu umut veriyor."

Kuantum izleyicilerimize daha iyi hizmet verebilmek için bir dizi anket yürütüyor. Bizimkini al bilgisayar bilimi okuyucu anketi ve ücretsiz kazanmak için girileceksiniz Kuantum mal.