निजी सूचना पुनर्प्राप्ति

क्रिप्टोग्राफी में, एक निजी सूचना पुनर्प्राप्ति (पीआईआर) प्रोटोकॉल एक प्रोटोकॉल है जो एक उपयोगकर्ता को डेटाबेस के कब्जे में एक सर्वर से एक आइटम को पुनः प्राप्त करने की अनुमति देता है बिना यह बताए कि कौन सा आइटम पुनर्प्राप्त किया गया है। पीआईआर 1-आउट-ऑफ-एन अनजान हस्तांतरण का एक कमजोर संस्करण है, जहां यह भी आवश्यक है कि उपयोगकर्ता को अन्य डेटाबेस आइटम के बारे में जानकारी नहीं मिलनी चाहिए।

सर्वर द्वारा उपयोगकर्ता को डेटाबेस की एक पूरी प्रति भेजने के लिए पीआईआर प्राप्त करने का एक तुच्छ, लेकिन बहुत अक्षम तरीका है। वास्तव में, यह एकमात्र संभव प्रोटोकॉल है (शास्त्रीय या क्वांटम क्रिप्टोग्राफी सेटिंग में ) जो उपयोगकर्ता को एकल-सर्वर सेटिंग में उनकी क्वेरी के लिए सैद्धांतिक सुरक्षा प्रदान करता है। इस समस्या को हल करने के दो तरीके हैं: सर्वर को कम्प्यूटेशनल सीमा बनाएं या मान लें कि कई गैर-सहयोगी सर्वर हैं, जिनमें से प्रत्येक में डेटाबेस की एक प्रति है।

यह समस्या 1995 में बेनी चोर, गोल्डरेइच, कुशीलेविट्ज़ और सूडान द्वारा पेश की गई थी सूचना-सैद्धांतिक सेटिंग में और 1997 में कम्प्यूटेशनल सेटिंग में कुशीलेविट्ज़ और ओस्ट्रोवस्की द्वारा। तब से, बहुत ही कुशल समाधान खोजे गए हैं। एकल डेटाबेस (कम्प्यूटेशनल रूप से निजी) पीआईआर को निरंतर (परिशोधित) संचार और के-डेटाबेस (सूचना सिद्धांत) पीआईआर के साथ प्राप्त किया जा सकता है $n^{O\left({\frac {\log \log k}{k\log k}}\right)}$ संचार।

कम्प्यूटेशनल पीआईआर में प्रगति

कम संचार जटिलता प्राप्त करने वाली पहली एकल-डेटाबेस कम्प्यूटेशनल पीआईआर योजना $n$ 1997 में कुशीलेविट्ज़ और ओस्ट्रोव्स्की द्वारा बनाया गया था और की संचार जटिलता हासिल की $n^{\epsilon }$ किसी के लिए $\epsilon$, कहाँ $n$ डेटाबेस में बिट्स की संख्या है। उनकी योजना की सुरक्षा अच्छी तरह से अध्ययन किए गए द्विघात अवशेष समस्या पर आधारित थी। 1999 में, क्रिश्चियन काचिन, सिल्वियो मिकाली और मार्कस स्टैडलर पॉली-लॉगरिदमिक संचार जटिलता हासिल की। उनके सिस्टम की सुरक्षा फी-हाइडिंग धारणा पर आधारित है। 2004 में, हेल्गर लिपमा लॉग-स्क्वायर संचार जटिलता हासिल की $O(\ell \log n+k\log ^{2}n)$, कहाँ $\ell$ तार की लंबाई है और $k$ सुरक्षा पैरामीटर है। उसकी प्रणाली की सुरक्षा दमगार्ड-जुरिक क्रिप्टोसिस्टम की तरह लंबाई-लचीली योगात्मक रूप से होमोमोर्फिक क्रिप्टोसिस्टम की शब्दार्थ सुरक्षा को कम कर देती है। 2005 में क्रेग जेंट्री और ज़ुल्फ़िकार रमजान लॉग-स्क्वायर संचार जटिलता हासिल की जो डेटाबेस के लॉग-स्क्वायर (लगातार) बिट्स को पुनः प्राप्त करती है। उनकी योजना की सुरक्षा भी फी-छिपाने की धारणा के एक प्रकार पर आधारित है। अंतत: संचार दर को नीचे लाया गया $1$ एंजेलोस कियाआस, निकोस लियोनार्डोस, गेल्गर लिप्मा, कतेरीना पावलिक, च्यांग तांग, आदि द्वारा 2015।

सभी पिछले सबलाइनियर-संचार कम्प्यूटेशनल पीआईआर प्रोटोकॉल के लिए रैखिक कम्प्यूटेशनल जटिलता की आवश्यकता होती है $\Omega (n)$ सार्वजनिक-कुंजी संचालन। 2009 में, हेल्गर लिप्मा संचार जटिलता के साथ एक कम्प्यूटेशनल पीआईआर प्रोटोकॉल तैयार किया $O(\ell \log n+k\log ^{2}n)$ और सबसे खराब स्थिति की गणना $O(n/\log n)$ सार्वजनिक-कुंजी संचालन। युवान उषा, इयाल कुशीलेविट्ज़, राफेल ओस्ट्रोवस्की और अमित सहाई द्वारा गैर-लगातार बिट्स को पुनः प्राप्त करने वाली परिशोधन तकनीकों पर विचार किया गया है। जैसा कि ओस्ट्रोव्स्की और स्कीथ द्वारा दिखाया गया है, कुशीलेविट्ज़ और ओस्ट्रोव्स्की की योजनाएँ और लिपमा होमोमोर्फिक एन्क्रिप्शन के आधार पर समान विचारों का उपयोग करें। कुशीलेविट्ज़ और ओस्ट्रोव्स्की प्रोटोकॉल गोल्डवास्सर-माइकली क्रिप्टोसिस्टम पर आधारित है, जबकि लिप्मा द्वारा प्रोटोकॉल डमगार्ड-जुरिक क्रिप्टोसिस्टम पर आधारित है।

सूचना सैद्धांतिक पीआईआर में प्रगति

अग्रिम सूचना सैद्धांतिक सुरक्षा प्राप्त करने के लिए यह मानना ​​आवश्यक है कि कई असहयोगी सर्वर हैं, जिनमें से प्रत्येक के पास डेटाबेस की एक प्रति है। इस धारणा के बिना, किसी भी सूचना-सैद्धांतिक रूप से सुरक्षित पीआईआर प्रोटोकॉल के लिए कम से कम डेटाबेस n के आकार के संचार की आवश्यकता होती है। बहु-सर्वर पीआईआर प्रोटोकॉल गैर-प्रतिक्रियाशील या दुर्भावनापूर्ण/मिलीभगत सर्वरों के प्रति सहिष्णु क्रमशः मजबूत या बीजान्टिन दोष सहिष्णुता कहलाते हैं। इन मुद्दों पर सबसे पहले बेइमेल और स्टाल (2002) ने विचार किया था। एक ℓ-सर्वर सिस्टम जो वहां काम कर सकता है जहां केवल k सर्वर प्रतिक्रिया करते हैं, ν सर्वर गलत तरीके से प्रतिक्रिया करते हैं, और जो क्लाइंट की क्वेरी को प्रकट किए बिना सर्वरों की मिलीभगत का सामना कर सकते हैं, उन्हें टी-निजी ν-बीजान्टिन मजबूत के-आउट कहा जाता है। ऑफ-ℓ पीर [डीजीएच 2012]। 2012 में, सी. डेवेट, आई. गोल्डबर्ग, और नादिया हेनिंगर|एन. हिनिंगर (डीजीएच 2012) ने एक इष्टतम रूप से मजबूत योजना का प्रस्ताव दिया जो बीजान्टिन-मजबूत है $\nu <k-t-1$ जो सैद्धांतिक अधिकतम मूल्य है। यह गोल्डबर्ग के पहले के प्रोटोकॉल पर आधारित है जो क्वेरी को छिपाने के लिए शमीर की सीक्रेट शेयरिंग का उपयोग करता है। गोल्डबर्ग ने सोर्सफोर्ज पर C++ कार्यान्वयन जारी किया है।

अन्य क्रिप्टोग्राफ़िक आदिम से संबंध

गैर-तुच्छ (अर्थात, सबलाइनियर संचार के साथ) एकल डेटाबेस कम्प्यूटेशनल रूप से निजी सूचना पुनर्प्राप्ति के लिए वन-वे फंक्शन आवश्यक हैं, लेकिन पर्याप्त नहीं हैं। वास्तव में, इस तरह के एक प्रोटोकॉल को गियोवन्नी डि क्रेसेन्ज़ो , ताल मल्किन और राफेल ओस्ट्रोव्स्की द्वारा बेखबर स्थानांतरण (नीचे देखें) के रूप में सिद्ध किया गया था।

अनजान स्थानांतरण, जिसे सममित पीआईआर भी कहा जाता है, अतिरिक्त प्रतिबंध के साथ पीआईआर है कि उपयोगकर्ता उसके अनुरोध के अतिरिक्त किसी अन्य वस्तु को नहीं सीख सकता है। इसे सममित कहा जाता है क्योंकि उपयोगकर्ता और डेटाबेस दोनों की गोपनीयता आवश्यकता होती है।

टकराव-प्रतिरोधी क्रिप्टोग्राफ़िक हैश फ़ंक्शन किसी भी एक-दौर कम्प्यूटेशनल पीआईआर योजना द्वारा निहित हैं, जैसा कि ईशाई, कुशीलेविट्ज़ और ओस्ट्रोवस्की द्वारा दिखाया गया है।

पीआईआर विविधताएं

निजी सूचना पुनर्प्राप्ति के लिए मूल प्रेरणा दो-पक्षीय प्रोटोकॉल का एक परिवार है जिसमें पार्टियों में से एक (प्रेषक) एक डेटाबेस का मालिक है, और दूसरा भाग (प्राप्तकर्ता) इसे कुछ गोपनीयता प्रतिबंधों और वारंटी के साथ क्वेरी करना चाहता है। इसलिए, प्रोटोकॉल के परिणामस्वरूप, यदि रिसीवर डेटाबेस में i-वें मान चाहता है तो उसे i-वें प्रविष्टि सीखनी चाहिए, लेकिन प्रेषक को i के बारे में कुछ नहीं सीखना चाहिए। एक सामान्य पीआईआर प्रोटोकॉल में, एक कम्प्यूटेशनल रूप से असीमित प्रेषक मेरे बारे में कुछ नहीं सीख सकता है इसलिए गोपनीयता सैद्धांतिक रूप से संरक्षित है। चूंकि पीआईआर समस्या पेश की गई थी, इसके समाधान के लिए विभिन्न दृष्टिकोण अपनाए गए हैं और कुछ बदलाव प्रस्तावित किए गए हैं।

एक सीपीआईआर (कम्प्यूटेशनली प्राइवेट इंफॉर्मेशन रिट्रीवल) प्रोटोकॉल एक पीआईआर प्रोटोकॉल के समान है: रिसीवर प्रेषक के डेटाबेस से उसके द्वारा चुने गए एक तत्व को पुनः प्राप्त करता है, जिससे कि प्रेषक को यह पता न चले कि किस तत्व को स्थानांतरित किया गया था। अंतर केवल इतना है कि बहुपद से बंधे प्रेषक के खिलाफ गोपनीयता की रक्षा की जाती है।

एक सीएसपीआईआर (कम्प्यूटेशनली सममित निजी सूचना पुनर्प्राप्ति) प्रोटोकॉल का उपयोग उसी तरह के परिदृश्य में किया जाता है जिसमें सीपीआईआर प्रोटोकॉल का उपयोग किया जाता है। यदि प्रेषक एक डेटाबेस का मालिक है, और रिसीवर इस डेटाबेस में i-वें मान प्राप्त करना चाहता है, तो एसपीआईआर प्रोटोकॉल के निष्पादन के अंत में, रिसीवर को i-वें के अतिरिक्त डेटाबेस में मानों के बारे में कुछ नहीं सीखना चाहिए। एक।

पीआईआर कार्यान्वयन

साहित्य में कई कम्प्यूटेशनल पीआईआर और सूचना सिद्धांत पीआईआर योजनाओं को लागू किया गया है। यहाँ एक अधूरी सूची है:

• मुचपीर पोस्टग्रेज सी/सी++ एक्सटेंशन [गिटहब, 2021] के रूप में एक सीपीआईआर कार्यान्वयन है।
• सीलपीर एक तेज सीपीआईआर कार्यान्वयन [एसीएलएस 2018] है।
• पॉपकॉर्न मीडिया के लिए तैयार किया गया एक पीआईआर कार्यान्वयन है [जीसीएमएसएडब्ल्यू 2016]।
• पर्सी++ में [एजी 2007, डीजीएच 2012, सीजीकेएस 1998, गोल्डबर्ग 2007, एचओजी 2011, एलजी 2015] का कार्यान्वयन शामिल है।
• रेड-पीर [डीएचएस 2014] की आईटीपीआईआर योजना का कार्यान्वयन है।
• एक्सपीआईआर एक तेज सीपीआईआर कार्यान्वयन [एबीएफके 2014] है।
• ऊपरपीर एक आईटीपीआईआर कार्यान्वयन [कैप्पोस 2013] है।

यह भी देखें

• के-गुमनामी
• स्थानीय रूप से डिकोडेबल कोड

संदर्भ

• A. Beimel, Y. Ishai, E. Kushilevitz, and J.-F. Raymond. Breaking the $O(n^{1/(2k-1)})$ barrier for information-theoretic private information retrieval. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, Canada, pages 261–270, 2002.
• A. Beimel and Y. Stahl, Robust information-theoretic private information retrieval, in Proceedings of the 3rd International Conference on Security in Communication Networks (SCN'02), pp. 326–341, 2003. Cite is from DGH 2012, op. cit.
• [DGH 2012] Casey Devet, Ian Goldberg, and Nadia Heninger, Optimally Robust Private Information Retrieval, 21st USENIX Security Symposium, August 2012.
• [AG 2007] C. Aguilar-Melchor and P. Gaborit. A lattice-based computationally-efficient private information retrieval protocol, Western European Workshop on Research in Cryptology (WEWoRC), 2007.
• [CGKS 1998] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, Private information retrieval, Journal of the ACM, 45(6):965–981, 1998.
• [Goldberg 2007] I. Goldberg, Improving the robustness of private information retrieval, IEEE Symposium on Security and Privacy (S&P), 2007.
• [HOG 2011] R. Henry, F. Olumofin, and I. Goldberg, Practical PIR for electronic commerce, ACM Conference on Computer and Communications Security (CCS), 2011.
• [LG 2015] W. Lueks and 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, and T. Schneider, RAID-PIR: Practical multi-server PIR, In Cloud computing security workshop (CCSW), 2014.
• [ABFK 2014] C. Aguilar-Melchor, J. Barrier, L. Fousse, and M.-O. Killijian, "XPIR: Private Information Retrieval for Everyone", Cryptology ePrint Archive, Report 2014/1025, 2014.
• [GCMSAW 2016] T. Gupta, N. Crooks, W. Mulhern, S. Setty, L. Alvisi, and M. Walfish, [1] Scalable and private media consumption with Popcorn. USENIX NSDI, March 2016.
• [Cappos 2013] J. Cappos, Avoiding theoretical optimality to efficiently and privately retrieve security updates, International Conference on Financial Cryptography and Data Security (FC), 2013.
• Sergey Yekhanin. New locally decodable codes and private information retrieval schemes, ECCC TR06-127, 2006.
• [ACLS 2018] S. Angel, H. Chen, K. Laine, S. Setty, PIR with compressed queries and amortized query processing, IEEE Symposium on Security and Privacy (S&P), 2018.

बाहरी संबंध

• Helger Lipmaa's web links on oblivious transfer and PIR
• William Gasarch's website on PIR including survey articles
• Rafail Ostrovsky's website contaiting PIR articles and surveys