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.^[1] 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^[1] 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^[2] 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^[3] 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,^[4] $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,^[5] Kushilevitz ve Ostrovsky^[1] ve Lipmaa'nın^[3] 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 ν yanlış yanıt verdiği yerde çalışabilen ve istemcinin sorgusunu açığa çıkarmadan t gizli sunucuya dayanabilen bir ℓ-sunucu sistemine " t -özel ν -Bizans sağlam k -out denir. -of-ℓ GBE" [DGH 2012]. 2012 yılında Ç. Devir, İ. Goldberg ve N.<span typeof="mw:Entity" id="mwXA"> </span>Heninger (DGH 2012), Bizans'a dayanıklı, optimal olarak sağlam bir şema önerdi. $\nu <k-t-1$ 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ı.^[6]

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.^[7]

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.^[4] Tek fark, mahremiyetin polinomla sınırlandırılmış bir göndericiye karşı korunmasıdır.^[8]

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.^[8]

GBE uygulamaları

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

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

Kaynakça

^ ^a ^b ^c "Replication is not needed: single database, computationally-private information retrieval". Proceedings of the 38th Annual Symposium on Foundations of Computer Science. Miami Beach, Florida, USA: IEEE Computer Society. 1997. ss. 364-373. doi:10.1109/SFCS.1997.646125. ISBN 978-0-8186-8197-4.
^ "Computationally Private Information Retrieval with Polylogarithmic Communication". Advances in Cryptology - EUROCRYPT '99. Prague, Czech Republic: Springer-Verlag. 1999. ss. 402-414. doi:10.1007/3-540-48910-X_28. ISBN 978-3-540-48910-8.
^ ^a ^b "An Oblivious Transfer Protocol with Log-Squared Communication". Proceedings of the 8th International Conference on Information Security (ISC 2005). Lecture Notes in Computer Science. 3650. Singapore: Springer-Verlag. 2005. ss. 314-328. doi:10.1007/11556992_23. ISBN 978-3-540-31930-6.
^ ^a ^b "First CPIR Protocol with Data-Dependent Computation". Proceedings of the 12th International Conference on Information Security and Cryptology. Lecture Notes in Computer Science. 5984. Seoul, Korea: Springer-Verlag. 2010. ss. 193-210. doi:10.1007/978-3-642-14423-3_14. ISBN 978-3-642-14423-3.
^ "A Survey of Single-Database Private Information Retrieval: Techniques and Applications". Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography. Springer-Verlag. 2007. ss. 393-411. doi:10.1007/978-3-540-71677-8_26. ISBN 978-3-540-71677-8.
^ ^a ^b Percy++ / PIR in C++ 7 Mart 2022 tarihinde Wayback Machine sitesinde arşivlendi. at SourceForge Kaynak hatası: Geçersiz <ref> etiketi: ":0" adı farklı içerikte birden fazla tanımlanmış (Bkz: Kaynak gösterme)
^ "Sufficient Conditions for Collision-Resistant Hashing". Proceedings of the Second Theory of Cryptography Conference. Cambridge, MA, USA: Springer-Verlag. 2005. ss. 445-456. doi:10.1007/978-3-540-30576-7_24. ISBN 978-3-540-30576-7.
^ ^a ^b "A Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol" (PDF). Yale University Technical Report YALEU/DCS/TR-1333. 2005.
^ "MuchPIR Demo". 14 Eylül 2021. 14 Ocak 2022 tarihinde kaynağından arşivlendi. Erişim tarihi: 23 Mart 2022.
^ "SealPIR". Github. 13 Ekim 2020 tarihinde kaynağından arşivlendi. Erişim tarihi: 7 Haziran 2018.
^ "Popcorn" (PDF). 21 Ağustos 2016 tarihinde kaynağından (PDF) arşivlendi. Erişim tarihi: 26 Mayıs 2016.
^ "encryptogroup/RAID-PIR". GitHub. 23 Mart 2022 tarihinde kaynağından arşivlendi. Erişim tarihi: 26 Mayıs 2016.
^ "XPIR-team/XPIR". GitHub. 8 Mart 2022 tarihinde kaynağından arşivlendi. Erişim tarihi: 26 Mayıs 2016.
^ "upPIR". uppir.poly.edu. 25 Haziran 2016 tarihinde kaynağından arşivlendi. Erişim tarihi: 26 Mayıs 2016.

Dış bağlantılar

Helger Lipmaa'nın habersiz aktarım ve GBE ile ilgili web bağlantıları 27 Eylül 2011 tarihinde Wayback Machine sitesinde arşivlendi.
Anket makaleleri de dahil olmak üzere GBE üzerinde William Gasarch'ın web sitesi 20 Ocak 2022 tarihinde Wayback Machine sitesinde arşivlendi.
Rafail Ostrovsky'nin GBE makaleleri ve anketleri içeren web sitesi 12 Mayıs 2015 tarihinde Wayback Machine sitesinde arşivlendi.

[KusOst97-1] "Replication is not needed: single database, computationally-private information retrieval". Proceedings of the 38th Annual Symposium on Foundations of Computer Science. Miami Beach, Florida, USA: IEEE Computer Society. 1997. ss. 364-373. doi:10.1109/SFCS.1997.646125. ISBN 978-0-8186-8197-4.

[2] "Computationally Private Information Retrieval with Polylogarithmic Communication". Advances in Cryptology - EUROCRYPT '99. Prague, Czech Republic: Springer-Verlag. 1999. ss. 402-414. doi:10.1007/3-540-48910-X_28. ISBN 978-3-540-48910-8.

[Lip04-3] "An Oblivious Transfer Protocol with Log-Squared Communication". Proceedings of the 8th International Conference on Information Security (ISC 2005). Lecture Notes in Computer Science. 3650. Singapore: Springer-Verlag. 2005. ss. 314-328. doi:10.1007/11556992_23. ISBN 978-3-540-31930-6.

[Lip09-4] "First CPIR Protocol with Data-Dependent Computation". Proceedings of the 12th International Conference on Information Security and Cryptology. Lecture Notes in Computer Science. 5984. Seoul, Korea: Springer-Verlag. 2010. ss. 193-210. doi:10.1007/978-3-642-14423-3_14. ISBN 978-3-642-14423-3.

[5] "A Survey of Single-Database Private Information Retrieval: Techniques and Applications". Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography. Springer-Verlag. 2007. ss. 393-411. doi:10.1007/978-3-540-71677-8_26. ISBN 978-3-540-71677-8.

[:0-6] Percy++ / PIR in C++ 7 Mart 2022 tarihinde Wayback Machine sitesinde arşivlendi. at SourceForge Kaynak hatası: Geçersiz <ref> etiketi: ":0" adı farklı içerikte birden fazla tanımlanmış (Bkz: Kaynak gösterme)

[7] "Sufficient Conditions for Collision-Resistant Hashing". Proceedings of the Second Theory of Cryptography Conference. Cambridge, MA, USA: Springer-Verlag. 2005. ss. 445-456. doi:10.1007/978-3-540-30576-7_24. ISBN 978-3-540-30576-7.

[TR1-8] "A Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol" (PDF). Yale University Technical Report YALEU/DCS/TR-1333. 2005.

[9] "MuchPIR Demo". 14 Eylül 2021. 14 Ocak 2022 tarihinde kaynağından arşivlendi. Erişim tarihi: 23 Mart 2022.

[10] "SealPIR". Github. 13 Ekim 2020 tarihinde kaynağından arşivlendi. Erişim tarihi: 7 Haziran 2018.

[11] "Popcorn" (PDF). 21 Ağustos 2016 tarihinde kaynağından (PDF) arşivlendi. Erişim tarihi: 26 Mayıs 2016.

[12] "encryptogroup/RAID-PIR". GitHub. 23 Mart 2022 tarihinde kaynağından arşivlendi. Erişim tarihi: 26 Mayıs 2016.

[13] "XPIR-team/XPIR". GitHub. 8 Mart 2022 tarihinde kaynağından arşivlendi. Erişim tarihi: 26 Mayıs 2016.

[14] "upPIR". uppir.poly.edu. 25 Haziran 2016 tarihinde kaynağından arşivlendi. Erişim tarihi: 26 Mayıs 2016.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]