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

כדי להעריך ביטחון של פרוטוקול חישוב רב־משתתפים קריפטוגרפי, מאמצים סגנון של "סימולציה". נניח שקיים עולם אידיאלי שבו הפרוטוקול מבוצע על ידי צד שלישי נאמן ובהגדרה מוסכם שהצד השלישי תמיד הגון ודיסקרטי. בעולם האמיתי הפרוטוקול מבוצע על ידי השחקנים עצמם והמתקיף שיכול להיות אחד או יותר מהשחקנים המשתתפים בפרוטוקול, או גורמים חיצוניים, שמנסים לגלות מידע פרטי של אחד או יותר מהשחקנים ההגונים. אומרים שהפרוטוקול יהיה בטוח אם כל התקפה שתימצא נגד הפרוטוקול אפשר יהיה "לדמות" גם בעולם האידיאלי. קיומו של סימולטור כזה מבטיח שהפרוטוקול המעשי יהיה קרוב במידת האפשר לעולם האידיאלי שהוא בטוח בהגדרה.
השאלה העיקרית שעוסקים בה מהיבט תאורטי היא עם כמה יריבים הפרוטוקול יכול להתמודד בו זמנית. ההנחה היא שכל היריבים מתואמים ביניהם, אם כי זה לא בהכרח תמיד נכון. העדפה היא להבטיח שהפרוטוקול בטוח גם אם רק שחקן אחד בלבד נותר הגון, אבל במקרה כזה העלות מבחינה חישובית גבוהה ולא תמיד זה ניתן. לעומת זאת אם נוכל להתפשר על מצב שבו רק מיעוט מהשחקנים מושחת אז אפשר להגיע לפרוטוקול יעיל מבחינה מעשית. כמו כן יש להבחין בין יריבים סטטיים לבין יריבים אדפטיביים. במקרה השני, היריב יכול להחליט איזה שחקן להשחית אחרי שהפרוטוקול מתחיל.
שאלה נוספת שמתעוררת היא עם איזה סוגים של יריבים הפרוטוקול מסוגל להתמודד. קיימים ארבעה סוגים עיקריים בהתאם לאסטרטגיה שלהם:
יריב פסיבי. היריב הבסיסי ביותר, שמניחים שהוא אינו יכול לסטות ממהלכי הפרוטוקול, אלא מוכרח לבצע את הפרוטוקול כלשונו ומתוך כך הוא מנסה לגלות מידע לגבי הקלט של שחקנים אחרים. יש עניין בדיון התאורטי לגבי יריב פסיבי, למרות שזו הגדרה מאוד חלשה, כי אפשר להוכיח שניתן להמיר פרוטוקול בטוח נגד יריב פסיבי לפרוטוקול בטוח נגד יריב אקטיבי.
יריב אקטיבי. יריב שמניחים שהוא יכול לסטות ממהלכי הפרוטוקול כרצונו במטרה לשנות את התוצאה והוא מנסה לאסוף כמה שיותר מידע לגבי הקלט של השחקנים ההגונים.
יריב סמוי. הוא יריב אקטיבי שמסתיר את כוונתו. הוא אינו בהכרח מבצע את הפרוטוקול כלשונו אבל מצד שני הוא לא רוצה להיתפס בקלקלתו. האם גורם הנחשב הגון יעמיד בסכנה את המוניטין שלו כדי להשיג מידע כלשהו על שחקן אחר תלוי בחשיבות המידע שהוא מנסה להשיג לעומת ההפסד במידה שהוא נתפס.
יריב רציונלי. זהו היבט חדש יחסית שדן ביריב שיש לו מטרה ספציפית והוא מוכן לרמות כדי להשיג יתרון משמעותי לגבי מטרה זו בלבד. מקרה כזה הוא ביטוי לחיבור בין שני תחומים, קריפטוגרפיה ותורת המשחקים ויש לזה השלכות מעשיות במקרים כמו מכרז מקוון.
מעבר ליריבים המנויים, תמיד קיים האיום של יריב חיצוני. מה שנקרא התקפת אדם באמצע. להתקפה כזו חשיבות רבה במיוחד במקרים בהם הפרוטוקול רץ במקביל עם שחקנים שונים, כך שהיריב יכול להצליב מידע בין הריצות השונות של הפרוטוקול. בקריפטוגרפיה סיטואציה כזו נקראת בשם הכללי מודל הרכבה אוניברסלי (באנגלית 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 הוא מחשב ארבעה טקסטים מוצפנים:
אז הוא מבצע תמורה אקראית שלהם (מערבב אותם) ושולח את התוצאות ל- 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.