بازیابی اطلاعات خصوصی
در علم رمزنگاری، بازیابی داده‌های خصوصی پروتکلی می‌باشد که به کاربران اجازه می‌دهد تا یک داده را از سروری که دیتابیس را در اختیار دارد بازیابی نموده بدون اینکه معلوم شود که کدام داده که کاربر انتخاب کرده‌است در حال بازیابی است. بازیابی اطلاعات خصوصی یک نسخه ضعیف تر از(one-out-of-n oblivious transfer) است که در آن نیز لازم است که کاربر نتواند اطلاعاتی از داده‌های موجود در دیتابیسهای دیگر دریافت کند.
این پروتکل نباید با آشکار سازی اطلاعات به وسیله کلید خصوصی اشتباه گرفته شود که کاربران معمولاً اطلاعات رمز شده خود را در دیتابیس قرار می‌دهند و می‌خواهند بدون اینکه این اطلاعات رمزنگاری شده آشکار شود در آن به دنبال داده‌های مورد نظر خود بگردند که دیتابیس از کلید خصوصی برای حل این موضوع استفاده می‌کند
یکی از پیش پا افتاده تریین و در عین حال نا کارامدترین راه ساخت بازیابی اطلاعات خصوصی برای یک سرور این است که کپی تمام موجودیت‌های دیتا بیس را برای کاربر ارسال نماییم. حال دو راه برای حل این مسئله وجود دارد: یکی ایجاد یک سرور محاسباتی دارای مرز و محدوده و دوم این که فرض کنیم چندین سرور غیر مرتبط با همدیگر داریم و به هر کدام از آن‌ها یک نسخه از پایگاه داده را بدهیم.
برای مثال در دیتابیس‌های یکتا پروتکل بازیابی اطلاعات خصوصی به این صورت تعریف می‌شود که فرض نمایید دیتابیس شامل یکسری اطلاعات عمومی می‌باشد مثلاً n بیت رشته ذخیره شده داریم. حال می‌خواهیم با این پروتکل بیت iام این رشته را به دست آوریم بدون اینکه برای پایگاه داده معلوم شود که ما چه موردی را درخواست داده‌ایم (i مخفی بماند).
به همین منظور می‌بایست کل موجودیت‌های دیتابیس برای کاربر ارسال شود که با توجه به این موضوع که n بیت داریم پس باید n بیت داده بین کاربر و دیتابیس منتقل شود. پروتکل مورد نظر این اطلاعات را با تعداد بسیار کمتر از n بیت بازیابی می‌نماید که تعداد کم ارتباطات باعث می‌شود تا کاربر بنواند کل موجودیت‌های دیتابیس را دانلود کند.
در این پروتکل بیشتر سعی در آن شده که به پیچیدگی‌های برقراری این ارتباطات برای انتقال n بیت بپردازند و معیار سنجش این پروتکل بر مبنای میزان پیچیدگی ارائه شده توسط هر نفر می‌باشد.
این مسئله در سال ۱۹۹۵ توسط Chor و Goldreich و Kushilevitz و Sudan در حیطیهٔ تئوری اطلاعات معرفی گردید و در سال ۱۹۹۷ توسط Kushilevitz و Ostrovsky در حیطه محاسباتی آن ارائه شد. از آن زمان تا کنون راه حل‌های بسیار کارامدی کشف گردیده‌است. یک دیتابیس بازیابی اطلاعات خصوصی (تئوری) را می‌توان با یک ارتباط ثابت طراحی کرد و kتا دیتابیس بازیابی اطلاعات خصوصی (محاسباتی) را با formula_1ارتباط ایجاد نمود.
در ابتدا طرح یک دیتابیس بازیابی اطلاعات خصوصی محاسباتی برای برقراری ارتباط با پیچیدگی کمتر ازformula_2 و برای برقرای ارتباط با پیچیدگی formula_3 برای هر مقدار formula_4 و formula_2 که تعداد بیت‌های درون دیتابیس می‌باشد در سال ۱۹۹۷ ساخته شد.
در سال ۱۹۹۹ میلادی Christian Cachin و Silvio Micali و Markus Stadler در یک طرحی این پیچیدگی ارتباط را با چند جمله‌ای‌های لگاریتمی حساب نمودند.
در سال ۲۰۰۴ میلادی Helger Lipmaa طرح را ارائه داد که دارای پیچیدگی ارتباطی formula_6 بود که formula_7 طول رشته مورد نظر بود و formula_8 پارامتر امنیتی در این طرح می‌بود.
تمامی طرح‌های محاسباتی بازیابی اطلاعات خصوصی که دارای پیچیدگی غیر خطی هستند، نیازمند کلید عمومی با پیچیدگی محاسباتی formula_9 می‌باشند.
استفاده از تابعه یک طرفه در این پروتکل ضروری است اما نمی‌دانیم که برای ارتباطات غیر خطی تا چه حد کافی می‌باشد. بایددر برابر تصادم توابع درهم ساز مقاوم باشد که در هر مرحله از طرح بازیابی اطلاعات خصوصی محاسباتی استفاده می‌شود.