איך מוכיחים שפרוטוקול קריפטוגרפי הוא מאובטח?

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

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

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

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

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

אנחנו נגדיר שהפרוטוקול בעולם האמיתי הוא מאובטח, אם ורק אם מתקיים הכלל הבא:

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

איך מוכיחים את זה מתמטית? בעזרת סימולטור.

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

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

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

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

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

איך מוכיחים שפרוטוקול קריפטוגרפי הוא מאובטח?

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

שלמה יונה

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

053-7326360

shlomo.yona@mathematic.ai 

https://mathematic.ai

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