Odzyskiwanie informacji prywatnych

W kryptografii protokół wyszukiwania informacji prywatnych (PIR) to protokół, który umożliwia użytkownikowi odzyskanie elementu z serwera posiadającego bazę danych bez ujawniania, który element jest pobierany. PIR jest słabszą wersją transferu 1 z n , gdzie wymagane jest również, aby użytkownik nie otrzymywał informacji o innych pozycjach bazy danych.

Jednym z trywialnych, ale bardzo nieefektywnych sposobów osiągnięcia PIR jest wysłanie przez serwer do użytkownika całej kopii bazy danych. W rzeczywistości jest to jedyny możliwy protokół (w ustawieniu klasycznym lub kwantowym ) , który zapewnia użytkownikowi teoretyczną prywatność w przypadku jego zapytań w ustawieniu jednego serwera. Istnieją dwa sposoby rozwiązania tego problemu: ogranicz serwer obliczeniowo lub załóż, że istnieje wiele niewspółpracujących serwerów, z których każdy ma kopię bazy danych.

Problem został wprowadzony w 1995 roku przez Chora, Goldreicha, Kushilevitza i Sudana w kontekście teorii informacji oraz w 1997 roku przez Kushilevitza i Ostrovsky'ego w kontekście obliczeniowym. Od tego czasu odkryto bardzo skuteczne rozwiązania. Pojedynczą bazę danych (prywatną obliczeniowo) PIR można osiągnąć przy stałej (amortyzowanej) komunikacji, a k-bazy danych (teoretycznie informacji) PIR można wykonać za pomocą n O ( $n ^ {O \ lewa({\frac {\log \log k}{k\log k}}\right)}}$ komunikacja.

Postępy w obliczeniowym PIR

Pierwszy schemat obliczeniowy PIR z pojedynczą bazą danych, który pozwolił na osiągnięcie złożoności komunikacji mniejszej niż, $displaystyle \ epsilon }$ $stworzony$ ${\ epsilon}}$ $^$ \ displaystyle , gdzie $.$ liczbą bitów w bazie danych Bezpieczeństwo ich schematu opierało się na dobrze zbadanym problemie resztowości kwadratowej . W 1999 r. Christian Cachin i Silvio Micali i Markus Stadler osiągnęli polilogarytmiczną złożoność komunikacji. Bezpieczeństwo ich systemu opiera się na założeniu ukrywania Phi . W 2004 roku Helger Lipmaa osiągnął $)}$ kwadratowy złożoności komunikacji , ℓ $displaystyle \ ell}$ $n$ to długość ciągów i ${\ displaystyle k}$ jest parametrem bezpieczeństwa. Bezpieczeństwo jego systemu sprowadza się do bezpieczeństwa semantycznego elastycznego pod względem długości addytywnie homomorficznego kryptosystemu, takiego jak kryptosystem Damgårda – Jurika . W 2005 roku Craig Gentry i Zulfikar Ramzan osiągnęli złożoność komunikacji logarytmicznej, która pozwala na pobieranie logarytmicznych (kolejnych) bitów bazy danych. Bezpieczeństwo ich planu również opiera się na wariancie założenia ukrywania Phi. $.$ komunikacji została ostatecznie obniżona do Aggelos Kiayias , Nikos Leonardos, Helger Lipmaa, Kateryna Pavlyk, Qiang Tang w 2015 roku

$kluczu$ komunikacją podliniową wymagał liniowej złożoności obliczeniowej publicznym. $_$ protokół _ obliczenie przypadku ${\ Displaystyle O (n / \ log n)}$ operacje na kluczu publicznym. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky i Amit Sahai rozważali techniki amortyzacji polegające na odzyskiwaniu nie następujących po sobie bitów .

Jak pokazali Ostrovsky i Skeith, schematy Kushilevitza, Ostrovsky’ego i Lipmy wykorzystują podobne pomysły oparte na szyfrowaniu homomorficznym . Protokół Kushilevitza i Ostrovsky’ego opiera się na kryptosystemie Goldwassera – Micali , natomiast protokół Lipmaa opiera się na kryptosystemie Damgård – Jurik .

Postępy w teorii informacji PIR

Osiągnięcie bezpieczeństwa teoretycznego informacji wymaga założenia, że istnieje wiele niewspółpracujących serwerów, z których każdy posiada kopię bazy danych. Bez tego założenia każdy teoretycznie bezpieczny protokół PIR wymaga ilości komunikacji co najmniej równej rozmiarowi bazy danych n . Wieloserwerowe protokoły PIR tolerujące niereagujące lub złośliwe/zmawiające się serwery nazywane są solidnymi lub bizantyjskimi solidnymi . Zagadnienia te po raz pierwszy zajęli się Beimel i Stahl (2002). System ℓ-serwerowy, który może działać tam, gdzie tylko k serwerów odpowiada, ν serwerów odpowiada niepoprawnie i który może wytrzymać do t serwerów w zmowie bez ujawniania zapytania klienta, nazywany jest „ t -prywatnym ν-bizantyjskim solidnym k -out-of-ℓ PIR” [DGH 2012]. W 2012 roku C. Devet, I. Goldberg i N. Heninger (DGH 2012) zaproponowali optymalnie solidny schemat, który jest odporny na warunki bizantyjskie. ${\ displaystyle \ nu <kt-1}$ co jest teoretyczną wartością maksymalną. Opiera się na wcześniejszym protokole Goldberga, który wykorzystuje funkcję tajnego udostępniania Shamira w celu ukrycia zapytania. Goldberg opublikował C++ na SourceForge .

Związek z innymi prymitywami kryptograficznymi

Funkcje jednokierunkowe są konieczne, ale nie są wystarczające do nietrywialnego (tj. przy komunikacji podliniowej) wyszukiwania prywatnych informacji obliczeniowo z jednej bazy danych. W rzeczywistości Giovanni Di Crescenzo, Tal Malkin i Rafail Ostrovsky udowodnili, że taki protokół sugeruje nieświadomy transfer (patrz poniżej).

Transfer nieświadomy , zwany także symetrycznym PIR, to PIR z dodatkowym zastrzeżeniem, że użytkownik nie może nauczyć się żadnego innego elementu niż ten, o który prosił. Nazywa się to symetrycznym, ponieważ zarówno użytkownik, jak i baza danych mają wymagania dotyczące prywatności.

Odporne na kolizje kryptograficzne funkcje skrótu są implikowane przez dowolny jednookrągły schemat obliczeniowy PIR, jak pokazali Ishai, Kushilevitz i Ostrovsky.

Różnice w PIR

Podstawową motywacją do wyszukiwania informacji prywatnych jest rodzina protokołów dwustronnych, w których jedna ze stron (nadawca ) jest właścicielem bazy danych, a druga część (odbiorca ) chce ją przeszukać z pewnymi ograniczeniami i gwarancjami prywatności. Zatem zgodnie z protokołem, jeśli odbiorca chce i-tej wartości w bazie danych, musi poznać i-ty wpis, ale nadawca nie może dowiedzieć się niczego o i . W ogólnym protokole PIR nieograniczony obliczeniowo nadawca nie może się niczego dowiedzieć więc teoretycznie prywatność jest zachowana. Od czasu postawienia problemu PIR szukano różnych podejść do jego rozwiązania i zaproponowano pewne zmiany.

Protokół CPIR (Computational Private Information Retrieval) jest podobny do protokołu PIR: odbiorca pobiera wybrany przez siebie element z bazy nadawcy, dzięki czemu nadawca nie ma wiedzy o tym, który element został przesłany. Jedyna różnica polega na tym, że prywatność jest chroniona przed nadawcą ograniczonym wielomianowo.

Protokół CSPIR (Computational Symmetric Private Information Retrieval) jest używany w podobnym scenariuszu, w którym używany jest protokół CPIR. Jeśli nadawca jest właścicielem bazy danych, a odbiorca chce uzyskać i-tą wartość w tej bazie danych, na koniec wykonywania protokołu SPIR odbiorca nie powinien dowiedzieć się niczego o wartościach w bazie danych innych niż i -ta jeden.

Wdrożenia PIR

W literaturze wdrożono wiele obliczeniowych schematów PIR i teoretycznych informacji PIR. Oto niekompletna lista:

MuchPIR to implementacja CPIR jako rozszerzenie Postgres C/C++ [GitHub, 2021].
SealPIR to szybka implementacja CPIR [ACLS 2018].
Popcorn to implementacja PIR dostosowana do mediów [GCMSAW 2016].
Percy++ zawiera implementacje [AG 2007, DGH 2012, CGKS 1998, Goldberg 2007, HOG 2011, LG 2015].
RAID-PIR jest implementacją schematu ITPIR z [DHS 2014].
XPIR to szybka implementacja CPIR [ABFK 2014].
upPIR jest implementacją ITPIR [Cappos 2013].

Notatki

Zobacz też

A. Beimel, Y. Ishai, E. Kushilevitz i J.-F. Raymond. Przełamanie bariery w zakresie teoretycznego wyszukiwania informacji prywatnych. ${\ displaystyle O (n ^ {1 / (2k-1)})}$ Materiały z 43. dorocznego sympozjum IEEE na temat podstaw informatyki , Vancouver, Kanada, strony 261–270, 2002.
A. Beimel i Y. Stahl, Robust Information-theoretic private Information Retrieval , w: Proceedings of the 3rd International Conference on Security in Communication Networks (SCN'02), s. 326–341, 2003. Cytat pochodzi z DGH 2012, op. cyt.
[DGH 2012] Casey Devet, Ian Goldberg i Nadia Heninger , Optimally Robust Private Information Retrieval , 21. sympozjum dotyczące bezpieczeństwa USENIX, sierpień 2012.
[AG 2007] C. Aguilar-Melchor i P. Gaborit. Oparta na kratach, wydajna obliczeniowo protokół wyszukiwania prywatnych informacji , Zachodnioeuropejskie warsztaty dotyczące badań w kryptologii (WEWoRC), 2007.
[CGKS 1998] B. Chor, O. Goldreich, E. Kushilevitz i M. Sudan, Private Information Retrieval , Journal of the ACM, 45(6):965–981, 1998.
[Goldberg 2007] I. Goldberg, Poprawa solidności wyszukiwania informacji prywatnych , Sympozjum IEEE na temat bezpieczeństwa i prywatności (S&P), 2007.
[HOG 2011] R. Henry, F. Olumofin i I. Goldberg, Praktyczne PIR dla handlu elektronicznego , Konferencja ACM na temat bezpieczeństwa komputerów i komunikacji (CCS), 2011.
[LG 2015] W. Lueks i I. Goldberg, Sublinear scaling for multi-client private Information Retrieval , International Conference on Financial Cryptography and Data Security (FC), 2015.
[DHS 2014] D. Demmler, A. Herzberg i T. Schneider, RAID-PIR: Praktyczny wieloserwerowy PIR , In Cloud Computing Security Workshop (CCSW), 2014.
[ABFK 2014] C. Aguilar-Melchor, J. Barrier, L. Fousse i M.-O. Killijian, „XPIR: wyszukiwanie informacji prywatnych dla każdego”, Cryptology ePrint Archive, raport 2014/1025, 2014.
[GCMSAW 2016] T. Gupta, N. Crooks, W. Mulhern, S. Setty, L. Alvisi i M. Walfish, [1] Skalowalna i prywatna konsumpcja mediów za pomocą Popcornu. USENIX NSDI, marzec 2016 r.
[Cappos 2013] J. Cappos, Unikanie teoretycznej optymalności w celu wydajnego i prywatnego pobierania aktualizacji zabezpieczeń , Międzynarodowa Konferencja na temat kryptografii finansowej i bezpieczeństwa danych (FC), 2013.
Siergiej Jechanin. Nowe lokalnie dekodowane kody i schematy wyszukiwania prywatnych informacji, ECCC TR06-127 , 2006.
[ACLS 2018] S. Angel, H. Chen, K. Laine, S. Setty, PIR ze skompresowanymi zapytaniami i amortyzowanym przetwarzaniem zapytań , Sympozjum IEEE na temat bezpieczeństwa i prywatności (S&P), 2018.

Linki zewnętrzne