پاورپوینت بازیابی محرمانه اطلاعات Private Information Retrieval

بخشی از پاورپوینت

اسلاید 1 :

بازیابی محرمانه اطلاعات Private Information Retrieval

اسلاید 2 :

فهرست مطالب
مقدمه
مدل ساده و روشهای ابتدایی
کاربرد
بیان نتایج کارهای انجام شده
معرفی روش کوشیلویتز و استرووسکی

اسلاید 3 :

مقدمه

یک پروتکل بازیابی محرمانه اطلاعات (PIR) به کاربر اجازه میدهد تا یک رکورد را از پایگاه داده بازیابی کند، درحالیکه هویت این رکورد برای پایگاه داده مخفی بماند.

این پروتکلها در سناریویی مطرح میشوند که کاربر به پایگاهداده اطمینان ندارد.

اولین پژوهشها در این زمینه به سال 1985 توسط فیگنبان [1] و بلیکلی و میدوز [2] برمیگردند.

اسلاید 4 :

مقدمه
هدف از بازیابی اطلاعات محرمانه ایجاد یک کانال امن بین کاربر و پایگاه داده نیست.
کاربر
پایگاه داده

اسلاید 5 :

مقدمه
در این سناریو ما به پایگاه داده اعتماد نداریم.
به عبارت بهتر با یک مدیر پایگاه داده کنجکاو طرف هستیم.
کاربر
پایگاه داده
کانال امن

اسلاید 6 :

مدل ساده
یک مدل ساده از این مسأله به این صورت است که در پایگاه داده یک رشته N-بیتی ذخیره شده است و کاربر میخواهد بیت i-ام این رشته را بازیابی کند، در حالیکه پایگاه داده هیچ دانشی در مورد i کسب نکند.

index i = 1,…,w
کاربر میخواهد مقدار Bi را بداند
each Bi є {0,1}
پایگاه داده
کاربر ممکن است مقدار سایر Bi ها را نیز بدست آورد

اسلاید 7 :

روشهای ابتدایی
بازیابی کل رشته توسط کاربر
سربار فراوان
استفاده از تکنیکهای گمنامسازی
اطلاعات آماری، نیاز به شخص معتمد، حملات (حمله همه علیه یکی)

اسلاید 8 :

کاربرد
پایگاه داده اختراعات
یک دانشمند به ایدهی جدیدی مانند «چرخ» رسیده است.
قبل از ثبت این ایده، میخواهد مطمئن شود ایدهی مشابهای وجود ندارد.
آیا اختراعی مشابه «وسیلهای دایره شکل برای راحتی حملونقل» وجود دارد.
مدیر پایگاهداده اختراعات جهان این درخواست را میبیند .
پایگاهدادههای دارویی
در دنیا داروسازی دو نوع شرکت وجود دارند: شرکت کشف و ساخت دارو، شرکت جمعآوری اطلاعات مولفههای مورد استفاده در داروها
اگر شرکتهای سازنده درخواستهای خود را برای شرکتهای جمعآوری اطلاعات بفرستند .

اسلاید 9 :

کاربرد
کاربرد بین سازمانی
وزارت دفاع قصد انجام یک عملیات ویژه در منطقهی الف دارد
وزارت دفاع باید اطلاعات جغرافیایی، هواشناسی و . را در مورد منطقه الف از سایر سازمانها کسب کند
سایر سازمانها نباید متوجه قصد وزارت دفاع برای انجام عملیات در منطقه الف شوند

اسلاید 10 :

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

اگر k کپی از پایگاهداده وجود داشته باشد، که با هم در ارتباط نیستند و همچنین پایگاههای داده دارای قدرت محاسباتی نامحدود باشند، میتوان بیت i-ام را با کمتر از n بیت بازیابی کرد. برای این مسأله شماهای زیادی وجود دارد، بهترین شمایی که ما از آن آگاه هستیم نیاز به بیت دارد.

اسلاید 11 :

بیان نتایج کارهای انجام شده

کاچین و همکارانش در [4] نشان دادند که اگر فرض کنیم پایگاهداده نمیتواند مسأله را حل کند آنگاه یک شمای احتمالاتی تک-پایگاهی وجود دارد که از بیت استفاده میکند.
کوشیلویتز و استرووسکی در [5] نشان دادند که اگر فرض کنیم پایگاهداده نمیتواند مسأله Quadratic Residue حل کند، آنگاه یک شمای تک-پایگاهی وجود دارد که از بیت استفاده میکند، به طوریکه є میتواند به اندازهی دلخواه کوچک شود.
کُر و جیلبوآ در [6] نشان دادند که اگر فرض کنیم توابع یکطرفه وجود دارند آنگاه یک شما وجود دارد که از دو نسخه از پایگاهداده و بیت استفاده میکند، به طوریکه є میتواند به اندازهی دلخواه کوچک شود.

اسلاید 12 :

روش کوشیلویتز و استرووسکی- مساله QR
Zm:={0,1,…,m-1}
Zm*:={x : x є Zm such that x is relatively prime to m}
مساله باقیمانده درجه دو (QR)
x یک باقیمانده درجه 2 در پیمانهی m است اگر یک zm* є a وجود داشته باشد به نحوی که x = a2 mod m باشد.
QR(m): مجموعه همهی باقیماندههای درجه 2 در پیمانه m
QNR(m): مجموعه Zm* منهای مجموعه QR(m)

اسلاید 13 :

روش کوشیلویتز و استرووسکی- مساله QR
در Zn* که n=pq و p و q دو عدد اول بزرگ هستند پاسخگویی به سوال آیا a є QR(n) سخت است.
Z13*:
QR(13):
a2:

اسلاید 14 :

ایده اولیه
i
↓
Yi is a QR iff Bj=0

اسلاید 15 :

مشکل ایده اولیه
صحت و امنیت پروتکل فوق برقرار است ولی .

سربار محاسباتی
هزینه ارتباط:
کاربر → پایگاه داده: |B| · |Zn|
پایگاه داده→ کاربر: |Zn|

اسلاید 16 :

حل مشکل
ایده:شمای روبرو را داریم:

این شما را بسازیم:

فرض کنید |B| = v2 است و B یک ماتریس v×v است:

اسلاید 17 :

روشی صحیح
فرض کنید j ستوانی باشد که Bi در آن قرار دارد

در هر ردیف کاربر jامین عضو را درخواست میکند

در نتیجه به جای ارسال v درخواست، کاربر یک درخواست ارسال میکند.
j
↓
هزینه ارتباط:
کاربر→ پایگاه داده: v2 · |Zn|
پایگاه داده→ کاربر: v · |Zn|
روش

اسلاید 18 :

تمام اجزای روش
حاصلضرب اعضای هر سطر
kth row
Bj=0 iff
Mk is QR

اسلاید 19 :

امنیت کاربر
از هر حمله کنندهای که شمای ما را بشکند، میتوان یک ماشین ساخت که QSR را بشکند.