موضوع مقاله: مسئله میلیونرهای یائو | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله میلیونرهای یائو | مقدمه: مسئلهٔ میلیونرهای یائو یک مشکل محاسبهٔ امن چند جانبه است که توسط اندرو یائو، دانشمند برجستهٔ کامپیوتر و نظریه‌پرداز محاسباتی معرفی شده‌است. | ## بخش 1: مسئله میلیونرهای یائو | مسئله راجع به دو میلیونر به نام‌های آلیس و باب است که می‌خواهند بدون این که مقدار واقعی ثروتشان را برملا کنند، بفهمند کدام یک ثروتمندترند. این مسئله شبیه مسئلهٔ کلی‌تری است که در آن دو عدد و را داریم و می‌خواهیم بدون این که مقدار واقعی آن‌ها را بدانیم، نامساوی را حل کنیم. مسئلهٔ میلیونرها یک نمونه از محاسبات امن چندجانبه است که مسئلهٔ مهمی در رمزنگاری است و حل این مسئله در تجارت الکترونیک و داده‌کاوی استفاده می‌شود. برنامه‌های تبلیغاتی گاهی ممکن است مجبور شوند ارزش ارقامی را باهم مقایسه کنند درحالی که این مقدارها محرمانه است و حفظ امنیت‌شان مهم است. برای حل این مسئله راه‌های زیادی مطرح شده ولی حلی که خود یائو آن را ارائه داده، هم برای زمان و هم برای حافظه مقدار نمایی دارد. پروتکل و اثبات پروتکل در این پروتکل ما از نوع خاصی از انتقال بی‌خبر به نام انتقال بی‌خبر ۱-۲ استفاده می‌کنیم. گیرنده یک i از مجموعهٔ انتخاب می‌کند و فرستنده با یک انتقال بی‌توجه را می‌فرستد به گونه‌ای که: فرستنده اطلاعاتی راجع به پیدا نمی‌کند، گیرنده مقدار را نمی‌فهمد. ما ثروت آلیس را و ثروت باب را می‌نامیم و فرض می‌کنیم که طول و به صورت باینری از عدد طبیعی کم‌تر است. پروتکل به شرح زیر است: آلیس یک ماتریس با سایز از اعداد -بیتی درست می‌کند ( طول کلید در پروتکل انتقال بی‌توجه است). | ## بخش 2: مسئله میلیونرهای یائو | نشان دهندهٔ بیت ام ماتریس است که در خانهٔ وجود دارد ( نشان دهندهٔ کم‌ارزش‌ترین بیت است). برای هر به‌صروت آلیس کارهای زیر را انجام می‌دهد: برای هر بیت او و را اعداد تصادفی قرار می‌دهد. اگر بود، قرار می‌دهد درغیر این‌صورت می‌کند و برای هر به صورت ، را یک بیت تصادفی قرار می‌دهد. برای ، و را قرار می‌دهد برای هر ، یک عدد تصادفی -بیتی است و هم یک عدد تصادفی -بیتی دیگر است که همهٔ بیت‌هایش به جز دو بیت آخر تصادفی اند و دو بیت آخر به صورت و محاسبه می‌شوند که xor است. باب xor تمام اعدادی که در قسمت ۳ بدست آورد و همچنین در قسمت قبل را محاسبه می‌کند. قسمت سمت راست حاوی همه اطلاعات مهم است و قسمت میانی دنباله‌ای از بیت‌های ۰ است که جداکننده دو بخش قبلی است. به ازای هر ، تنها یکی از مقادیر یا دارای بخش راست غیر صفر هستند که در شرایط ، و در غیر این صورت است. علاوه بر این، اگر و دارای بخش راست غیری صفر باشد، آنگاه نیز دارای بخش راست غیر صفر خواهد بود و دو بیت سمت چپ این بخش راست با دو بیت سمت چپ مساوی خواهد شد. در نتیجه، بخش راست c تابعی است از ورودی‌هایی که باب بر طبق بیت‌های یکتای و انتقال داده است و تنها بیت‌هایی در بخش راست c که مقادیر رندوم ندارند همان دو بیت سمت چپ هستند که دقیقاً نتیجه را مشخص می‌کنند که در آن i پرارزش‌ترین بیتی است که و در آن تفاوت دارند. | ## بخش 3: مسئله میلیونرهای یائو | در نهایت اگر ، آنگاه آن دو بیت سمت چپ برابر ۱۱ خواهند بود و باب اعلام می‌کند که . در صورتی که ، آنگاه دارای بخش راست نخواهد بود و در این صورت دو بیت سمت چپ برابر با ۱۱ خواهد بود که جواب را مشخص می‌کند. امنیت اطلاعاتی که باب به آلیس می‌دهد به دلیل اینکه از طریق انتقال بی‌توجه فرستاده می‌شود؛ امن است. باب از آلیس سه عدد دریافت می‌کند، باب به ازای هر ، را دریافت می‌کند که در آن مقداری تصادفی است. بنابراین هیچ بخشی از اطلاعات امن تغییر پیدا نمی‌کند، ، که نتیجه یای مانعةالجمع تعدادی عدد تصادفی است و مشخص‌کننده هیچ اطلاعات خاصی نیست. اطلاعات مرتبط با آن تنها بعد از محاسبه مشخص می‌شود و ، موارد فوق برای هم برقرار است. بخش چپ مقداری تصادفی است و بخش راست آن نیز به جز دو بیت بخش چپ از مقادیری تصادفی تشکیل شده‌است. استخراج هرگونه اطلاعات از روی آن دو بیت نیازمند حدس زدن مقادیر دیگری است که احتمال درست حدس زدن آن‌ها بسیار پایین است. آلیس به ازای هر بیت یک عدد بیتی تولید می‌کند و باب بار یای مانعةالجمع اعداد بیتی را محاسبه می‌کند. | ## جمع‌بندی | برای مطالعه بیشتر رمزنگاری محاسبات امن چندجانبه آراس‌ای میلیونر سوسیالیستی، روشی دیگر برای اینکه میلیونرها تشخیص دهند که سرمایه‌هایشان یکی است یا نه.