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

אגודת ACM בתחום המיחשוב ומדעי המחשב הכריזה היום (רביעי) על הענקת פרס טיורינג לפרופ' שפי גולדווסר מהמחלקה למדעי המחשב ומתמטיקה שימושית במכון ויצמן למדע, ומהמעבדה למדעי המחשב ואינטליגנציה מלאכותית במכון הטכנולוגי של מסצ'וסטס (MIT). יחד איתה יקבל את הפרס פרופ' סילביו מיקלי מהמכון הטכנולוגי של מסצ'וסטס. הפרס מוענק להם על "עבודה מהפכנית שהניחה את היסודות התיאורטיים לתורת ההצפנה בתחום הסיבוכיות, תוך המצאת שיטות חדשות וחלוציות לאימות יעיל של הוכחות מתמטיות בתחום תורת הסיבוכיות".

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

הצפנה הסתברותית

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

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

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

הוכחות אינטראקטיביות באפס ידיעה

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

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

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

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

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

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

יישומים מעשיים

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

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

האשה השלישית הזוכה בפרס טיורינג

פרופ' גולדווסר היא כלת פרס הנשיא לחוקרים צעירים מטעם הקרן הלאומית האמריקאית למדע, וזכתה בפרס Grace Murray Hopper שמעניק ה-ACM לחוקר צעיר בעל הישגים יוצאי דופן בתחום מדעי המחשב. היא זכתה פעמיים בפרס גדל (Gödel), המוענק במשותף על-ידי קבוצה ב-ACM העוסקת באלגוריתמים ובתורת החישוב (SIGACT), והאיגוד האירופי למדעי המחשב התיאורטיים (EATCS).

גולדווסר נבחרה לאקדמיה הלאומית האמריקאית לאמנויות ומדעים, לאגודה הלאומית האמריקאית למדעים, ולאקדמיה הלאומית האמריקאית להנדסה. היא נבחרה על-ידי מועצת ה-ACM לענייני נשים במדעי המחשב לשאת את הרצאת אתנה, וקיבלה את פרס עמנואל פיור שמעניק ארגון מהנדסי החשמל ואלקטרוניקה (IEEE), וכן את מדליית בנג'מין פרנקלין במדעי המחשב ובמדעים קוגניטיביים שמעניק מכון פרנקלין.

גולדווסר סיימה את לימודי התואר הראשון במתמטיקה באוניברסיטת קרנגי מלון, פנסילבניה בשנת 1979, ואת לימודי התואר השני והשלישי במדעי המחשב באוניברסיטת קליפורניה בברקלי. לאחר מכן, בשנת 1983, המשיכה למחקר בתר-דוקטוריאלי במכון הטכנולוגי של מסצ'וסטס. בשנת 1993 הצטרפה לסגל המחלקה למדעי המחשב ומתמטיקה שימושית במכון ויצמן למדע, כפרופסור מן המניין.

פרופ' גולדווסר היא האשה השלישית הזוכה בפרס טיורינג.

מידע נוסף אפשר לקבל במשרד דובר מכון ויצמן למדע: 08-934-3856