סילביו מיקאלי: להוכיח בלי לגלות
לפני שסילביו מיקאלי (Silvio Micali) ועמיתיו עסקו בכך, הקריפטוגרפיה הייתה מלאכת מחשבת של טריקים חכמים, שנשפטו לפי השאלה אם מישהו הצליח לפצח אותם. הקריירה של מיקאלי, שיועדה להפיכת מלאכה זו לדיסציפלינה עם הוכחות מתמטיות מוצקות מאחורי טענותיה, הניבה את אחד הרעיונות המוזרים והאלגנטיים ביותר בתחום: דרך לשכנע מישהו שטענה היא נכונה תוך מתן אפס מידע נוסף על הסיבה לכך.
מרומא לברקלי
סילביו מיקאלי נולד ב-13 באוקטובר 1954 באיטליה. הוא קיבל תואר במתמטיקה מאוניברסיטת לה ספיינצה (La Sapienza University) ברומא בשנת 1978, ולאחר מכן חצה את האוקיינוס לצורך דוקטורט במדעי המחשב באוניברסיטת קליפורניה, ברקלי, אותו השלים ב-1982 בהנחייתו של מנואל בלום (Manuel Blum), בעצמו חתן פרס טיורינג לעתיד שעבד בחזית התאוריה הקריפטוגרפית. מיקאלי הצטרף לסגל המחלקה להנדסת חשמל ומדעי המחשב ב-MIT בשנת 1983 ונשאר שם מאז, בעבודתו דרך המעבדה למדעי המחשב ובינה מלאכותית ב-MIT, עם תקופות הוראה נוספות באוניברסיטת פנסילבניה, אוניברסיטת טורונטו ואוניברסיטת צ'ינגהואה.
הפיכת האבטחה להוכחה מתמטית
פרויקט המחקר המרכזי של מיקאלי, שבוצע ברובו בשיתוף עם שפי גולדווסר (Shafi Goldwasser), היה להחליף את הסטנדרט המסורתי של אבטחה בקריפטוגרפיה - שאף אחד עוד לא פרץ את המערכת - בסטנדרט מתמטי: הוכחה שפריצת המערכת תדרוש פתרון בעיה שנחשבת כקשה חישובית. יחד עם גולדווסר הוא פיתח הצפנה הסתברותית, שיטה המצפינה את אותה הודעה בצורה שונה בכל פעם שהיא נשלחת, ובכך חוסמת סוג של התקפות שבהן יריב יכול ללמוד מידע רק מעצם ההבחנה ששני צפנים זהים. התיעוד של ה-ACM על פרס טיורינג המשותף שלהם זוקף לזכותם את ייסוד תחום האבטחה הניתנת להוכחה ועיגון הרעיון שהאבטחה הקריפטוגרפית "חייבת להיות חישובית ולא מוחלטת" - מסגור מחדש שהעניק לדיסציפלינה כולה בסיס קפדני שהיה חסר לה. הצגת מערכות הוכחה אינטראקטיביות והסתברותיות על ידם תרמה גם היא ישירות לתורת הסיבוכיות החישובית הרבה מעבר לגבולות הקריפטוגרפיה.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →הוכחות באפס ידיעה
הרעיון הבודד המוכר ביותר הקשור למיקאלי הוא הוכחה באפס ידיעה (Zero-Knowledge Proof), שהומצא במשותף עם גולדווסר וצ'ארלס ראקוף (Charles Rackoff): פרוטוקול שבו "מוכיח" משכנע "מוודא" שטענה היא נכונה - שהם יודעים סיסמה, שעסקה היא תקפה, שלגרף יש צביעה מסוימת - מבלי לחשוף דבר אחר לגבי הסיבה לכך שהיא נכונה, אפילו לא את המידע שיאפשר לוודא לשחזר את ההוכחה בעצמו. זה נשמע פרדוקסלי בשמיעה ראשונה וטופל כסקרנות מתמטית כאשר הוצג; מאז הוא הפך למרכיב פעיל במערכות אימות, וכעבור עשורים, בטכנולוגיית פרטיות של בלוקצ'יין. גוף העבודה הרחב יותר של מיקאלי התרחב ליצירת פונקציות פסאודו-אקראיות, חישוב מאובטח מרובה משתתפים - המאפשר למספר צדדים לחשב במשותף תוצאה מבלי לחשוף זה לזה את הקלטים הפרטיים שלהם - ופרוטוקולי העברה בלתי מודעת, כל אחד מהם מהווה אבן בניין המשמשת כיום לאורך ההנדסה הקריפטוגרפית המודרנית.
מתאוריה לסטארט-אפים
בניגוד לתאורטיקנים רבים שהסתפקו בהשארת רעיונותיהם על הדף, מיקאלי לא הגביל את עבודתו לכתבי עת. בשנת 2001 הוא היה שותף להקמת CoreStreet Ltd, חברת אבטחה שנמכרה מאוחר יותר ל-ActivIdentity ב-2009, ובתחילת שנות ה-2000 סייע ביצירת Peppercoin, מערכת מיקרו-תשלומים דיגיטלית מוקדמת. בשנת 2017 הוא ייסד את Algorand, פלטפורמת בלוקצ'יין מבוססת הוכחת החזקה (Proof-of-Stake) שנועדה ליישם את עשרות שנות התאוריה הקריפטוגרפית שלו על ספר חשבונות ציבורי ומבוזר - מהלך מאוחר בקריירה שהציב חתן פרס טיורינג ישירות במרכז תעשיית המטבעות הדיגיטליים שעבורה, במובן מסוים, הוא הקדיש שלושים שנה להנחת התשתית המתמטית.
הכרה
מיקאלי וגולדווסר קיבלו במשותף את פרס טיורינג של ה-ACM לשנת 2012, שהוענק בשנת 2013, "על עבודה טרנספורמטיבית שהניחה את היסודות התאורטיים-סיבוכיים למדע הקריפטוגרפיה". קודם לכן קיבל מיקאלי את פרס גדל (Gödel Prize) בשנת 1993 עבור תורת מערכות ההוכחה האינטראקטיביות ואת פרס RSA למצוינות במתמטיקה בשנת 2004. הוא חבר באקדמיה הלאומית למדעים ובאקדמיה הלאומית להנדסה, והפך לעמית ACM בשנת 2017.
מדוע סילביו נקרא גאון
הראיה החזקה ביותר לכנות את מיקאלי גאון היא מושגית ולא אנקדוטלית: הוכחות באפס ידיעה הן מסוג הרעיונות שברגע שרואים אותם, נראים הכרחיים מובן מאליו ובכל זאת דרשו קפיצה דמיונית ממשית להגותם מלכתחילה - הוכחה שאינה מוכיחה דבר מלבד את עצמה. הפיכת "האבטחה" ממלאכה לא רשמית לדיסציפלינה עם משפטים והפחתות, ההישג שציטוט פרס טיורינג מכבד במיוחד, דרשה לא רק מיומנות טכנית אלא את התעוזה המושגית לשאול איך בכלל תיראה הגדרה מתמטית של סודיות. הכנות המהותית כאן היא שאף אחד מאלו לא היה עבודת יחיד. פרס טיורינג הוענק במשותף למיקאלי ולשפי גולדווסר, ומאמר ההוכחה באפס ידיעה עצמו מונה שלושה מחברים - גולדווסר, מיקאלי וצ'ארלס ראקוף - מה שהופך זאת למקרה מובהק של רעיון יסוד שנבנה באמצעות שותפות מתמשכת ולא תובנה מבודדת של אדם אחד. המיזמים העצמאיים המאוחרים יותר של מיקאלי, CoreStreet ו-Algorand, מראים נכונות אישית להמר על התאוריה שלו עצמו במציאות מסחרית ותעשייתית, אך הליבה התאורטית המקנה לו את תווית ה"גאון" הייתה, לפי כל התיאורים כולל ציטוט הפרס עצמו, הישג משותף.
מורשת
עבודתו של מיקאלי איפסה מחדש את קו הבסיס למה שמשמעו לכנות מערכת קריפטוגרפית מאובטחת, והוכחות באפס ידיעה בפרט שרדו את עמימותן המקורית כדי להפוך לתשתית - המשמשת בפרוטוקולי אימות, מערכות בלוקצ'יין שומרות פרטיות ותוכניות אימות שלא היו קיימות כאשר הוא וגולדווסר תיארו את הרעיון לראשונה. מעטים המושגים הקריפטוגרפיים שנדדו כל כך רחוק מתאוריה טהורה לטכנולוגיה יומיומית מוטמעת. העובדה שדיסציפלינה שמתמטיקאים פטרו פעם כמחשבה מאוחרת הנדסית מחזיקה כעת ביסודות תאורטיים-סיבוכיים משלה, הנלמדת לצד חישוביות וניתוח אלגוריתמי בכל תוכנית לימודים רצינית למדעי המחשב, היא במידה רבה התוצאה הישירה של המסגור מחדש שמיקאלי וגולדווסר דחפו בתחילת שנות ה-80 - מעבר מהשאלה האם מערכת כבר נפרצה לשאלה מה, בדיוק, היה צריך להיות נכון לגבי היקום כדי שהיא תהיה ניתנת לפריצה בכלל.