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

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

به ازای هر <math>i</math>، تنها یکی از مقادیر <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 تابعی است از ورودی‌هایی که باب بر طبق بیت‌های یکتای <math>a</math> و <math>b</math> انتقال داده است و تنها بیت‌هایی در بخش راست c که مقادیر رندوم ندارند همان دو بیت سمت چپ هستند که دقیقاً نتیجه <math> a_i> b_i </math> را مشخص می‌کنند که در آن i پرارزش ترینپرارزش‌ترین بیتی است که <math>a</math> و <math>b</math> در آن تفاوت دارند. در نهایت اگر <math> a_i> b_i </math>، آنگاه آن دو بیت سمت چپ برابر ۱۱ خواهند بود و باب اعلام می‌کند که <math> a \geq b </math>. در صورتی که آن دو بیت برابر ۱۰ باشند، آنگاه <math> a_i <b_i </math> و باب a <b را اعلام خواهد کرد. در صورتی که <math>a = b</math>، آنگاه <math>c</math> دارای بخش راست نخواهد بود و در این صورت دو بیت سمت چپ <math>c</math> برابر با ۱۱ خواهد بود که جواب را مشخص می‌کند.

# <math>c</math>، موارد فوق برای <math>c</math> هم برقرار است. بخش چپ <math>c</math> مقداری تصادفی است و بخش راست آن نیز به جز دو بیت بخش چپ از مقادیری تصادفی تشکیل شده استشده‌است. استخراج هرگونه اطلاعات از روی آن دو بیت نیازمند حدس زدن مقادیر دیگری است که احتمال درست حدس زدن آنهاآن‌ها بسیار پایین است.