مسئله میلیونرهای یائو: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
بدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش |
||
خط ۹:
== پروتکل و اثبات ==
=== پروتکل ===
در این پروتکل ما از نوع دیگری از [[انتقال بی‌اعتنا]] به نام انتقال بی‌توجه ۱-۲ استفاده می‌کنیم. به‌این‌ترتیب یک بیت به صورت زیر انتقال می‌یابد: فرستنده دو بیت <math>S_0</math> و <math>S_1</math> را دارد. گیرنده یک i از مجموعه‌ی <math>i\in\{0,1\} </math> انتخاب می‌کند و فرستنده با یک انتقال بی‌توجه <math>S_i</math> را می‌فرستد به گونه‌ای که:
# فرستنده اطلاعاتی راجع به <math>S_{(1-i)}</math> پیدا نمی‌کند،
# گیرنده مقدار <math>i</math> را نمی‌فهمد.
حال با توصیف پروتکل آغاز می‌کنیم. ما ثروت آلیس را <math>a</math> و ثروت باب را <math>b</math> می‌نامیم و فرض می‌کنیم که طول <math>a</math> و <math>b</math> به صورت باینری از عدد طبیعی <math>d</math> کم‌تر است. پروتکل به شرح زیر است:
# آلیس یک ماتریس <math>K</math> با سایز <math>d\times2</math> از اعداد <math>k</math>-بیتی درست می‌کند (<math>k</math> طول کلید در پروتکل انتقال بی‌توجه است). او دو عدد تصادفی <math>0<u<2k</math> و <math>v \leq k</math> را هم برمی‌گزیند.
#<math>K_{ijl} </math> نشان دهنده‌ی بیت <math>l</math>ام ماتریس است که در خانه‌ی <math>K_{ij} </math> وجود دارد (<math>l=0</math> نشان دهنده‌ی [[کم‌ارزش‌ترین بیت است]]). هم‌چنین <math> a_i </math> بیت <math>i</math>ام ثروت آلیس است (عدد <math>a</math>). برای هر <math>i</math> به‌صروت <math> 0 \leq i \leq d </math> آلیس کارهای زیر را انجام می‌دهد:
## برای هر بیت<math> j \geq v </math> او <math> K_{i1j} </math> و <math> K_{i2j} </math> را اعداد تصادفی قرار می‌دهد.
## اگر <math> a_i=1 </math> بود، <math>l=0</math> قرار می‌دهد درغیر این‌صورت <math>l=1</math> می‌کند و برای هر <math>j</math> به صورت <math> 0 \leq j \leq 2 \cdot i -1 </math>، <math>K_{ilj}</math> را یک بیت تصادفی قرار می‌دهد.
## برای <math>m=2 \cdot i </math>، <math> K_{il(m+1)}=1 </math> و <math> K_{ilm} </math> را <math>a_i</math> قرار می دهد
## برای هر <math> i, 0 \leq i <d</math>، <math>S_i</math> یک عدد تصادفی <math>k</math>-بیتی است و <math>S_d</math> هم یک عدد تصادفی <math>k</math>-بیتی دیگر است که همه‌ی بیت‌هایش به جز دو بیت آخر تصادفی اند و دو بیت آخر به صورت <math>S_{d(k-1)}=1 \oplus \bigoplus_{j=1}^{d-1}S_{j(k-1)}\oplus \bigoplus_{j=1}^{d}K_{j1(k-1)}</math> و <math>S_{d(k-2)}=1 \oplus \bigoplus_{j=1}^{d-1}S_{j(k-2)}\oplus \bigoplus_{j=1}^{d}K_{j1(k-2)}</math> محاسبه می‌شوند که <math> \bigoplus </math> [[یای مانعةالجمع]] است.
## برای <math>l=1,2</math> قرار بدهید <math> K'_{ij}=rol(K_{il} \oplus S_i,u)</math> که در آن
# برای هر <math>i</math> که <math> 0 \leq i \leq d </math>، باب <math> K'_{il} </math> را تحت انتقال بی‌توجه انتقال می‌دهد که در آن <math> l=b_i+1 </math> و <math> b_i </math> بیت <math>i</math>ام <math>b</math> است.
# آلیس <math>N=rol(\bigoplus_{j=1}^d S_j,u)</math> را به باب می‌فرستد.
خط ۲۶:
==== درستی ====
باب نتیجه نهایی را از روی <math>N \oplus \bigoplus_{i=1}^d K'_{i(b_i+1)}=rol(\bigoplus_{i=1}^d K_{i(b_i+1)},u) </math> به‌دست می‌آورد. و نتیجه نهایی وابسته به <math>c=\bigoplus_{i=1}^d K_{i(b_i+1)}</math> است. <math>K</math> و در نتیجه <math>c</math> می‌توانند به سه قسمت تقسیم شوند. قسمت سمت چپ روی نتیجه تأثیری ندارد. قسمت سمت راست حاوی همه اطلاعات مهم است و قسمت میانی دنباله ای از بیت های ۰ است که جداکننده دو بخش قبلی است. طول هر یک از سه بخش <math>c</math> به نقشه امنیتی مرتبط است.
به ازای هر
==== امنیت ====
| |||