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

חישוב רב-משתתפים בטוח, Secure Multi-Party Computation - SMPC, הוא תחום בקריפטוגרפיה יישומית שמאפשר למספר צדדים לחשב במשותף פונקציה על קלטים פרטיים ומבטיח שאף צד לא ייחשף לקלט של משתתף אחר, מעבר למה שניתן להסיק מהתוצאה הסופית.

SMPC מודרני מבוסס על שלוש משפחות עיקריות:

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

מעגלים משובשים, Garbled Circuits - GC

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

ה-SOTA המעשי כולל אופטימיזציות כגון Free-XOR וHalf-Gates. הגישה מתבססת מתמטית על מפתחות סימטריים ומעגלים לוגיים. המודל התקשורתי מאופיין במספר סבבים קבוע, ללא תלות בעומק החישוב, אך בדרישת רוחב פס גבוהה שפרופורציונלית לגודל המעגל. הגישה אופטימלית לפעולות לוגיות, כמו השוואות ומניפולציות ביטים, אך מוגבלת בסקלאביליות ומשמשת בעיקר לתרחישי שני משתתפים.

הצפנה הומומורפית, Homomorphic Encryption - HE

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

ישנן גם טכנולוגיות עזר כמו העברת נתונים נעלמת, Oblivious Transfer - OT.

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

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

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

שלמה יונה

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

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

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