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

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

היסטוריה

חישוב רב משתתפים נחשב לאחד היעדים החשובים ביותר של הקריפטוגרפיה המודרנית ולו היסטוריה ארוכה. החל עם עבודתו של אנדרו יאו, בתחילת שנות השמונים של המאה הקודמת, שהציע פרוטוקול לשני משתתפים שנקרא בקיצור 2PC. הפרוטוקול תואר בצורת משל הנקרא בעיית המליונרים שהיא בעיה בוליאנית. שני מיליונרים רוצים לדעת מי מהם יותר עשיר מבלי לחשוף את הונם האישי. במקרה זה הקלט הוא הונם האישי והפלט הוא סיבית אחת. הוא הציע פתרון המבוסס על מעגל בוליאני מעוות. לאחר מכן הציעו גולדרייך, מיקאלי וויגדרזון הרחבה של הפרוטוקול ליותר משתתפים, המבוסס על חלוקת סוד והוכחה באפס ידיעה, מה שהפך במרוצת הזמן למודל כללי ששימש כהשראה ובסיס לפרוטוקולים החדשים שבאו אחריו. מתוך כך התפתח ענף חדש בקריפטוגרפיה הנקרא חישוב פונקציונלי בטוח בקיצור (SFE) או באופן כללי יותר קריפטוגרפיה פונקציונלית (בקיצור FE).
עד שנות ה-2000 נחשב חישוב רב משתתפים לנושא בעל ערך תאורטי בלבד, במרוצת השנים חלה התקדמות משמעותית וכיום כבר אפשר למנות מספר מערכות מעשיות שפועלות בהצלחה על עיקרון של חישוב רב משתתפים בטוח. בשנת 2008 הופעל לראשונה פרויקט חישוב רב משתתפים בטוח במסגרת מכרז לחוזי סלק סוכר בהשתתפות 1200 מגדלים בדנמרק. הפרויקט נועד להעריך את מחיר השוק של סלק הסוכר בהסתמך על נתונים שנאספו מהמגדלים בצורה כזו שאף אחד מהם לא נזקק לחשוף את תעריפי הקנייה/מכירה שלו. אמנם החישוב ארך כשלושים דקות, שזה לא רע עבור אירוע שקורה רק פעם בשנה, אבל במקרה הכללי זה עשוי להיות בעייתי. נושא היעילות הוא הבעיה הגדולה ביותר של התחום הזה ושל הקריפטוגרפיה המתקדמת בכלל.
באופן כללי אפשר לבסס חישוב רב משתתפים על שילוב של ארבעה פרימיטיבים קריפטוגרפיים ידועים: הצפנה הומומורפית, העברה עלומה, הוכחה באפס ידיעה וחלוקת סוד. הצפנה הומומורפית מלאה פרקטית לא קיימת לכן ישנן הצעות לשימוש בהצפנה הומומורפית חלקית, כמו SPDZ. הפרוטוקולים הראשונים שפותחו הסתמכו על ההנחה שקיים ערוץ תקשורת בטוח כך שכל אחד מהשחקנים יכול להעביר לשני הודעה בצורה מזוהה כמו למשל בשימוש עם תשתית PKI (עם חתימה דיגיטלית ופונקציית גיבוב) והפרוטוקול אמור להתמודד עם סיטואציה שבה חלק מהשחקנים הגונים וחלקם מה שנקרא 'הגונים למחצה' או מושחתים, כשרובם נחשבים הגונים וכן גם בסיטואציות שבהן רוב השחקנים מושחתים. ההבדל בין שחקן הגון למחצה לבין שחקן מושחת הוא שהראשון ממלא אחר הוראות הפרוטוקול אבל הוא בכל זאת מעוניין לדעת כמה שיותר על הסודות של האחרים ואילו בשני ההנחה היא שהוא מסוגל לסטות מהוראות הפרוטוקול במטרה לעוות את התוצאה ולגרום לפלט שונה. חישוב רב משתתפים בטוח כללי אמור לתת מענה גם במקרים בהם לא קיים ערוץ בטוח בין השחקנים וכולם למעט אחד מושחתים. במקרה הכללי בלתי אפשרי להבטיח חישוב רב משתתפים אם יותר משליש מהשחקנים אינם הגונים או מושחתים. במרוצת השנים המודל הכללי של חישוב רב משתתפים בטוח הפך כר פורה למחקר.