بازیابی اطلاعات خصوصی

در علم رمزنگاری، بازیابی داده‌های خصوصی (به انگلیسی: Private information retrieval) پروتکلی می‌باشد که به کاربران اجازه می‌دهد تا یک داده را از سروری که دیتابیس را در اختیار دارد بازیابی نموده بدون اینکه معلوم شود که کدام داده که کاربر انتخاب کرده‌است در حال بازیابی است. بازیابی اطلاعات خصوصی یک نسخه ضعیف تر از(one-out-of-n oblivious transfer) است که در آن نیز لازم است که کاربر نتواند اطلاعاتی از داده‌های موجود در دیتابیسهای دیگر دریافت کند.

این پروتکل نباید با آشکار سازی اطلاعات به وسیله کلید خصوصی اشتباه گرفته شود که کاربران معمولاً اطلاعات رمز شده خود را در دیتابیس قرار می‌دهند و می‌خواهند بدون اینکه این اطلاعات رمزنگاری شده آشکار شود در آن به دنبال داده‌های مورد نظر خود بگردند که دیتابیس از کلید خصوصی برای حل این موضوع استفاده می‌کند

راه حل‌ها

یکی از پیش پا افتاده تریین و در عین حال نا کارامدترین راه ساخت بازیابی اطلاعات خصوصی برای یک سرور این است که کپی تمام موجودیت‌های دیتا بیس را برای کاربر ارسال نماییم. حال دو راه برای حل این مسئله وجود دارد: یکی ایجاد یک سرور محاسباتی دارای مرز و محدوده و دوم این که فرض کنیم چندین سرور غیر مرتبط با همدیگر داریم و به هر کدام از آن‌ها یک نسخه از پایگاه داده را بدهیم.

توضیحات

برای مثال در دیتابیس‌های یکتا (به انگلیسی: Single-Database) پروتکل بازیابی اطلاعات خصوصی به این صورت تعریف می‌شود که فرض نمایید دیتابیس شامل یکسری اطلاعات عمومی می‌باشد مثلاً n بیت رشته ذخیره شده داریم. حال می‌خواهیم با این پروتکل بیت iام این رشته را به دست آوریم بدون اینکه برای پایگاه داده معلوم شود که ما چه موردی را درخواست داده‌ایم (i مخفی بماند).

به همین منظور می‌بایست کل موجودیت‌های دیتابیس برای کاربر ارسال شود که با توجه به این موضوع که n بیت داریم پس باید n بیت داده بین کاربر و دیتابیس منتقل شود. پروتکل مورد نظر این اطلاعات را با تعداد بسیار کمتر از n بیت بازیابی می‌نماید که تعداد کم ارتباطات باعث می‌شود تا کاربر بنواند کل موجودیت‌های دیتابیس را دانلود کند.

در این پروتکل بیشتر سعی در آن شده که به پیچیدگی‌های برقراری این ارتباطات برای انتقال n بیت بپردازند و معیار سنجش این پروتکل بر مبنای میزان پیچیدگی ارائه شده توسط هر نفر می‌باشد.

تاریچه

این مسئله در سال ۱۹۹۵ توسط Chor و Goldreich و Kushilevitz و Sudan در حیطیهٔ تئوری اطلاعات معرفی گردید و در سال ۱۹۹۷ توسط Kushilevitz و Ostrovsky در حیطه محاسباتی آن ارائه شد. از آن زمان تا کنون راه حل‌های بسیار کارامدی کشف گردیده‌است. یک دیتابیس بازیابی اطلاعات خصوصی (تئوری) را می‌توان با یک ارتباط ثابت طراحی کرد و kتا دیتابیس بازیابی اطلاعات خصوصی (محاسباتی) را با $n^{O({\frac {\log \log k}{k\log k}})}$ارتباط ایجاد نمود.

در ابتدا طرح یک دیتابیس بازیابی اطلاعات خصوصی محاسباتی برای برقراری ارتباط با پیچیدگی کمتر از$n$ و برای برقرای ارتباط با پیچیدگی $n^{\epsilon }$ برای هر مقدار $\epsilon$ و $n$ که تعداد بیت‌های درون دیتابیس می‌باشد در سال ۱۹۹۷ ساخته شد.

در سال ۱۹۹۹ میلادی Christian Cachin و Silvio Micali و Markus Stadler در یک طرحی این پیچیدگی ارتباط را با چند جمله‌ای‌های لگاریتمی حساب نمودند.

در سال ۲۰۰۴ میلادی Helger Lipmaa طرح را ارائه داد که دارای پیچیدگی ارتباطی $O(\ell \log n+k\log ^{2}n)$ بود که $\ell$ طول رشته مورد نظر بود و $k$ پارامتر امنیتی در این طرح می‌بود.

تمامی طرح‌های محاسباتی بازیابی اطلاعات خصوصی که دارای پیچیدگی غیر خطی هستند، نیازمند کلید عمومی با پیچیدگی محاسباتی $\Omega (n)$ می‌باشند.

ارتباط با سایر شکل‌های رمزنگاری

استفاده از تابعه یک طرفه در این پروتکل ضروری است اما نمی‌دانیم که برای ارتباطات غیر خطی تا چه حد کافی می‌باشد.

بایددر برابر تصادم توابع درهم ساز مقاوم باشد که در هر مرحله از طرح بازیابی اطلاعات خصوصی محاسباتی استفاده می‌شود.

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Private information retrieval». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در July ۱۴, ۲۰۱۲.

برای مطالعه بیشتر

• 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 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 TR۰۶-۱۲۷, ۲۰۰۶.