חישוב רב-משתתפים בטוח

חישוב רב־משתתפים בטוח (באנגלית: Secure multi-party computation; בקיצור SMPC או MPC), הוא ענף בקריפטוגרפיה העוסק בשיטות לחישוב פונקציה מוסכמת של קלטים ממשתתפים שונים באופן שהקלטים עצמם נשארים סודיים וזאת מבלי להיעזר בצד שלישי. בניגוד לקריפטוגרפיה רגילה בין משתתפים שסומכים זה על זה כשהפרוטוקול אמור להגן עליהם מפני גורמים חיצוניים, במודל זה המשתתפים לא בהכרח סומכים זה על זה והפרוטוקול אמור להגן על המשתתפים עצמם זה מזה במידה וחלקם או רובם בלתי הגונים או מושחתים.

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

היסטוריה

חישוב רב־משתתפים נחשב לאחד היעדים החשובים ביותר של הקריפטוגרפיה המודרנית ולו היסטוריה ארוכה. החל עם עבודתו של אנדרו יאו, בתחילת שנות ה-80 של המאה ה-20, שהציע פרוטוקול לשני משתתפים שנקרא בקיצור 2PC. הפרוטוקול תואר בצורת משל הנקרא בעיית המיליונרים שהיא בעיה בוליאנית. שני מיליונרים רוצים לדעת מי מהם יותר עשיר מבלי לחשוף את הונם האישי. במקרה זה הקלט הוא הונם האישי והפלט הוא סיבית אחת. הוא הציע פתרון המבוסס על מעגל בוליאני מעוות. לאחר מכן הציעו עודד גולדרייך, סילביו מיקאלי ואבי ויגדרזון הרחבה של הפרוטוקול ליותר משתתפים, המבוסס על חלוקת סוד והוכחה באפס ידיעה, מה שהפך במרוצת הזמן למודל כללי ששימש כהשראה ובסיס לפרוטוקולים החדשים שבאו אחריו. מתוך כך התפתח ענף חדש בקריפטוגרפיה הנקרא חישוב פונקציונלי בטוח בקיצור (SFE) או באופן כללי יותר קריפטוגרפיה פונקציונלית (בקיצור FE).

עד תחילת המאה ה-21 נחשב חישוב רב־משתתפים לנושא בעל ערך תאורטי בלבד, במרוצת השנים חלה התקדמות משמעותית וכיום כבר אפשר למנות מספר מערכות מעשיות שפועלות בהצלחה על עיקרון של חישוב רב־משתתפים בטוח. בשנת 2008 הופעל לראשונה פרויקט חישוב רב־משתתפים בטוח במסגרת מכרז לחוזי סלק סוכר בהשתתפות 1,200 מגדלים בדנמרק. הפרויקט נועד להעריך את מחיר השוק של סלק הסוכר בהסתמך על נתונים שנאספו מהמגדלים בצורה כזו שאף אחד מהם לא נזקק לחשוף את תעריפי הקנייה/מכירה שלו. אמנם החישוב ארך כשלושים דקות, שזה לא רע עבור אירוע שקורה רק פעם בשנה, אבל במקרה הכללי זה עשוי להיות בעייתי. נושא היעילות הוא הבעיה הגדולה ביותר של התחום הזה ושל הקריפטוגרפיה המתקדמת בכלל.

באופן כללי אפשר לבסס חישוב רב־משתתפים על שילוב של ארבעה פרימיטיבים קריפטוגרפיים ידועים: הצפנה הומומורפית, העברה עלומה, הוכחה באפס ידיעה וחלוקת סוד. הצפנה הומומורפית מלאה פרקטית לא קיימת לכן ישנן הצעות לשימוש בהצפנה הומומורפית חלקית, כמו SPDZ. הפרוטוקולים הראשונים שפותחו הסתמכו על ההנחה שקיים ערוץ תקשורת בטוח כך שכל אחד מהשחקנים יכול להעביר לאחר הודעה בצורה מזוהה כמו למשל בשימוש עם תשתית PKI (עם חתימה דיגיטלית ופונקציית גיבוב) והפרוטוקול אמור להתמודד עם סיטואציה שבה חלק מהשחקנים הגונים וחלקם מה שנקרא 'הגונים למחצה' או מושחתים, כשרובם נחשבים הגונים וכן גם בסיטואציות שבהן רוב השחקנים מושחתים. ההבדל בין שחקן הגון למחצה לבין שחקן מושחת הוא שהראשון ממלא אחר הוראות הפרוטוקול אבל הוא בכל זאת מעוניין לדעת כמה שיותר על הסודות של האחרים ואילו בשני ההנחה היא שהוא מסוגל לסטות מהוראות הפרוטוקול במטרה לעוות את התוצאה ולגרום לפלט שונה. חישוב רב־משתתפים בטוח כללי אמור לתת מענה גם במקרים בהם לא קיים ערוץ בטוח בין השחקנים וכולם למעט אחד מושחתים. במקרה הכללי בלתי אפשרי להבטיח חישוב רב־משתתפים אם יותר משליש מהשחקנים אינם הגונים או מושחתים. במרוצת השנים המודל הכללי של חישוב רב־משתתפים בטוח הפך כר פורה למחקר.

תיאור כללי

בעיית חישוב רב־משתתפים היא כדלהלן: ישנם $n$ שחקנים המסומנים $P_{1},P_{2},P_{3},...,P_{n}$, כל אחד מהם מחזיק במידע פרטי משלו המסומנים $x_{1},x_{2},x_{3},...,x_{n}$ בהתאמה. ונניח שהם הסכימו על פונקציה $y=f(x_{1},x_{2},x_{3},...,x_{n})$ שהם רוצים לחשב על המידע הפרטי שלהם, אבל הם אינם סומכים זה על זה והם לא רוצים לחשוף או לשתף את המידע האישי שלהם. פתרון פשוט לבעיה האמורה יכול להיות הפרוטוקול הבא: השחקנים ימנו צד שלישי נאמן וימסרו לו את כל המידע הפרטי שלהם. הוא יחשב עבורם את הפונקציה $f$ על המידע הפרטי ויפרסם את התוצאה. זהו הפתרון שננקט בפועל בימינו אבל יש בו חסרונות. לא תמיד האמון שניתן בצד השלישי מוצדק ובמיוחד ייתכנו סיטואציות מסוימות שבהן אי אפשר לסמוך על צד שלישי. פרוטוקול MPC אמור להחליף את הפונקציונליות של הצד השלישי, בשני היבטים חשובים:

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

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

מודל ביטחון

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

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

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

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

מעבר ליריבים המנויים, תמיד קיים האיום של יריב חיצוני. מה שנקרא התקפת אדם באמצע. להתקפה כזו חשיבות רבה במיוחד במקרים בהם הפרוטוקול רץ במקביל עם שחקנים שונים, כך שהיריב יכול להצליב מידע בין הריצות השונות של הפרוטוקול. בקריפטוגרפיה סיטואציה כזו נקראת בשם הכללי מודל הרכבה אוניברסלי (באנגלית Universal Composable) בקיצור UC שדן בביטחון של פרוטוקול אינטראקטיבי קריפטוגרפי המורץ במקביל עם קלט שונה. הוכח שאין אפשרות להשיג מורכבות כזו בחישוב רב־משתתפים בטוח אלא רק במקרה שבו יש לכל הצדדים סוד משותף, או באמצעות תשתית מפתח ציבורי, שמן הסתם יהיה צורך בה בכל מקרה.

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

כשמדברים על פרוטוקול חישוב רב־משתתפים בטוח בדרך כלל מנסחים אותו במונחים של מעגל אלקטרוני. ישנם שני סוגים: מעגל בוליאני ומעגל אריתמטי. למעשה עם מעגל בוליאני אפשר לבנות מעגל אריתמטי אבל הוא פחות יעיל. במעגל בוליאני של יאו המודל מורכב משני צדדים, צד $A$ נקרא בונה מעגל וצד $B$ נקרא מעריך. $A$ מצפין או מערבל את המעגל ושולח אותו ל-$B$. בשלב זה $B$ מקבל מפתח $X_{a}$ המתאים לקלט של $A$ שהוא הסיבית $a$. כדי לפענח את המידע $B$ צריך להשיג גם את המפתח $Y_{b}$ אך $b$ חייב להיות מוסתר מ-$A$. כדי להשיג את המפתח מ-$A$ באופן מוסתר הוא משתמש בפרוטוקול העברה עלומה שבו $A$ מפיק שני קלטים $Y_{0},Y_{1}$ ו-$B$ מגריל סיבית קלט אחת $b$ ובסיום הפרוטוקול $B$ השיג את $Y_{b}$ מבלי ש-$A$ יידע מהו $b$. הערבול של המעגל מתבצע כך: כאשר $A$ רוצה להסתיר שער AND הוא מחשב ארבעה טקסטים מוצפנים:

$C_{00}=E_{X_{0},Y_{0}}(Z_{0})$

$C_{01}=E_{X_{0},Y_{1}}(Z_{0})$

$C_{10}=E_{X_{1},Y_{0}}(Z_{0})$

$C_{11}=E_{X_{1},Y_{1}}(Z_{1})$

אז הוא מבצע תמורה אקראית שלהם (מערבב אותם) ושולח את התוצאות ל-$B$ שיכול לפענח רק את הטקסט המוצפן שמתאים למפתח $(X_{a},Y_{b})$ ומזה הוא יכול לדעת מהו $Z_{a\land b}$. ההנחה היא ש-$B$ יכול לזהות הבדל בין פענוח נכון לפענוח לא נכון, אפשר למשל להוסיף מספר קבוע של אפסים בסוף ההודעה לפני ההצפנה כך שבסבירות גבוהה רק המפתח הנכון יניב תוצאה שתכיל מספר קבוע של אפסים בסופה, לעומת זאת פענוח עם מפתח שגוי יניב תוצאה הנראית אקראית לגמרי. דרך אחרת יותר יעילה נקראת Point-and-permute שבה אם נתייחס לשער המוצפן כאל טבלה, אפשר לקבוע שחלק מסיביות המפתחות ישמשו כאינדקסים לשורה ועמודה. הפלט של השערים יכול לשמש כמפתח להצפנת השכבה הבאה של שערים וכן הלאה, או ש-$A$ יכריז מהם $(0,Z_{0}),(1,Z_{1})$. בכל אופן בדרך זו אפשר להצפין מעגל שלם בצורה שהמעריך יוכל לחשב את הפלט מבלי לדעת מהו הקלט. שזו המטרה של חישוב רב־משתתפים.

הפרוטוקול של יאו שתואר בתמצית בטוח רק במסגרת מודל שבו היריב פסיבי בלבד. הבעיה העיקרית היא ש-$A$ יכול עקרונית לשלוח ל-$B$ מעגל המחשב פונקציה אחרת ממה שהוסכם מראש מבלי ש-$B$ יוכל לדעת זאת. כלומר במקרה כזה $A$ הוא יריב אקטיבי שיכול לסטות ממהלכי הפרוטוקול. באופן כללי כדי להתאים את הפרוטוקול שיהיה בטוח גם נגד יריב אקטיבי אפשר להפעיל פרוטוקול משני שנקרא Cut-and-choose כמו בהוכחה באפס ידיעה. $A$ ישלח ל-$B$ מספר מרובה של עותקים של המעגל הבוליאני המעוות ו-$B$ יבחר תת-קבוצה אקראית של מעגלים ש-$A$ יצטרך "לפתוח" (לחשוף בפניו את המעגלים המקוריים המתאימים להם), אם הוא רואה בכל המקרים שהמעגלים מחשבים את הפונקציה המוסכמת אז סטטיסטית הוא יכול להיות משוכנע ש-$A$ לא מרמה אותו ומנסה להגניב פונקציה אחרת.

למעגל אריתמטי יש עדיפות במקרים מסוימים מהיבט של יעילות. מעגל זה בדרך כלל מיישמים עם פונקציית הצפנה הומומורפית חלקית מעל פעולת החיבור או פעולת הכפל, למשל אם $C_{1}=E(x)$ וכן $C_{2}=E(y)$ אז $C_{1}\otimes C_{2}=E(x+y)$ כאשר הפעולה $\otimes$ היא פעולה אריתמטית מודולו $p$ כלשהו. במקרה כזה $A$ יכול לשלוח ל-$B$ את $C_{1}=E(a)$ שבתורו ינצל את תכונת ההומורפיות של ההצפנה כדי לחשב את $C_{2}=E(ab-1)$. כעת $A$ יכול לפענח את זה כדי לקבל את $s=ab-1$ מודולו $p$. זהו מעין שיתוף סוד בין $A$ ל-$B$ מעל פעולת החיבור של $r$ ו-$s$ שהם הכפולה של הקלטים $a$ ו-$b$ כך שמתקיים $r+s=ab$.

פרויקטים

נכון לשנת 2019 קיימים מספר פרויקטים לחישוב רב־משתתפים בטוח לשימוש כללי, בהם:

• Fairplay. חישוב פונקציות בטוח (SFE) שהוקם בחסות האוניברסיטה העברית בירושלים. זוהי מערכת מפותחת המאפשרת חישוב מעגל בוליאני על ידי שנים או יותר שחקנים עם ביטחון פאסיבי.
• VIFF תשתית המאפשרת יישום חישוב רב־משתתפים בטוח הכולל אפשרות לחישובים אריתמטיים כמו חיבור וכפל בהתבסס על שיתוף סוד פסידו-אקראי של שמיר. עם תמיכה למקביליות.
• Sharemind. מערכת חישוב בטוח לשלושה משתתפים עם אפשרות לשחקן לא הגון פסיבי אחד לכל היותר. המערכת פותחה על ידי חברת Cybernetica מאסטוניה. הרעיון הוא במקום להחזיק במסד נתונים מרכזי לפזר את מסד הנתונים על פני מספר נקודות חישוב. הפרויקט מתמקד סביב הבעיה של שיתוף וניתוח של מידע ממקורות שונים.
• TASTY. פרויקט חישוב בטוח לשני משתתפים המאפשר חישובים בוליאניים ואריתמטיים עם ביטחון פאסיבי בלבד, הפועל על שילוב של מעגל בוליאני מעוות עם הצפנה הומומורפית.
• Jana. מסד נתונים התומך בחישוב רב־משתתפים בטוח, שפותח על ידי חברת Galois מארצות הברית. מסד הנתונים פועל לפי מודל שנקרא Priavte Data as Service או בקיצור PDaaS למסד נתונים יחסי. הייחודיות במסד הנתונים הזה שהוא מאפשר לבצע חישובים וסטטיסטיקות על המידע המצוי במסד הנתונים מבלי לפענח אותו.
• Partisia (אורכב 10.09.2019 בארכיון Wayback Machine) שהוקם על ידי חברה מדנמרק שנחשבת לחלוצה בתחום MPC. עיקר התמחותה הוא מכרזים מקוונים והיא יישמה לראשונה חישוב רב־משתתפים במכרז לסוכר.
• Unbound Tech. חברה ישראלית המציעה תמיכה בשמירה על סודות ארגוניים כמו מפתחות הצפנה בכל סיטואציה בהתבסס על טכנולוגיות MPC.