משתמש:Amilevy/ארגז חול/בעיית המיליונרים

בעיית המליונרים היא בעיית חישוב רב-משתתפים בטוח שהוצגה לראשונה על ידי אנדרו יאו.

תיאור הבעיה

הבעיה עוסקת בשני מליונרים סקרנים המעונינים להעריך מי מהם עשיר יותר, מבלי לגלות מהו הערך המדוייק של נכסיהם. בעייה זו שקולה לבעייה הכללית יותר, בה ישנם שני מספרים a ו-b ורוצים לפתור את אי השוויון $a\geq b$ מבלי לגלות את ערכי a ו-b.

בעיית המליונרים היא בעייה חשובה בקריפטוגרפיה ופתרונה משמש במסחר אלקטרוני וכריית מידע. יישומים מסחריים לעיתים נזקקים להשוות בין מספרים סודיים אשר אבטחתם חשובה.

פתרונות רבים הוצעו לבעייה זו, ביניהם הפתרון הראשון, שהוצג על ידי יאו עצמו ואשר הינו בעל סיבוכיות זמן ומקום אקספוננציאלית. אנו נציג להלן פתרון אפשרי אחר.

פרוטוקול והוכחה

הפרוטוקול

אנו נעשה שימוש בהעברה עלומה. בהעברה בזו מועבר ביט אחד באופן הבא: לשולח יש שני ביטים $S_{0}$ ו-$S_{1}$. המקבל בוחר $i\in \{0,1\}$ והשולח שולח את $S_{i}$ בפרוטוקול ההעברה העלומה כך ש:
1. המקבל אינו מקבל כל מידע על $S_{i'}$ כאשר $i\not =i'\in \{0,1\}$.
2. ערכו של i איננו גלוי לשולח.

כעת נתחיל בתיאור הפרוטוקול עצמו. נסמן את המספר של