אני מתחייב לאפשר למגלי העתידות לשכנע אותי

יצא לי פעם לראות קטע משעשע מאוד מתוכנית האירוח של יהורם גאון. הוא אירח את ליאור מנור, והלה ניבא איזו נבואה עתידית של משהו שאין לו עליו שליטה ושם את הנבואה בכספת באחריות מפיקי התוכנית. לאחר זמן מה, שוב בתוכנית ולאחר שתוצאת האירוע המנובא הייתה ידועה לכל, פתח גאון את הכספת והוציא את הנבואה, שהתגלתה כנכונה לחלוטין, כמובן. מי שהראה לי את הוידאו השתעשע בעיקר ממה שהיה גלוי לחלוטין כאשר גאון פתח את הכספת - הקוד שלה היה 1-2-3-4, כנראה קוד ברירת המחדל הנפוץ בעולם. יש סיפורי אימה מזוויעים לספר על האסונות הקריפטוגרפיים שמתרחשים מכך שדבקים בברירת המחדל, אך לא ניכנס אליהם כעת. הסיבה שאני מספר על השטות הזו כעת היא כי מן הסתם, מה שראיתי לא שכנע אותי שלליאור מנור יש כוחות נבואיים (מצד שני, ובניגוד לקוסמים אחרים מסויימים, למיטב ידיעתי מנור לא טוען שיש לו כאלו). מה בעצם הבעיה במה שראיתי, שמונעת ממני להשתכנע? הבעיה היא בכך שהעובדה שמנור שם את הפתק בכספת לא מהווה "התחייבות" אמינה שלו לנבואה שלו, מכיוון שהוא יכול לשנות אותה די בקלות - הרי אני לא באמת רואה מה עושים עם הכספת, או אפילו אם זו אותה כספת, ואין לי שום סיבה להניח שמפיקי התוכנית לא משתפים פעולה עם מנור. מצד שני, איך אפשר אחרת? הרי מנור ואני לא מתקשרים על בסיס יומיומי. טוב, ברור שיש דרך טריוויאלית - מנור יגיד בטלוויזיה מה הנבואה במקום להסתבך עם מעטפות, וחסל; אבל הרי החוק הראשון של הנבואה אומר שאסור לעשות דברים כאלו. אם כן, האם יש דרך שבה מנור יכול "להתחייב" לאיזו שהיא תוצאה, מבלי שיוכל אחר כך לשנות את התוצאה שעליה התחייב, ועם זאת כל עוד הוא לא "יפתח" את ההתחייבות הזו, לא אדע בעצמי מהי? סכימת התחייבות (Commitment scheme) הוא המושג הקריפטוגרפי שעוסק בדיוק בסיטואציה שכזו. הרעיון התיאורטי הוא כזה: יש שני "שחקנים" - אליס ובוב מיועדנו משכבר הימים, אבל לצורך הגיוון אשנה אותם לאריק ובנץ. לאריק יש סוד והוא רוצה להתחייב עליו בפני בנץ, מבלי לחשוף אותו לבינתיים - כלומר, לשלוח לבנץ מידע כלשהו שיהווה "התחייבות", ולאחר זמן מה "לפתוח" את ההתחייבות על ידי שליחת מידע נוסף שיגלה לבנץ מהו הסוד, וישכנע אותו שזה אכן הסוד שעליו בוצעה ההתחייבות מלכתחילה. לצורך פשטות נניח שהסוד הוא בן ביט אחד - כלומר, הוא 0 או 1 (זה לא מגביל אותנו, כי אם יש סוד שמורכב מכמה ביטים, אפשר להתחייב על כל ביט בנפרד). יש שתי דרישות שנשמעות סבירות מפרוטוקול שישמש את אריק ובנץ - סודיות ומחוייבות. סודיות פירושה שבנץ לא מסוגל לגלות מהו הסוד בהינתן ה"התחייבות", ומחוייבות פירושה שאריק לא יוכל לשנות את הסוד לאחר שביצע את ההתחייבות - דהיינו, אם הוא ינסה, בנץ ישים לב לרמאות. אפשר לדבר על כמה רמות שונות של סודיות ומחוייבות. ניקח למשל סודיות. יש סודיות מושלמת, שפירושה שלא משנה מה בנץ יעשה ולא משנה איך - מובטח, תמיד, שהוא לא יצליח לגלות את הסוד של אריק, כל עוד אריק לא פתח את ההתחייבות. לעומת זאת, יש סודיות חישובית - פירוש הדבר שאם בנץ מוגבל מבחינה חישובית רק לחישובים הסתברותיים פולינומיים (המשמעות המדוייקת אינה חשובה - חשבו על כך בתור "חישוב שאפשר לבצע בזמן סביר בתוכנית מחשב שיכולה לבצע הגרלות"), הסיכוי שהוא יצליח לגלות את הסוד של אריק הוא אפסי (רמת ביניים היא "סודיות סטטיסטית", שפירושה שגם אם אריק לא מוגבל חישובית, הסיכוי שלו לגלות את הסוד הוא נמוך ביותר ותלוי בצורה האקראית שבה ההתחייבות נוצרה). כל אלו תקפים גם עבור מחוייבות - כך למשל מחוייבות חישובית פירושה שאם אריק מוגבל לחישובים יעילים בלבד, ההסתברות שהוא יצליח לרמות ולשנות את הסוד היא אפסית. נתחיל מהחדשות הרעות - אין, לא הייתה ולא תהיה סכימת התחייבות שגם הסודיות וגם המחוייבות שלה מושלמים. הסיבה לכך היא אלמנטרית מבחינה מתמטית - כמעט פילוסופית. נניח שיש לנו סודיות מושלמת. זה אומר שלא משנה מה בנץ עושה, יש לפחות שני "סודות פוטנציאליים" שכל אחד מהם עשוי להיות הסוד שעליו אריק התחייב, ובנץ לא יכול להבדיל ביניהם; אפילו אם הוא "ינחש" כל דבר אפשרי שאריק יגיד לו בזמן פתיחת ההתחייבות, עדיין יהיו שני סודות שהם לגיטימיים. מכאן שאריק יכול לרמות - הוא יתחייב על סוד א', אבל בזמן פתיחת ההתחייבות יגיד את מה שצריך להגיד כדי להפוך את סוד ב' ללגיטימי. הפואנטה כאן היא שאנו מקווים שלאריק לא יהיה מושג מה צריך להגיד כדי להפוך את סוד ב' ללגיטימי, ושחיפוש התשובה הזו ייקח לו יותר מדי זמן. מכאן רואים גם שאם יש מחוייבות מושלמת, אז יש רק סוד אחד שאריק מסוגל לשכנע בו את בנץ, ואז בנץ יכול "לנחש" מה אריק יגיד כדי לשכנע אותו, ולהשתכנע. זו רק שאלה של הזמן שיידרש לבנץ כדי למצוא את השכנוע הזה. מבולבלים? הגיוני למדי, בהתחשב בכך שלא נתתי שום דוגמה קונקרטית. אם כן, הנה דוגמה פשוטה, שאותה הציג נוגה אלון בהרצאתו שכבר דיברתי עליה כאן (בהקשר של אחד השימושים של סכימות התחייבות - "הטלת מטבע דרך הטלפון"): אם אריק רוצה להתחייב על 0, הוא מגריל שני מספרים ראשוניים בני 300 ספרות כל אחד, מכפיל אותם ומביא לבנץ. אם הוא רוצה להתחייב על 1 הוא מגריל שלושה ראשוניים בני 200 ספרות כל אחד ושולח לבנץ. מנקודת מבטו של בנץ, הוא תמיד מקבל מספר בן 600 ספרות שהפירוק שלו לא ידוע (ועד להודעה חדשה, פירוק לגורמים הוא דבר קשה מבחינה חישובית). כשאריק רוצה לפתוח את ההתחייבות שלו הוא פשוט שולח לבנץ את הפירוק של המספר. האם המחוייבות כאן מושלמת? והסודיות? הנה דוגמה נוספת, מורכבת יותר, שמבוססת על בעיה אחרת מתורת המספרים, ומתאפיינת במחוייבות מוחלטת אבל בסודיות חישובית בלבד, וגם כאן, כמו בדוגמה הקודמת, זה נכון רק תחת ההנחה שבעיה מסויימת (שכיום לא ידוע לה פתרון יעיל) היא אכן בלתי פתירה בזמן חישוב יעיל. הרעיון די פשוט. אנחנו מסתכלים על המספרים מ-1 ועד p-1 כאשר p הוא ראשוני כלשהו, עם פעולת כפל מודולו p - כלומר, כדי לכפול שני מספרים כופלים אותם "כרגיל" ואז מחלקים ב-p ומחזירים את השארית. כך למשל אם p הוא חמש, אז שלוש כפול ארבע יתן 2 - השארית של חלוקת 12 ב-5. כעת, הבעיה היא כזו: אם p הוא גדול יחסית, ואם \( g \) הוא מספר בתחום שלנו שבאמצעות העלאה שלו בחזקה (מודולו p) אפשר לקבל את כל המספרים מ-1 ועד p-1 - למספר שכזה קוראים "יוצר", מושג שמגיע מתורת החבורות - אז אם אנחנו יודעים את \( g \), ואם יש לנו את הערך של חזקה כלשהי שלו, דהיינו מתוך המשוואה \( g^x=y \) ידוע לנו גם \( y \), עדיין קשה לנו למצוא את המעריך של g, כלומר את \( x \). הבעיה הזו נקראת "בעיית הלוגריתם הדיסקרטי". לוגריתם כי לוגריתם פירושו בדיוק למצוא מעריך של חזקה ביחס לבסיס מסויים שנותן ערך נתון; דיסקרטי, כי אנחנו לא עובדים מעל המספרים הממשיים, שבהם מציאת לוגריתם אינה מסובכת, אלא מעל אוסף של מספרים טבעיים, ובהם העסק הרבה פחות קל. שתי הדוגמאות הללו נחמדות, אך הן אד-הוקיות מאוד במובן מסויים: הן מתבססות על קושי של בעיה "אמיתית" ספציפית, ואם הבעיה הזו תישבר, השיטה תלך לכל הרוחות. האם קיימת דרך "גנרית" לבנות סכמת התחייבות, שמתבססת על מעין "קופסאות שחורות" גנריות? התשובה היא כן, וזה בדיוק מה שהקריפטוגרפיה התיאורטית מתעסקת בו: ניתוח כללי וגנרי של מושגים כמו "בעיה קשה מבחינה קריפטוגרפית" (חשוב להבין שזה לא שם נרדף ל"בעיה קשה מבחינה חישובית", ואסביר בהמשך), שאחר כך מאפשרים לה לבנות, למשל, מערכות הצפנה שהן בטוחות באופן מוכח. מה הבעיה כאן? למשל, שכל עוד לא ידוע לנו ש-P שונה מ-NP, ייתכן שכל הקריפטוגרפיה התיאורטית מבוססת על מגדלים פורחים באוויר, שכן כל מה שהיא עוסקת בו פחות או יותר דורש את ההנחה ש-P שונה מ-NP. אחד המושגים הבסיסיים ביותר, אולי הבסיסי ביותר (יש סיבה מדוע הוא מופיע על כריכת ספרו של עודד גולדרייך שעוסק בקריפטוגרפיה תיאורטית) הוא פונקציה חד כיוונית - פונקציה \( f(x) \) שקל לחשב אותה, אבל קשה, בהינתן \( y=f(x) \) למצוא \( x^\prime \) כך ש-\( f(x^\prime)=y \). מהיצור הזה אפשר לבנות שלל כלים קריפטוגרפיים חביבים. בינתיים לא ארחיב כמעט על כלום, כי אני רוצה להציג דבר אחד ספציפי - סכימת התחייבות. לשם כך צריך פונקציה חד כיוונית שמקיימת תכונה נוספת - היא הפיכה (יותר במדוייק, היא פרמוטציה, אך לא ניכנס לזאת), כלומר לכל פלט יש קלט אחד ויחיד שנותן אותו. האם אתם כבר רואים את הסכימה מתחילה להיבנות? טוב, אז אפשר לפעול בדיוק כמו במקרה הלוגריתם הדיסקרטי - לבחור \( x \) שייצג את הסוד, לחשב את \( f(x) \), לשלוח לבנץ ושלום על ישראל. מה הבעיה? שבנץ אולי לא יצליח למצוא את ה-\( x \) שממנו התחלנו (הרי דרשנו ש-\( f \) היא חד כיוונית), אבל אולי הוא מסוגל להפיק אינפורמציה כלשהי על \( x \), למשל שהביט האחרון שלו הוא 0, או שסכום הביטים שלו הוא 1, וכדומה (זה שפונקציה היא חד כיוונית לא סותר זאת). מצד שני, חייבים לשלוח את \( f(x) \) אחרת זה יפגום במחוייבות המוחלטת של אריק; לכן הרעיון הוא לחפש מידע כלשהו - לצורך העניין, ביט בודד - שניתן להפיק מ-\( x \) בקלות, אך קשה להפיק אותו מ-\( f(x) \). למידע שכזה קוראים "פרדיקט ליבה" (Hard-core predicate). במילים אחרות, פרדיקט ליבה הוא פונקציה קלה לחישוב \( h(x) \) שמובטח לנו שקשה לחשב (במובן הקריפטוגרפי של המילה, שטרם הצגתי פורמלית) אם נתון לנו רק \( f(x) \) (בפרט, הפרדיקט הוא ביחס לפונקציה חד כיוונית ספציפית). בהינתן פונקציה חד כיוונית, ניתן באמצעות התחכמות מסויימת להפיק ממנה פונקציה חד כיוונית אחרת עם פרדיקט ליבה ספציפי, כך שאפשר להניח תמיד שיש לפונקציה החד כיוונית שאנו עובדים איתה פרדיקט ליבה. כצפוי, לא אכנס לפרטי ה"התחכמות" הזו כרגע. באמצעות פרדיקט הליבה הזה, סכמת ההתחייבות היא פשוטה: בהינתן סוד \( S \) של ביט בודד, אריק מגריל \( x \), מחשב את \( f(x) \) ואת פרדיקט הליבה \( h(x) \), שולח לבנץ את \( f(x) \) ואת \( S\oplus h(x) \) (כלומר, את הסוד כשהוא "מכוסה" באמצעות ערכו של פרדיקט הליבה), וזהו. כשאריק רוצה לפתוח את ההתחייבות, הוא פשוט שולח את \( x,S \); בנץ יחשב את \( f(x) \) ויוודא שזה אכן הערך שיש ברשותו, ואז יוכל לחשב את פרדיקט הליבה, להסיר את הכיסוי מה-S שאריק שלח לו קודם ולראות שהכל בסדר. יש לנו כאן מחוייבות מושלמת (כי \( f \) היא הפיכה, ולכן אין עוד מקור ל-\( f(x) \)), ומצד שני יש לנו בטיחות חישובית מוכחת, שכן זוהי בדיוק המהות של פרדיקט ליבה. אז מה העוקץ כאן? כמובן, שכיום לא ידוע על אף פונקציה שהיא חד כיוונית באופן מוכח, ואם נגלה אחת כזו, זה יגרור מייד ש-P שונה מ-NP (כי אם P=NP, אז כל דבר שקל לוידוא הוא קל לחישוב; מכיוון שקל לוודא ש-\( x \) ספציפי הוא המקור של \( f(x) \), פשוט על ידי חישוב \( f \), ינבע מכך ש-P=NP שקל גם למצוא \( x \) שכזה). מעניין? אני מתחייב להרחיב בהמשך בנושאי הקריפטוגרפיה התיאורטית, ובצורה יותר מסודרת מאשר כאן. בינתיים, אני מקווה שיצוץ מגלה עתידות שיפרסם באתר האינטרנט שלו התחייבות על איזה אירוע עתידי באמצעות מכפלה של שניים או שלושה ראשוניים; אלא שהמציאות עגומה הרבה יותר. מגידי עתידות רבים טורחים לפרסם תחזיות ספציפיות, שמרבית הזמן מתבדות. האם מישהו שם לכך לב, עם או בלי סכימות התחייבות?