בעיית המיליונרים וחישוב מאובטח רב משתתפים

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

לצורך הפתרון, נניח שההון של אליס הוא i מיליונים ושל בוב הוא j מיליונים, ושניהם מוגבלים לחסם עליון של N מיליונים. התהליך מתחיל בכך שבוב מייצר מפתח פומבי הכולל את הערכים e ו-n, ומפתח פרטי d. הוא שולח לאליס את המפתח הפומבי.

אליס בוחרת מספר אקראי x ומצפינה אותו עם המפתח של בוב כדי לקבל את הערך c:

c = xᵉ mod n

לאחר מכן, אליס מחסירה את ההון שלה, i, מהתוצאה כדי לקבל ערך חדש a, אותו היא שולחת לבוב:

a = c - i

בשלב זה, בוב אינו יודע מה ההון של אליס. לכן, עבור כל סכום אפשרי u מ-1 ועד N, הוא מחבר את u ל-a ומפענח את התוצאה עם המפתח הפרטי שלו ליצירת סדרה של ערכים zᵤ:

zᵤ = (a + u)ᵈ mod n

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

כדי להסתיר את המידע שלו, בוב בוחר מספר ראשוני p. הוא יוצר רצף מספרים חדש S על ידי חישוב שארית החלוקה ב-p לכל ערכי הפענוח שחישב. אם האינדקס u קטן או שווה להון שלו, הוא משאיר את התוצאה כפי שהיא. אם האינדקס גדול מההון שלו, הוא מוסיף 1 לתוצאה.

Sᵤ = zᵤ mod p (for u ≤ j)

Sᵤ = (zᵤ + 1) mod p (for u > j)

בוב שולח את הרצף S ואת המספר p לאליס. אליס בודקת רק את האיבר במקום ה-i ברצף, שהוא ההון שלה. היא מחשבת את x mod p ומשווה לאיבר שקיבלה. אם הערכים זהים, המשמעות היא שבוב לא הוסיף 1, ולכן ההון של אליס קטן או שווה לזה של בוב. אם הערכים שונים, בוב הוסיף 1, ולכן לאליס יש יותר כסף.

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

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

הסיבוכיות של אליס: זמן קבוע O(1). אליס מבצעת מספר קבוע של פעולות, ללא שום קשר לגודל החסם העליון של ההון N. הפעולות שלה כוללות הצפנת RSA אחת, העלאה בחזקה מודולרית, חיסור אחד, פעולת מודולו אחת בסוף, והשוואה לוגית אחת.

הסיבוכיות של בוב: זמן לינארי O(N).

כמות העבודה של בוב גדלה ביחס ישר לחסם העליון של ההון האפשרי N. הוא נדרש לבצע N פעולות חיבור, N פעולות מודולו, ובעיקר, N פענוחי RSA, העלאה בחזקה מודולרית של מספרים גדולים. מדוע? ליבת הפרוטוקול היא שבוב מכין עבור אליס את כל התרחישים האפשריים, כדי שהיא תוכל לשלוף רק את זה שרלוונטי אליה. מכיוון שבוב אינו יודע מה ההון של אליס, הוא נאלץ לכסות את כל האפשרויות ולבצע את תהליך הפענוח והכנת התשובה עבור כל סכום אפשרי שאליס עשויה להחזיק בו, מ-1 ועד N. אם חסם ההון המוסכם N עומד על מיליארד שקלים, בוב ייאלץ לבצע מיליארד פעולות פענוח RSA נפרדות.

סיבוכיות התקשורת של בוב היא O(N). אליס שולחת לבוב רק את a, בוב נדרש לשלוח חזרה לאליס רצף המכיל N מספרים מוצפנים.

בעיית המיליונרים וחישוב מאובטח רב משתתפים

צריכים עזרה עם קריפטוגרפיה? צריכים עזרה עם סכימות קריפטוגרפיות? צריכים עזרה עם אלגוריתמים מבוזרים? האצת אלגוריתמים? אופטימיזציה? מחקר אלגוריתמי יישומי? דברו איתי:

שלמה יונה

מייסד ומדען ראשי, מתמטיקאי מחקר ופיתוח בע"מ

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

פודקאסט על החברה ועליי, שלמה יונה, ואופן העבודה שלנו ואיתנו: A technical deep dive about Mathematic.ai