مسئله میلیونرهای یائو: تفاوت میان نسخه‌ها

'''مسأله‌ی میلیونر‌هایمیلیونرهای یائو''' یک مسأله‌ی یک مشکل محاسبه ی امن چند جانبه است که توسط [[اندرو یائو]]، دانشمند برجسته‌ی کامپیوتر و نظریه‌پرداز محاسباتی معرفی شده است. مسأله راجع به دو میلیونر به نام‌های آلیس و باب است که می‌خواهند بدون این که مقدار واقعی ثروتشان را برملا کنند، بفهمند کدام یک ثروتمند‌ترندثروتمندترند.

این مسأله شبیه مسأله‌ی کلی‌تری است که در آن دو عدد <math>a</math> و <math>b</math> را داریم و می‌خواهیم بدون این که مقدار واقعی آن‌ها را بدانیم، نا‌مساوینامساوی <math>a \geq b</math> را حل کنیم.

مسأله‌ی میلیونر‌‌هامیلیونرها یک نمونه از محاسبات امن چندجانبه است که مسأله‌ی مهمی در [[رمز‌نگاریرمزنگاری]] است و حل این مسأله در [[تجارت الکترونیک]] و [[داده‌کاوی]] استفاده می‌شود. برنامه‌های تبلیغاتی گاهی ممکن است مجبور شوند ارزش‌ارزش ارقامی را با‌همباهم مقایسه کنند در‌حالیدرحالی که این مقدار‌هامقدارها محرمانه است و حفظ امنیت‌شان مهم است.

== پروتکل و اثبات ==

=== پروتکل ===

حال با توصیف پروتکل آغاز می‌کنیم. ما ثروت آلیس را <math>a</math> و ثروت باب را <math>b</math> می‌نامیم و فرض می‌کنیم که طول <math>a</math> و <math>b</math> به صورت باینری از عدد طبیعی <math>d</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> 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> 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>N</math> در قسمت قبل را محاسبه می‌کند. باب نتیجه را از چپ به راست مرور می‌کند تا به دنباله بلندی از بیت های ۰ برسد. <math>c</math> را بیت راست این دنباله قرار دهید (<math>c</math> مخالف صفر است). اگر بیت سمت راست <math>c</math> با ۱ برابر باشد، آنگاه <math>a \geq b</math> و در غیر این صورت <math>a < b</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> است. K و در نتیجه c می‌توانند به سه قسمت تقسیم شوند. قسمت سمت چپ روی نتیجه تأثیری ندارد. قسمت سمت راست حاوی همه اطلاعات مهم است و قسمت میانی دنباله ای از بیت های ۰ است که جداکننده دو بخش قبلی‌قبلی است. طول هر یک از سه بخش c به نقشه امنیتی مرتبط است.

به ازای هر i، تنها یکی از مقادیر <math>K_{i1} </math> یا <math>K_{i2} </math> دارای بخش راست غیر صفر هستند که در شرایط <math>a_i=1 </math>،<math>K_{i1} </math> و در غیر این صورت <math>K_{i2} </math> است. علاوه بر این، اگر <math> i>j </math> و <math>K_{il} </math> دارای بخش راست غیری صفر باشد، آنگاه <math>K_{il} \oplus K_{jl} </math> نیز دارای بخش راست غیر صفر خواهد بود و دو بیت سمت چپ این بخش راست با دو بیت سمت چپ <math>A_{il}</math> مساوی خواهد شد. در نتیجه، بخش راست c تابعی است از ورودی هایی که باب بر طبق بیت های یکتای a و b انتقال داده است و تنها بیت هایی در بخش راست c که مقادیر رندوم ندارند همان دو بیت سمت چپ هستند که دقیقاٌدقیقاً نتیجه <math> a_i > b_i </math> را مشخص می‌کنند که در آن i پرارزش ترین بیتی است که a و b در آن تفاوت دارند. در نهایت اگر <math> a_i > b_i </math>، آنگاه آن دو بیت سمت چپ برابر ۱۱ خواهند بود و باب اعلام می‌کند که <math> a \geq b </math>. در صورتی که آن دو بیت برابر ۱۰ باشند، آنگاه <math> a_i < b_i </math> و باب a < b را اعلام خواهد کرد. در صورتی که a = b، آنگاه c دارای بخش راست نخواهد بود و در این صورت دو بیت سمت چپ c برابر با ۱۱ خواهد بود که جواب را مشخص می‌کند.

==== امنیت ====

=== پیچیدگی ===