Získávání soukromých informací - Private information retrieval

v kryptografie, a vyhledávání soukromých informací (PIR) Protokol je protokol, který umožňuje uživateli načíst položku ze serveru, který vlastní databáze bez odhalení, která položka je načtena. PIR je slabší verze 1-out-of-n lhostejný přenos, kde je také požadováno, aby uživatel nedostával informace o dalších položkách databáze.

Jeden triviální, ale velmi neefektivní způsob, jak dosáhnout PIR, je, aby server odeslal uživateli celou kopii databáze. Ve skutečnosti je to jediný možný protokol (v klasickém nebo kvantová nastavení[1]), který dává uživateli informační teoretické soukromí pro jejich dotaz v nastavení jednoho serveru.[2] Tento problém lze vyřešit dvěma způsoby: provést server výpočetně omezený nebo předpokládejme, že existuje více nespolupracujících serverů, z nichž každý má kopii databáze.

Problém zavedli v roce 1995 Chor, Goldreich, Kushilevitz a Súdán[2] v informačně-teoretickém prostředí a v roce 1997 Kushilevitzem a Ostrovským ve výpočetním prostředí.[3] Od té doby byla objevena velmi účinná řešení. Jednotné databáze (výpočetně soukromé) PIR lze dosáhnout s konstantní (amortizovanou) komunikací a k-databáze (informační teoretická) PIR lze provést s sdělení.

Pokroky ve výpočetním PIR

První jedno-databázové výpočetní schéma PIR pro dosažení komunikační složitosti menší než byla vytvořena v roce 1997 Kushilevitzem a Ostrovským [3] a dosažená komunikační složitost pro všechny , kde je počet bitů v databázi. Zabezpečení jejich schématu bylo založeno na dobře prostudovaném Kvadratický problém reziduaity. V roce 1999 Christian Cachin, Silvio Micali a Markus Stadler[4] dosáhl poly-logaritmické komunikační složitosti. Zabezpečení jejich systému je založeno na Předpoklad skrývání Phi. V roce 2004 Helger Lipmaa [5] dosáhl složitosti log-kvadrát komunikace , kde je délka řetězců a je parametr zabezpečení. Zabezpečení jeho systému se snižuje na sémantická bezpečnost délkově flexibilního aditivně homomorfního kryptosystému, jako je Kryptosystém Damgård – Jurik. V roce 2005 Craig Gentry a Zulfikar Ramzan [6] dosažená log-kvadrát komunikační složitost, která načte log-square (po sobě jdoucí) bity databáze. Zabezpečení jejich schématu je také založeno na variantě předpokladu skrývání Phi. Rychlost komunikace byla nakonec snížena na podle Aggelos Kiayias, Nikos Leonardos, Helger Lipmaa, Kateryna Pavlyk, Qiang Tang v roce 2015 [7].

Všechny předchozí výpočetní protokoly PIR sublineární komunikace vyžadovaly lineární výpočetní složitost operace veřejného klíče. V roce 2009, Helger Lipmaa [8] navrhl výpočetní PIR protokol se složitostí komunikace a nejhorší výpočet operace veřejného klíče. Amortizační techniky, které načítají nenasledující bity, byly považovány za Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovský a Amit Sahai.[9]

Jak ukazují Ostrovsky a Skeith,[10] schémata Kushilevitze a Ostrovského [3] a Lipmaa [5] použít podobné nápady založené na homomorfní šifrování. Protokol Kushilevitz a Ostrovsky je založen na Kryptosystém Goldwasser – Micali zatímco protokol Lipmaa je založen na Kryptosystém Damgård – Jurik.

Pokroky v informační teoretické PIR

Dosažení informační teoretické bezpečnosti vyžaduje předpoklad, že existuje několik nespolupracujících serverů, z nichž každý má kopii databáze. Bez tohoto předpokladu jakýkoli informační teoreticky zabezpečený protokol PIR vyžaduje takové množství komunikace, které je alespoň velikost databáze n. Jsou volány multi-serverové PIR protokoly tolerantní k nereagujícím nebo škodlivým / tajným serverům robustní nebo Byzantský robustní resp. O těchto otázkách poprvé uvažovali Beimel a Stahl (2002). Systém server-serveru, který může fungovat pouze tam, kde k serverů odpovídá, ν serverů reaguje nesprávně a které vydrží až t dohodnuté servery bez odhalení dotazu klienta se nazývá „t- soukromý ν-byzantský robustní k-out-of-ℓ PIR "[DGH 2012]. V roce 2012 C. Devet, I. Goldberg a N. Heninger (DGH 2012) navrhla optimálně robustní schéma, které je byzantské robustní což je teoretická maximální hodnota. Je založen na dřívějším protokolu Goldbergu, který používá Shamirovo tajné sdílení skrýt dotaz. Goldberg vydal a C ++ implementace dne Sourceforge.[11]

Vztah k jiným kryptografickým primitivům

Jednosměrné funkce jsou nezbytné, ale není o nich známo, že jsou dostatečné pro netriviální (tj. sublimní komunikaci) výpočetně soukromé získávání informací z jedné databáze. Ve skutečnosti takový protokol prokázal Giovanni Di Crescenzo, Tal Malkin a Rafail Ostrovský znamenat lhostejný přenos (viz níže).[12]

Nezapomenutelný převod, nazývaný také symetrický PIR, je PIR s dalším omezením, že se uživatel nemusí naučit jinou položku, než požadovala. Nazývá se symetrický, protože uživatel i databáze mají požadavek na ochranu osobních údajů.

Odolný proti kolizi kryptografické hashovací funkce jsou implikovány jakýmkoli jednokolovým výpočetním schématem PIR, jak ukazují Ishai, Kushilevitz a Ostrovsky.[13]

Varianty PIR

Základní motivací pro získávání soukromých informací je skupina protokolů dvou stran, ve kterých jedna ze stran (dále jen odesílatel) vlastní databázi a druhou část ( přijímač) chce na něj požádat s určitými omezeními a zárukami ochrany osobních údajů. Takže v důsledku protokolu, pokud přijímač chce i-tý hodnotu v databázi se musí naučit i-tý vstup, ale odesílatel musí se o tom nic naučit i. V obecném protokolu PIR je výpočetně neomezené odesílatel se o tom nic nedozví i takže soukromí je teoreticky zachováno. Od vzniku problému PIR byly sledovány různé přístupy k jeho řešení a byly navrženy některé varianty.

Protokol CPIR (Computationally Private Information Retrieval) je podobný protokolu PIR: přijímač načte jím vybraný prvek z databáze odesílatele, takže odesílatel nezíská žádné informace o tom, který prvek byl přenesen.[8] Jediným rozdílem je, že soukromí je chráněno proti polynomiálně ohraničenému odesílateli.[14]

Protokol CSPIR (Computationally Symmetric Private Information Retrieval) se používá v podobném scénáři, ve kterém se používá protokol CPIR. Pokud odesílatel vlastní databázi a přijímač chce získat i-tý hodnota v této databázi, na konci provádění protokolu SPIR, přijímač se neměl o hodnotách v databázi dozvědět nic jiného než i-tý jeden.[14]

PIR implementace

V literatuře byla implementována četná výpočetní PIR a informační teoretická PIR schémata. Zde je neúplný seznam:

  • Percy ++[11] zahrnuje implementace [AG 2007, DGH 2012, CGKS 1998, Goldberg 2007, HOG 2011, LG 2015].
  • Popcorn[15] je implementace PIR šitá na míru pro média [GCMSAW 2016].
  • RAID-PIR[16] je implementací schématu ITPIR ze dne [DHS 2014].
  • SealPIR[17] je rychlá implementace CPIR [ACLS 2018].
  • upPIR[18] je implementace ITPIR [Cappos 2013].
  • XPIR[19] je rychlá implementace CPIR [ABFK 2014].

Poznámky

  1. ^ Baumeler, Ämin; Broadbent, Anne (17. dubna 2014). "Kvantové načítání soukromých informací má složitost lineární komunikace". Journal of Cryptology. 28: 161–175. arXiv:1304.5490. doi:10.1007 / s00145-014-9180-2.
  2. ^ A b Chor, Benny; Kushilevitz, Eyal; Goldreich, Oded; Súdán, Madhu (1. listopadu 1998). „Získávání soukromých informací“ (PDF). Deník ACM. 45 (6): 965–981. CiteSeerX  10.1.1.51.3663. doi:10.1145/293347.293350.
  3. ^ A b C Kushilevitz, Eyal; Ostrovský, Rafail (1997). Msgstr "Replikace není nutná: jedna databáze, výpočetně soukromé vyhledávání informací". Proceedings of the 38th Annual Symposium on Foundations of Computer Science. Miami Beach, Florida, USA: IEEE Computer Society. 364–373. CiteSeerX  10.1.1.56.2667. doi:10.1109 / SFCS.1997.646125. ISBN  978-0-8186-8197-4.
  4. ^ Cachin, Christian; Micali, Silvio; Stadler, Markus (1999). "Výpočetně soukromé získávání informací s polylogaritmickou komunikací". Pokroky v kryptologii - EUROCRYPT '99. Praha, Česká republika: Springer-Verlag. 402–414. doi:10.1007 / 3-540-48910-X_28. ISBN  978-3-540-48910-8.
  5. ^ A b Lipmaa, Helger (2005). „Oblivious Transfer Protocol with Log-Squared Communication“. Sborník příspěvků z 8. mezinárodní konference o informační bezpečnosti (ISC 2005). Přednášky z informatiky. 3650. Singapur: Springer-Verlag. 314–328. CiteSeerX  10.1.1.73.8768. doi:10.1007/11556992_23. ISBN  978-3-540-31930-6.
  6. ^ Gentry, Craig; Ramzan, Zulfikar (2005). "Načítání soukromých informací z jedné databáze s konstantní rychlostí komunikace". ICALP. LNCS. 3580. Springer. str. 803–815. CiteSeerX  10.1.1.113.6572. doi:10.1007/11523468_65.
  7. ^ Kiayias, Aggelos; Leonardos, Nikos; Lipmaa, Helger; Pavlyk, Kateryna; Tang, Qiang (2015). "Optimální rychlost získávání soukromých informací z homomorfního šifrování". Sborník o technologiích zvyšujících ochranu soukromí 2015. 2015. DE GRUYTER. str. 222–243. doi:10.1515 / popets-2015-0016.
  8. ^ A b Lipmaa, Helger (2010). "První protokol CPIR s výpočtem závislým na datech". Sborník z 12. mezinárodní konference o informační bezpečnosti a kryptologii. Přednášky z informatiky. 5984. Soul, Korea: Springer-Verlag. 193–210. CiteSeerX  10.1.1.215.7768. doi:10.1007/978-3-642-14423-3_14. ISBN  978-3-642-14423-3.
  9. ^ Ishai, Yuval; Kushilevitz, Eyal; Ostrovský, Rafail; Sahai, Amit (2004). "Dávkové kódy a jejich aplikace" (PDF). STOC'04. ACM. 262–271. doi:10.1145/1007352.1007396. Citováno 2015-10-23.
  10. ^ Ostrovský, Rafail; Skeith III; William E. (2007). „Průzkum získávání soukromých informací z jedné databáze: techniky a aplikace“. Sborník příspěvků z 10. mezinárodní konference o praxi a teorii v kryptografii veřejným klíčem. Springer-Verlag. 393–411. doi:10.1007/978-3-540-71677-8_26. ISBN  978-3-540-71677-8.
  11. ^ A b Percy ++ / PIR v C ++ na SourceForge
  12. ^ Di Crescenzo, Giovanni; Malkin, Tal; Ostrovsky, Rafail (2000). Msgstr "Načítání soukromých informací z jedné databáze znamená nepředvídatelný přenos". Eurokrypt 2000. LNCS. 1807. Springer. str. 122–138. doi:10.1007/3-540-45539-6_10.
  13. ^ Ishai, Yuval; Kushilevitz, Eyal; Ostrovsky, Rafail (2005). "Dostatečné podmínky pro hašování odolné proti kolizi". Sborník druhé konference o teorii kryptografie. Cambridge, MA, USA: Springer-Verlag. str. 445–456. doi:10.1007/978-3-540-30576-7_24. ISBN  978-3-540-30576-7.
  14. ^ A b Saint-Jean, Felipe (2005). „Implementace Java pro výpočetní symetrický protokol pro načítání soukromých informací (CSPIR) s jednou databází“ (PDF). Technická zpráva Yale University YALEU / DCS / TR-1333.
  15. ^ "Popcorn" (PDF). Archivovány od originál (PDF) dne 2016-08-21. Citováno 2016-05-26.
  16. ^ „encryptogroup / RAID-PIR“. GitHub. Citováno 2016-05-26.
  17. ^ „SealPIR“. Github. Citováno 2018-06-07.
  18. ^ „upPIR“. uppir.poly.edu. Archivovány od originál dne 2016-06-25. Citováno 2016-05-26.
  19. ^ „XPIR-team / XPIR“. GitHub. Citováno 2016-05-26.

Viz také

Reference

  • A. Beimel, Y. Ishai, E. Kushilevitz a J.-F. Raymond. Prolomení bariéra pro získávání soukromých informací z teoreticko-informačního hlediska. Sborník 43. výročního sympozia IEEE o základech informatiky, Vancouver, Kanada, strany 261-270, 2002.
  • A. Beimel a Y. Stahl, Robustní získávání soukromých informací z teoreticko-teoretického hlediska, Ve sborníku z 3. mezinárodní konference o bezpečnosti v komunikačních sítích (SCN'02), s. 326–341, 2003. Citace je z DGH 2012, op. cit.
  • [DGH 2012] Casey Devet, Ian Goldberg, a Nadia Heningerová, Optimálně robustní načítání soukromých informací, 21. USENIX Security Symposium, srpen 2012.
  • [AG 2007] C. Aguilar-Melchor a P. Gaborit. Výpočtově efektivní protokol pro načítání soukromých informací založený na mřížce, Západoevropský seminář o výzkumu v kryptologii (WEWoRC), 2007.
  • [CGKS 1998] B. Chor, O. Goldreich, E. Kushilevitz a M. Súdán, Získávání soukromých informací, Journal of the ACM, 45 (6): 965–981, 1998.
  • [Goldberg 2007] I. Goldberg, Zlepšení robustnosti vyhledávání soukromých informací, IEEE Symposium on Security and Privacy (S&P), 2007.
  • [HOG 2011] R. Henry, F. Olumofin a I. Goldberg, Praktický PIR pro elektronický obchod, ACM Conference on Computer and Communications Security (CCS), 2011.
  • [LG 2015] W. Lueks a I. Goldberg, Sublineární škálování pro načítání soukromých informací z více klientů, Mezinárodní konference o finanční kryptografii a zabezpečení dat (FC), 2015.
  • [DHS 2014] D. Demmler, A. Herzberg a T. Schneider, RAID-PIR: Praktický multi-serverový PIR, In Cloud computing security workshop (CCSW), 2014.
  • [ABFK 2014] C. Aguilar-Melchor, J. Barrier, L. Fousse a M.-O. Killijian, „XPIR: Získávání soukromých informací pro každého“, Archiv kryptologie ePrint, Zpráva 2014/1025, 2014.
  • [GCMSAW 2016] T. Gupta, N. Crooks, W. Mulhern, S. Setty, L. Alvisi a M. Walfish, [1] Škálovatelné a soukromé spotřeba médií s popcornem. USENIX NSDI, březen 2016.
  • [Cappos 2013] J. Cappos, Vyhýbání se teoretické optimitě pro efektivní a soukromé načítání aktualizací zabezpečení, Mezinárodní konference o finanční kryptografii a zabezpečení dat (FC), 2013.
  • Sergey Yekhanin. Nové lokálně dekódovatelné kódy a schémata vyhledávání soukromých informací, ECCC  TR06-127, 2006.
  • [ACLS 2018] S. Angel, H. Chen, K. Laine, S. Setty, PIR s komprimovanými dotazy a amortizovaným zpracováním dotazů, IEEE Symposium on Security and Privacy (S&P), 2018.

externí odkazy