עיתונאיות ועיתונאים, הירשמו כאן להודעות לעיתונות שלנו
הירשמו לניוזלטר החודשי שלנו:
שתף
פרס טיורינג לשנת 2012 הוענק לפרופ' שפי גולדווסר ממכון ויצמן למדע
האגודה האמריקאית למיחשוב - ACM – העניקה את פרס טיורינג לפרופ' שפי גולדווסר מהמחלקה למדעי המחשב ומתמטיקה שימושית במכון ויצמן למדע, ומהמעבדה למדעי המחשב ואינטליגנציה מלאכותית במכון הטכנולוגי של מסצ'וסטס (MIT). יחד איתה זכה בפרס פרופ' סילביו מיקלי מהמכוןהטכנולוגי של מסצ'וסטס. פרופ' גולדווסר היא האשה השלישית הזוכה בפרס זה מעולם. היא גם השלישית מבין מדעני מכון ויצמן למדע, אחרי פרופ' אמיר פנואלי (1996) ופרופ' עדי שמיר (2002), שזכתה בו. פרס טיורינג הוא הפרס החשוב ביותר במדעי המחשב (תחום בו לא מוענק פרס נובל).
הצפנה הסתברותית
במאמר מדעי שפרסמו בשנת 1982, אשר עסק ב"הצפנה הסתברותית", הניחו גולדווסר ומיקלי יסודות לתורת ההצפנה המודרנית, שבעיני רבים הפכו את תורת ההצפנה מ"אמנות" למדע. במאמר הוצגו מספר נושאים חלוציים, שנחשבים היום לאבני דרך בסיסיות בתחום זה. בין אלה אפשר למנות: הצגת הגדרות בטיחות פורמליות, הנחשבות כיום ל"תו תקן" באבטחת מידע; הצגת שיטות הצפנה אקראיות, אשר יכולות לענות על דרישות בטיחות מחמירות, שבעבר אפשר היה להתמודד איתן רק באמצעות תוכנות הצפנה דטרמיניסטיות; והצגת שיטה ל"הוכחות רדוקציוניסטיות", המראה כיצד אפשר לתרגם התקפות קלות ביותר על בטיחות המידע לאלגוריתמים המסוגלים לפתור בעיות מתמטיות קלאסיות, כמו פירוק לגורמים. מהוכחות כאלה אפשר רק להרוויח, שכן הן מראות שאחת משתי קביעות מרשימות חייבת להיות נכונה: או שיש ברשותנו מערכת הצפנה בטוחה לחלוטין, או שיש בידינו אלגוריתם חדש המסוגל לפרק מספרים לגורמים ראשוניים (ואגב כך לחשוף מידע מוצפן).
אפס ידיעה
במאמר רב השפעה אחר, שפרסמו בשנת 1985 ביחד עם פרופ' צ'רלס רקוף, הציגו גולדווסר ומיקלי את הרעיון ל"הוכחות אינטראקטיביות באפס ידיעה". דוגמה לשימוש בהוכחות כאלה יכולה להיות מכשיר כספומט, שבמקום לבקש מהמשתמש את הקוד הסודי, יצטרך רק לוודא שהוא אכן יודע מהו. הוכחות כאלה מאפשרות למשתמשים העובדים ביחד, אך אינם סומכים זה על זה, לבצע חישובים משותפים על נתונים השמורים ברשת האינטרנט, מבלי לחשוף את הנתונים עצמם.
בניגוד להוכחות מתמטיות קלאסיות, אותן אפשר לכתוב ולבדוק, הוכחה אינטראקטיבית נעשית באמצעות דו-שיח. צד אחד – ה"מוכיח" – מנסה לשכנע את הצד האחר – ה"מוודא" – כי יש בידו הוכחה לטענה מתמטית. על ה"מוודא" לשאול את ה"מוכיח" סדרה של שאלות, אותן ה"מוכיח" אינו מכיר מראש. השאלות נבחרות באופן אקראי, אך ה"מוודא" בוחר כל שאלה בהתאם לתשובה שקיבל על השאלה הקודמת. אם ה"מוכיח" אינו יודע את ההוכחה לטענה המתמטית, קיימת הסתברות גבוהה שה"מוודא" יבחין בטעות. כיוון שאפשר לשכנע את ה"מוודא" כי אכן קיימת הוכחה מבלי לספק לו את ההוכחה עצמה, ההוכחה קרויה "הוכחה באפס ידיעה".
חשיבותו של המאמר לגבי תורת ההצפנה הייתה ברורה מיד עם פרסומו, שכן, בין היתר, היא מציעה שיטת זיהוי המאפשרת שימוש בטוח באינטרנט. הרעיון הוא, שהמשתמש יכיר הוכחה לטענה פרטית וייחודית לו, אשר תשמש כסיסמה. כדי לזהות את עצמו, ייצור המשתמש קשר עם "מוודא" (כמו, לדוגמה, כספומט), ויציג לו הוכחה באפס מידע לטענה הפרטית שלו.
שיטה זו משפיעה גם על תורת הסיבוכיות. היא מאפשרת לוודא את אמיתותן של הוכחות מתמטיות במהירות רבה יותר מאמיתותן של הוכחות קלאסיות, ואפילו מאפשרות למתמטיקאים להוכיח, כי טענות מתמטיות מסוימות אינן נכונות (באמצעות הוכחת אי-קיומן של הוכחות קלאסיות). הרעיונות שהעלו גולדווסר ומיקלי מיושמים בדפדפנים של ימינו, ומאפשרים שימוש בטוח בכרטיסי אשראי ברשת.
שתף
