הקריפטוגרף שמבטיח שנוכל לסמוך על המחשבים שלנו | מגזין קוונטה

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

"הייתי עושה צרות," היא אמרה. "בעצם - לא ממש, אבל בעצם - זרקו אותי מהתיכון."

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

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

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

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

איך הפכת ממעצבן צרות בתיכון לאקדמאי?

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

מה היה במתמטיקה שכבש אותך?

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

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

על איזה סוג של בעיות קריפטוגרפיות עבדת?

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

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

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

האם מוסד אי פעם באמת ישתמש במערכת הזו?

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

איך העבודה שלך התפתחה לניתוח האבטחה של המכשירים שלנו?

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

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

איך הגיעו ההוכחות הללו?

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

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

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

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

כמו תעודת מקוריות?

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

אז איך מסירים את האינטראקציה ליצירת האישורים הניתנים להעברה?

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

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

דיברת על מכונות שצריכות להיות "פוסט-קוונטי מאובטחות". מה זה אומר?

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

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

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

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

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

מעבר ממחשוב קלאסי למחשוב קוונטי נשמע כמו עקומת למידה תלולה.

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