عرض مصدر استعادة المعلومات الخاصة

{{يتيمة|تاريخ=مايو_2011}}

'''استعادة المعلومات الخاصة PIR''' في [[علم التعمية]] يسمح [[بروتوكول (توضيح)|بروتوكول]] للمستخدم باستعادة نص من خادم ينتمي إلي [[قاعدة بيانات]] بدون الكشف عن النص الذي تتم استعادته. يعتبر بروتوكول استعادة المعلومات الخاصة PIR نسخة أضعف من النقل الواضح 1-من- عدد لانهائي حيث يكون من الضروري أيضاً ألا يحصل المستخدم علي معلومات عن نصوص من قواعد بيانات أخرى.
 
من إحدي الطرق الضعيفة والغير فعالة لاستعادة المعلومات الخاصة PIR يقوم الخادم بإرسال نسخة كاملة من قاعدة البيانات إلي المستخدم. في الواقع, فإن هذا هو البروتوكول الممكن الوحيد الذي يُتيح للمستخدم خصوصية المعلومات النظرية في سياق [[خادم (توضيح)|خادم]] واحد. هناك طريقتين لمعالجة هذه المشكلة: الأولي هي جعل الخادم مقيد حسابيا، والأخرى هي افتراض أن هناك خوادم متعددة غير متعاونة/مترابطة يمتلك كل منها نسخة من قاعدة البيانات.
 
تم طرح هذه المشكلة في عام 1995 بواسطة [[كور]] وجولدريتش وكاشيلفيتز وسودان <ref>Benny Chor, Eyal Kushilevitz, [[Oded Goldreich]]، [[مادو سودان]]: [https://web.archive.org/web/20040327173643/http://www.cs.technion.ac.il/~benny/PIR.pdf Private Information Retrieval]. J. ACM 45(6): 965–981 (1998) {{Webarchive|url=https://web.archive.org/web/20200911100513/https://web.archive.org/web/20040327173643/http://www.cs.technion.ac.il/~benny/PIR.pdf |date=11 سبتمبر 2020}}</ref> في سياق المعلومات النظرية وفي عام 1997 بواسطة كاشيلفيتز وأوستروفسكي في السياق الحاسوبي.<ref name="KusOst97">Eyal Kushilevitz, [[Rafail Ostrovsky]]: Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval. FOCS 1997: 364–373 [http://web.cs.ucla.edu/~rafail/PUBLIC/34.pdf (PDF)] {{Webarchive|url=https://web.archive.org/web/20131126075502/http://www.cs.ucla.edu/~rafail/PUBLIC/34.pdf |date=26 نوفمبر 2013}}</ref> منذ ذلك الحين تم اكتشاف حلول فعالة للغاية. يمكن تخصيص قاعدة بيانات واحدة (خاصة حاسوبيا) لاستعادة المعلومات الخاصة PIR مع اتصال ثابت ([[مستهلك]]) , وكذلك يمكن إنشاء قاعدة بيانات k-database (معلوماتية نظرية) لاستعادة المعلومات الخاصة PIR باستخدام الاتصال <math>n^{O(\frac{\log \log k}{k \log k})}</math>.

== تطورات بروتوكول استعادة المعلومات الخاصة PIR الحاسوبية ==
أول [[قاعدة بيانات]] حاسوبية مفرد لخطة استعادة المعلومات الخاصة لتحقيق تعقد اتصالات أقل من n قد ظهر عام 1997 بواسطة كاشيلفيتز وأوستروفسكي<ref name="KusOst97"/> وقد حققت تعقيد اتصالات <math>n^\epsilon</math> لأي <math>\epsilon</math>, ,حيث <math>n</math> عدد البيتات في قاعدة البيانات. أمان خطتهم كان يعتمد علي نظرية مشكلة البقايا التربيعية. في عام 1999 قام كل من [[كريستيلن كاشين]] و[[سيلفيو ميكالي]] و[[ماركيوس ستادلر]][http://www.zurich.ibm.com/~cca/papers/cpir.pdf] بوضع تعقيد اتصال متعدد [[لوغاريتم|اللوغاريتمية]]. يعتمد أمان نظامهم علي أساس فرضية إخفاء فاي. في عام 2004 وضع [[هيلجر ليبما]]<ref name="Lip04">Helger Lipmaa: An Oblivious Transfer Protocol with Log-Squared Communication. ISC 2005: 314–328 [https://eprint.iacr.org/2004/063.pdf (PDF)] {{Webarchive|url=https://web.archive.org/web/20170808093255/https://eprint.iacr.org/2004/063.pdf |date=08 أغسطس 2017}}</ref> تعقيد اتصال لوغاريتمي مربع <math>O(\ell \log n+k \log^2 n)</math>, حيث <math>\ell</math> هي طول الخطوط و k معيار الأمان. يتم اختزال أمان هذا النظام إلي الأمان الدلالي لنظام تشفير متماثل الشكل ومرن الطول مثل نظام تشفير Damgård–Jurik.
في عام 2005 وضع كريج جينتري وذوالفقار رامزان [http://citeseer.ist.psu.edu/context/2700426/0] تعقيد اتصال لوغاريتمي مربع يستطيع استعادة البيتات اللوغاريتمية المربعة (المتتالية) من قاعدة البيانات. يعتمد أمان نظامهم علي أساس تفسير مختلف لفرضية إخفاء فاي. آليات الاستهلاك التي يمكنها استعادة البيتات الغير متتالية قام بدراستها كل من يوفال إيشاي, وإيال كاشيلفيتز ورافايل أوستروفسكي وأميت ساهاي [http://citeseer.ist.psu.edu/ishai04batch.html].

كما يُشير أوستروفسكي وسكيث,<ref>Rafail Ostrovsky, William Skeith. A Survey of Single-Database Private Information Retrieval: Techniques and Applications. Proceedings of the Public Key Cryptography 2007 conference, pp. 393–411. (PKC-2007). [http://web.cs.ucla.edu/~rafail/PUBLIC/78.pdf (PDF)] {{Webarchive|url=https://web.archive.org/web/20120414235916/http://www.cs.ucla.edu/~rafail/PUBLIC/78.pdf |date=14 أبريل 2012}}</ref> فإن الخطط التي استخدمها كاشيلفيتز و[[أوستروفسكي]]<ref name="KusOst97"/> وليبما<ref name="Lip04"/> تستخدم أفكار متماثلة قائمة علي أساس [[تعمية|التشفير]] المتماثل. إن بروتوكول كاشيلفيتز وأوستروفسكي قائم علي أساس نظام تشفير Goldwasser–Micali, بينما بروتوكول ليبما قائم علي أساس نظام تشفير نظام تشفير Damgård–Jurik.

== تطورات المعلومات النظرية لاستعادة المعلومات الخاصة PIR ==
يتطلب [[أمن المعلومات]] النظرية افتراض أن هناك عدة خوادم غير مترابطة ولدي كل منها نسخة من قاعدة البيانات. بدون هذه [[فرضية|الفرضية]] فإن إي بروتوكول استعادة المعلومات الخاصة PIR لأمن المعلومات النظري يتطلب كم من الاتصالات التي ترقي على الأقل إلي حجم قاعدة بيانات n

== العلاقة بأوليات التشفير الأخري ==
الدوال أحادية الجانب ضرورية لكنها ليست كافية لقواعد البيانات الفردية الغير ضعيفة (أي ذات الاتصالات الخطية الفرعية) التي تتضمن معلومات خاصة حاسوبياً. في الواقع إن مثل هذه البروتوكولات قد أثبت كل من جي دي كريسينزو وتي مالكين وآر أوستروفسكي في [4] بأنها تتضمن نقل واضح (أنظر أدناه).
النقل الواضح والذي يسمي أيضاً [[بروتوكول (توضيح)|بروتوكول]] استعادة المعلومات الخاصة PIR المتماثل هو بروتوكول استعادة المعلومات الخاصة PIR بالإضافة إلي قيود بألا يعلم المستخدم أي نص غير الذي طلبه فقط. ويسمي متماثل لأن لكلا من المستخدم وقاعدة البيانات متطلبات خصوصية.
دوال الهاش المشفرة والمقاومة للائتلاف يتم تضمينها في مخطط استعادة المعلومات الخاصة PIR حاسوبي واحد كما أوضح إيشاي وكاشيلفيتز وأوستروفسكي.<ref>[http://www.springerlink.com/content/dr8aw5rdcjqx220f/ Sufficient Conditions for Collision-Resistant Hashing] {{Webarchive|url=https://web.archive.org/web/20200212233058/http://www.springerlink.com/content/dr8aw5rdcjqx220f/ |date=12 فبراير 2020}} {{وصلة مكسورة|تاريخ=2020-08-02|bot=JarBot}}</ref>

== المراجع ==
{{بداية المراجع}}
* A. Beimel, Y. Ishai, E. Kushilevitz, and J.-F. Raymond. Breaking the <math>O(n^{1/(2k-1)})</math> barrier for information-theoretic private information retrieval. ''Proceedings of the 43nd Annual IEEE Symposium on Foundations of Computer Science'', Vancouver, Canada, pages 261-270, 2002.
* Sergey Yekhanin. New locally decodable codes and private information retrieval schemes, {{ECCC|2006|06|127}}, 2006.
{{نهاية المراجع}}

=== ملاحظات ===
{{مراجع}}

== وصلات خارجية ==
* [https://web.archive.org/web/20160304210330/http://research.cyber.ee/~lipmaa/crypto/link/protocols/oblivious.php Helger Lipmaa's web links on oblivious transfer and PIR]
* [https://web.archive.org/web/20120212074635/http://www.cs.umd.edu/~gasarch/pir/ Bill Gasarch's website on PIR, with survey articles]
* [http://www.cs.ucla.edu/~rafail/ Rafail Ostrovsky's website contaiting PIR articles and surveys]
{{شريط بوابات|تقانة|تقانة المعلومات}}

[[تصنيف:بدئيات التعمية]]
[[تصنيف:بروتوكولات تعمية]]