مسئله میلیونرهای یائو: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
Gharakhanlou (بحث | مشارکتها) جزبدون خلاصۀ ویرایش |
جز ربات ردهٔ همسنگ (۳۰.۱) +مرتب (۱۴.۹ core): + رده:نظریه رمزنگاری |
||
خط ۱:
'''مسئلهٔ میلیونرهای یائو''' یک مشکل محاسبهٔ امن چند جانبه
این مسئله شبیه مسئلهٔ کلیتری است که در آن دو عدد <math>a</math> و <math>b</math> را داریم و میخواهیم بدون این که مقدار واقعی آنها را بدانیم، نامساوی <math>a \geq b</math> را حل کنیم.
مسئلهٔ میلیونرها یک نمونه از [[محاسبات چندجانبه امن|محاسبات امن چندجانبه]] است که مسئلهٔ مهمی در [[رمزنگاری]] است و حل این مسئله در [[تجارت الکترونیک]] و [[دادهکاوی]] استفاده میشود. برنامههای تبلیغاتی گاهی ممکن است مجبور شوند ارزش ارقامی را باهم مقایسه کنند درحالی که این مقدارها محرمانه است و حفظ امنیتشان مهم است.
خط ۷:
== پروتکل و اثبات ==
=== پروتکل ===
در این پروتکل ما از نوع خاصی از [[انتقال بیخبر]]
# فرستنده اطلاعاتی راجع به <math>S_{(1-i)}</math> پیدا نمیکند،
# گیرنده مقدار <math>i</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>l=1,2</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> به نقشه امنیتی مرتبط است.
به ازای هر <math>i</math>، تنها یکی از مقادیر <math>K_{i1} </math> یا <math>K_{i2} </math>
==== امنیت ====
خط ۳۲:
اطلاعاتی که باب به آلیس میدهد به دلیل اینکه از طریق انتقال بیتوجه فرستاده میشود؛ امن است.
باب از آلیس سه عدد دریافت میکند،
# باب به ازای هر <math>i</math>،
# <math>N</math>، که نتیجه یای مانعةالجمع تعدادی عدد تصادفی است و مشخصکننده هیچ اطلاعات خاصی نیست. اطلاعات مرتبط با آن تنها بعد از محاسبه <math>c</math> مشخص میشود و
# <math>c</math>، موارد فوق برای <math>c</math>
=== پیچیدگی ===
خط ۴۱:
== برای مطالعه بیشتر ==
* [[رمزنگاری]]
* [[محاسبات چندجانبه امن|محاسبات امن چندجانبه]]
* [[آراسای]]
* [[میلیونر سوسیالیستی]]، روشی دیگر برای اینکه میلیونرها تشخیص دهند که سرمایههایشان یکی است یا نه.
== منابع ==
* {{یادکرد-ویکی
|پیوند=http://en.wikipedia.org/wiki/Yao%27s_Millionaires%27_Problem
سطر ۵۷ ⟵ ۵۶:
[[رده:پروتکلهای رمزنگاری]]
[[رده:نظریه رمزنگاری]]
|