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

پروتکل

در این پروتکل ما از نوع خاصی از انتقال بی‌خبر به نام انتقال بی‌خبر ۱-۲ استفاده می‌کنیم. به‌این‌ترتیب یک بیت به صورت زیر انتقال می‌یابد: فرستنده دو بیت ${\displaystyle S_0}$

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

حال با توصیف پروتکل آغاز می‌کنیم. ما ثروت آلیس را ${\displaystyle a}$

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

اثبات

درستی

باب نتیجه نهایی را از روی ${\displaystyle N\oplus \underset{i=1}{\overset{d}{⨁}}{K}_{i(b_i+1)}^{\prime }=rol(\underset{i=1}{\overset{d}{⨁}}{K}_{i(b_i+1)},u)}$

امنیت

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

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

پیچیدگی

پیچیدگی این پروتکل ${\displaystyle O(d^2)}$

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