Gizli bilgi erişimi

**Gizli bilgi erişimi**, kullanıcının bir veritabanından veri talep etmesi sonucunda, hangi bilginin talep edildiğinin veritabanı tarafından gözetlenememe durumudur. GBE, n-içinden-1 habersiz transferin daha zayıf bir versiyonudur.

Kullanışlı olmadığı halde bu protokolu gerçekleştirmek için kullanılabilecek bir yöntem: veritabanından bir bilgi talep edildiğinde, kullanıcaya tüm veritabanının bir kopyasını yollamaktır. Aslında bu tek sunuculu bir sistem (klasik veya kuantum kriptografik sistemler) için bilgi teorisindeki güvenlik şartını sağlayabilen tek yöntemdir. Bu problem için yapılabilecek iki yordam vardır; işlemsel olarak bağlı bir sunucu veya birbirinden bağımsız sunucuların aynı veritabanına sahip olma durumu.

Fikir 1995'te Chor, Goldreich, Kushilevitz ve Sudan tarafından bilgi teorisi seviyesinde, 1997'de Kushilevitz ve Ostrovsky tarafından yazılımsal olarak sunulmuştur. Takibinde bu problem için çok daha efektik çözümler keşfedilmiştir.Tekli bir veritabanı için (işlemsel gizlilik) GBE olanağı amortize iletişim ile, k-veritabanı (bilgi teorisi) için GBE ise, n^{O\left(\frac{\log \log k}{k \log k}\right)} ile gerçekleştirilebilir.

## Yazılımsal GBE'deki gelişmeler
İletişim karmaşıklığının n'den daha aza indirildiği ilk  GBE tekniği 1997 yılında Kushilevitz ve Ostrovsky tarafından yaratılmış ve herhangi bir \epsilon değeri için, n^\epsilon karmaşıklığını elde edilmiştir (n, veritabanınındaki bit sayısı). Tekniğin arka planı, Kuadratik artıklık problemine dayanıyordu. 1999'da Christian Cachin, Silvio Micali ve Markus Stadler poli-logaritmik iletişim karmaşıklığına ulaştı. Sistemlerinin güvenliği, Phi-gizleme varsayımına dayanmaktadır. 2004 yılında, Helger Lipmaa log-kare iletişim karmaşıklığını elde etti. O(\ell \log n+k \log^2 n), (\ell dizgi uzunluğu ve k güvenlik parametresidir). Sisteminin güvenliği, Damgård–Jurik şifreleme sistemi gibi uzunluk açısından esnek, toplamsal olarak homomorfik bir şifreleme sisteminin anlamsal güvenliğine indirgenir. 2005 yılında Craig Gentry ve Zulfikar Ramzan, veritabanının log-kare (ardışık) bitlerini alan log-kare iletişim karmaşıklığını elde ettiler. Bu teknik için de güvenlik, Phi-gizleme varsayımının bir çeşidine dayanmaktadır. 2015 yılında nihayetinde iletişim karmaşıklığı Aggelos Kiayias, Nikos Leonardos, Helger Lipmaa, Kateryna Pavlyk ve Qiang Tang tarafından  1 'e düşürüldü.

Öncelerde tüm açık-anahtar şifrelemeli operasyonlarda, alt doğrusal iletişim hesaplamalı GBE protokolü, aşağıdakilerin doğrusal hesaplama karmaşıklığını, \Omega (n), gerektiriyordu. 2009'da Helger Lipmaa,O(\ell \log n+k \log^2 n) iletişim karmaşıklığına ve en kötü durum için O (n / \log n) hesaplamasına sahip GBE protokolü tasarladı. Ardışık olmayan bitleri alan amortisman teknikleri Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky ve Amit Sahai taraflarınca değerlendirildi.

Ostrovsky ve Skeith tarafından kanıtlandığı gibi, Kushilevitz ve Ostrovsky ve Lipmaa'nın tasarımları homomorfik şifrelemeye dayalı benzer altyapılara dayanmıştır. Kushilevitz ve Ostrovsky protokolü Goldwasser- Micali şifreleme sistemine, Lipmaa protokolü ise Damgård -Jurik şifreleme sistemine dayanmaktadır.

## Bilgi teorik GBE'deki gelişmeler
Bilgi teorik güvenliğinin sağlanması, her biri veritabanının bir kopyasına sahip olan, işbirliği yapmayan birden çok sunucu olduğu varsayımını gerektirmektedir. Bu varsayım olmadan, herhangi bir bilgi-teorik olarak güvenli GBE protokolü, en azından veritabanının *n* boyutu kadar bir iletişim miktarı gerektirir. Yanıtlamayan ya da kötü niyetli/danışman sunuculara toleranslı çok sunuculu GBE protokollerine sırasıyla *sağlam* veya *Bizans sağlamlığı* denir. Bu konular ilk olarak Beimel ve Stahl (2002) tarafından ele alınmıştır. Yalnızca *k* sunucusunun yanıt verdiği, sunucuların &#x3BD; yanlış yanıt verdiği yerde çalışabilen ve istemcinin sorgusunu açığa çıkarmadan *t* gizli sunucuya dayanabilen bir ℓ-sunucu sistemine " *t* -özel &#x3BD; -Bizans sağlam *k* -out denir. -of-ℓ GBE" [DGH 2012]. 2012 yılında Ç.&nbsp;Devir, İ.&nbsp;Goldberg ve N.nbsp;Heninger (DGH 2012), Bizans'a dayanıklı, optimal olarak sağlam bir şema önerdi. \nu  bu teorik maksimum değerdir. Sorguyu gizlemek için Shamir'in Gizli Paylaşımını kullanan daha önceki bir Goldberg protokolüne dayanır. Goldberg, SourceForge üzerinde bir C++ uygulaması yayınladı.

## Diğer kriptografik ilkellerle ilişkisi
Tek yönlü fonksiyonlar, önemli (yani, alt-doğrusal iletişim ile) tek veritabanı hesaplamalı özel bilgi alımı için gereklidir, ancak yeterli oldukları bilinmemektedir. Aslında, böyle bir protokolün Giovanni Di Crescenzo, Tal Malkin ve Rafail Ostrovsky tarafından habersiz transferi ima ettiği kanıtlanmıştır (aşağıya bakınız).

Simetrik GBE olarak da adlandırılan habersiz transfer, kullanıcının istediği dışında herhangi bir öğe öğrenemeyeceği ek kısıtlaması olan GBE'dir. Simetrik olarak adlandırılır, çünkü hem kullanıcı hem de veritabanı bir gizlilik gereksinimine sahiptir.

Çarpışmaya dayanıklı kriptografik karma işlevleri, Ishai, Kushilevitz ve Ostrovsky tarafından gösterildiği gibi, herhangi bir tek yönlü hesaplamalı GBE şeması tarafından ima edilir.

## GBE varyasyonları
Özel Bilgi Erişimi için temel motivasyon, taraflardan birinin (*gönderen*) bir veritabanına sahip olduğu ve diğer tarafın (*alıcı*) belirli gizlilik kısıtlamaları ve garantileri ile sorgulamak istediği iki taraflı bir protokol ailesidir. Yani protokolün bir sonucu olarak, eğer *alıcı* veritabanında *i-th* değerini istiyorsa *i-th* girişini öğrenmeli, ancak *gönderici* *i* hakkında hiçbir şey öğrenmemesi gerekmektedir. Genel bir GBE protokolünde, hesaplama açısından sınırsız bir *gönderici*, *i* hakkında hiçbir şey öğrenemez, bu nedenle gizlilik teorik olarak korunmaktadır. GBE problemi ortaya atıldığından beri çözümüne farklı yaklaşımlar izlenmiş ve bazı varyasyonlar önerilmiştir.

Bir CGBE (Yazılımsal Olarak Gizli Bilgi Erişimi) protokolü, bir GBE protokolüne benzer: *alıcı*, göndericinin veri tabanından kendisi tarafından seçilen bir öğeyi alır, böylece *gönderici*, hangi öğenin aktarıldığı hakkında hiçbir bilgi alamaz. Tek fark, mahremiyetin polinomla sınırlandırılmış bir göndericiye karşı korunmasıdır.

Bir CGBE protokolünün kullanıldığı benzer bir senaryoda bir CSGBE (Yazılımsal Simetrik Gizli Bilgi Erişimi) protokolü kullanılır. *Gönderici* bir veri tabanına sahipse ve *alıcı* bu veri tabanından *i-th* değerini almak istiyorsa, bir SGBE protokolünün yürütülmesi sonunda *alıcının* *i-th* dışında veri tabanındaki değerler hakkında hiçbir şey öğrenmemiş olması gerekir.

## GBE uygulamaları
Literatürde çok sayıda Hesaplamalı GBE ve Bilgi teorik GBE şemaları uygulanmıştır. İşte bir liste:

* MuchGBE, Postgres C/C++ Uzantısı [GitHub, 2021] olarak bir CGBE uygulamasıdır.
* SealGBE hızlı bir CGBE uygulamasıdır [ACLS 2018].
* Popcorn, medya [GCMSAW 2016] için uyarlanmış bir GBE uygulamasıdır.
* Percy++, [AG 2007, DGH 2012, CGKS 1998, Goldberg 2007, HOG 2011, LG 2015] uygulamalarını içerir.
* RAID-GBE, [DHS 2014]'ün ITGBE şemasının bir uygulamasıdır.
* XGBE, hızlı bir CGBE uygulamasıdır [ABFK 2014].
* upGBE bir ITGBE uygulamasıdır [Cappos 2013].

## Kaynakça

## Dış bağlantılar
* Helger Lipmaa'nın habersiz aktarım ve GBE ile ilgili web bağlantıları 
* Anket makaleleri de dahil olmak üzere GBE üzerinde William Gasarch'ın web sitesi 
* Rafail Ostrovsky'nin GBE makaleleri ve anketleri içeren web sitesi