مسئله میلیونرهای یائو

مسئلهٔ میلیونرهای یائو یک مشکل محاسبهٔ امن چند جانبه است که توسط اندرو یائو، دانشمند برجستهٔ کامپیوتر و نظریه‌پرداز محاسباتی معرفی شده‌است. مسئله راجع به دو میلیونر به نام‌های آلیس و باب است که می‌خواهند بدون این که مقدار واقعی ثروتشان را برملا کنند، بفهمند کدام یک ثروتمندترند. این مسئله شبیه مسئلهٔ کلی‌تری است که در آن دو عدد $a$ و $b$ را داریم و می‌خواهیم بدون این که مقدار واقعی آن‌ها را بدانیم، نامساوی $a\geq b$ را حل کنیم. مسئلهٔ میلیونرها یک نمونه از محاسبات امن چندجانبه است که مسئلهٔ مهمی در رمزنگاری است و حل این مسئله در تجارت الکترونیک و داده‌کاوی استفاده می‌شود. برنامه‌های تبلیغاتی گاهی ممکن است مجبور شوند ارزش ارقامی را باهم مقایسه کنند درحالی که این مقدارها محرمانه است و حفظ امنیت‌شان مهم است. برای حل این مسئله راه‌های زیادی مطرح شده ولی حلی که خود یائو آن را ارائه داده، هم برای زمان و هم برای حافظه مقدار نمایی دارد. در این مقاله یک راه حل را توضیح می‌دهیم.

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

پروتکل

در این پروتکل ما از نوع خاصی از انتقال بی‌خبر به نام انتقال بی‌خبر ۱-۲ استفاده می‌کنیم. به‌این‌ترتیب یک بیت به صورت زیر انتقال می‌یابد: فرستنده دو بیت $S_{0}$ و $S_{1}$ را دارد. گیرنده یک i از مجموعهٔ $i\in \{0,1\}$ انتخاب می‌کند و فرستنده با یک انتقال بی‌توجه $S_{i}$ را می‌فرستد به گونه‌ای که:

1. فرستنده اطلاعاتی راجع به $S_{(1-i)}$ پیدا نمی‌کند،
2. گیرنده مقدار $i$ را نمی‌فهمد.

حال با توصیف پروتکل آغاز می‌کنیم. ما ثروت آلیس را $a$ و ثروت باب را $b$ می‌نامیم و فرض می‌کنیم که طول $a$ و $b$ به صورت باینری از عدد طبیعی $d$ کم‌تر است. پروتکل به شرح زیر است:

1. آلیس یک ماتریس $K$ با سایز $d\times 2$ از اعداد $k$-بیتی درست می‌کند ($k$ طول کلید در پروتکل انتقال بی‌توجه است). او دو عدد تصادفی $0<u<2k$ و $v\leq k$ را هم برمی‌گزیند.
2. $K_{ijl}$ نشان دهندهٔ بیت $l$ام ماتریس است که در خانهٔ $K_{ij}$ وجود دارد ($l=0$ نشان دهندهٔ کم‌ارزش‌ترین بیت است). هم‌چنین $a_{i}$ بیت $i$ام ثروت آلیس است (عدد $a$). برای هر $i$ به‌صروت $0\leq i\leq d$ آلیس کارهای زیر را انجام می‌دهد:
   1. برای هر بیت$j\geq v$ او $K_{i1j}$ و $K_{i2j}$ را اعداد تصادفی قرار می‌دهد.
   2. اگر $a_{i}=1$ بود، $l=0$ قرار می‌دهد درغیر این‌صورت $l=1$ می‌کند و برای هر $j$ به صورت $0\leq j\leq 2\cdot i-1$، $K_{ilj}$ را یک بیت تصادفی قرار می‌دهد.
   3. برای $m=2\cdot i$، $K_{il(m+1)}=1$ و $K_{ilm}$ را $a_{i}$ قرار می‌دهد
   4. برای هر $i,0\leq i<d$، $S_{i}$ یک عدد تصادفی $k$-بیتی است و $S_{d}$ هم یک عدد تصادفی $k$-بیتی دیگر است که همهٔ بیت‌هایش به جز دو بیت آخر تصادفی اند و دو بیت آخر به صورت $S_{d(k-1)}=1\oplus \bigoplus _{j=1}^{d-1}S_{j(k-1)}\oplus \bigoplus _{j=1}^{d}K_{j1(k-1)}$ و $S_{d(k-2)}=1\oplus \bigoplus _{j=1}^{d-1}S_{j(k-2)}\oplus \bigoplus _{j=1}^{d}K_{j1(k-2)}$ محاسبه می‌شوند که $\bigoplus$ xor است.
   5. برای $l=1,2$ قرار بدهید $K'_{ij}=rol(K_{il}\oplus S_{i},u)$ که در آن $rol(x,t)$ مشخص کننده نتیجه دروان $x$ به اندازه $t$-بیت به سمت چپ است.
3. برای هر $i$ که $0\leq i\leq d$، باب $K'_{il}$ را تحت انتقال بی‌توجه انتقال می‌دهد که در آن $l=b_{i}+1$ و $b_{i}$ بیت $i$ام $b$ است.
4. آلیس $N=rol(\bigoplus _{j=1}^{d}S_{j},u)$ را به باب می‌فرستد.
5. باب xor تمام اعدادی که در قسمت ۳ بدست آورد و همچنین $N$ در قسمت قبل را محاسبه می‌کند. باب نتیجه را از چپ به راست مرور می‌کند تا به دنباله بلندی از بیت‌های ۰ برسد. $c$ را بیت راست این دنباله قرار دهید ($c$ مخالف صفر است). اگر بیت سمت راست $c$ با ۱ برابر باشد، آنگاه $a\geq b$ و در غیر این صورت $a<b$.

اثبات

درستی

باب نتیجه نهایی را از روی $N\oplus \bigoplus _{i=1}^{d}K'_{i(b_{i}+1)}=rol(\bigoplus _{i=1}^{d}K_{i(b_{i}+1)},u)$ به‌دست می‌آورد. و نتیجه نهایی وابسته به $c=\bigoplus _{i=1}^{d}K_{i(b_{i}+1)}$ است. $K$ و در نتیجه $c$ می‌توانند به سه قسمت تقسیم شوند. قسمت سمت چپ روی نتیجه تأثیری ندارد. قسمت سمت راست حاوی همه اطلاعات مهم است و قسمت میانی دنباله‌ای از بیت‌های ۰ است که جداکننده دو بخش قبلی است. طول هر یک از سه بخش $c$ به نقشه امنیتی مرتبط است. به ازای هر $i$، تنها یکی از مقادیر $K_{i1}$ یا $K_{i2}$ دارای بخش راست غیر صفر هستند که در شرایط $a_{i}=1$،$K_{i1}$ و در غیر این صورت $K_{i2}$ است. علاوه بر این، اگر $i>j$ و $K_{il}$ دارای بخش راست غیری صفر باشد، آنگاه $K_{il}\oplus K_{jl}$ نیز دارای بخش راست غیر صفر خواهد بود و دو بیت سمت چپ این بخش راست با دو بیت سمت چپ $A_{il}$ مساوی خواهد شد. در نتیجه، بخش راست c تابعی است از ورودی‌هایی که باب بر طبق بیت‌های یکتای $a$ و $b$ انتقال داده است و تنها بیت‌هایی در بخش راست c که مقادیر رندوم ندارند همان دو بیت سمت چپ هستند که دقیقاً نتیجه $a_{i}>b_{i}$ را مشخص می‌کنند که در آن i پرارزش‌ترین بیتی است که $a$ و $b$ در آن تفاوت دارند. در نهایت اگر $a_{i}>b_{i}$، آنگاه آن دو بیت سمت چپ برابر ۱۱ خواهند بود و باب اعلام می‌کند که $a\geq b$. در صورتی که آن دو بیت برابر ۱۰ باشند، آنگاه $a_{i}<b_{i}$ و باب a <b را اعلام خواهد کرد. در صورتی که $a=b$، آنگاه $c$ دارای بخش راست نخواهد بود و در این صورت دو بیت سمت چپ $c$ برابر با ۱۱ خواهد بود که جواب را مشخص می‌کند.

امنیت

اطلاعاتی که باب به آلیس می‌دهد به دلیل اینکه از طریق انتقال بی‌توجه فرستاده می‌شود؛ امن است. باب از آلیس سه عدد دریافت می‌کند،

1. باب به ازای هر $i$، $rol(K_{i(1+b_{i})}\oplus S_{i},u)$ را دریافت می‌کند که در آن $S_{i}$ مقداری تصادفی است. بنابراین هیچ بخشی از اطلاعات امن تغییر پیدا نمی‌کند،
2. $N$، که نتیجه یای مانعةالجمع تعدادی عدد تصادفی است و مشخص‌کننده هیچ اطلاعات خاصی نیست. اطلاعات مرتبط با آن تنها بعد از محاسبه $c$ مشخص می‌شود و
3. $c$، موارد فوق برای $c$ هم برقرار است. بخش چپ $c$ مقداری تصادفی است و بخش راست آن نیز به جز دو بیت بخش چپ از مقادیری تصادفی تشکیل شده‌است. استخراج هرگونه اطلاعات از روی آن دو بیت نیازمند حدس زدن مقادیر دیگری است که احتمال درست حدس زدن آن‌ها بسیار پایین است.

پیچیدگی

پیچیدگی این پروتکل $O(d^{2})$ است. آلیس به ازای هر بیت $a$ یک عدد $d$ بیتی تولید می‌کند و باب $d$ بار یای مانعةالجمع اعداد $d$ بیتی را محاسبه می‌کند. پیچیدگی این عملیات $O(d^{2})$ می‌شود. بخش ارتباطی نیز از مرتبه $O(d^{2})$ است، در نتیجه پیچیدگی این پروتکل $O(d^{2})$ است.

برای مطالعه بیشتر

• رمزنگاری
• محاسبات امن چندجانبه
• آراس‌ای
• میلیونر سوسیالیستی، روشی دیگر برای اینکه میلیونرها تشخیص دهند که سرمایه‌هایشان یکی است یا نه.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Yao's Millionaires Problem». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۹ مارچ ۲۰۱۴.