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

פורמט ה-MP3 חולל מהפכה אדירה בכל הנוגע לתרבות ההאזנה למוזיקה. סוד הקסם שלו היה כיווץ שהקטין מאוד את קבצי המוזיקה, עד לסדר גודל של מגהבייט לדקה. זה הפך את שיתוף קבצי המוזיקה לדבר מעשי ונפוץ. המחיר היה פגיעה כלשהי באיכות המוזיקה - MP3 הוא מה שנקרא “פורמט lossy”. הכיווץ שהוא מציע מתבסס על זריקה לזבל של חלק מהמידע של הצליל - מידע שבתקווה אינו מורגש בפועל על ידי השומעים. כמובן שטענה נפוצה היא שגם בקידודים איכותיים יחסית של MP3 (כלומר, כאלו שזורקים לזבל רק מעט דברים) עדיין ניתן להרגיש בהבדל. האמנם? האם ניתן להבחין בין קובץ מוזיקה “רגיל” ובין קובץ שכווץ באמצעות MP3? איך?

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

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

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

הבה נעבור כעת למספרים פסאודו אקראיים. הזכרתי בפוסט הקודם כמה שימושים בסיסיים של מספרים שכאלו. השאלה המרכזית שעולה, כשמשתמשים במספרים פסאודו אקראיים ליישום כלשהו, היא “האם העובדה שאני משתמש במספרים פסאודו אקראיים ולא במספרים אקראיים באמת משנה משהו?”.

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

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

נניח שהתוכנית משתמשת במחולל האקראי האמיתי. מה ההסתברות שלה לפלוט 1? כמובן, 1/6. לכן אם אריץ אותה הרבה פעמים, אספור כמה פעמים קיבלתי 1 ואחלק במספר ההרצות הכולל, אקבל מספר שקרוב ל-1/6. לעומת זאת, אם התוכנית משתמשת במחולל של xkcd, היא תמיד תחזיר 1, ולכן כשאספור כמה פעמים קיבלתי 1 ואחלק במספר ההרצות הכולל, אקבל 1. ההבדלים כאן ברורים בצורה שאינה משתמעת לשתי פנים.

השאלה המתבקשת כאן היא “איך ידעת לכתוב דווקא את התוכנה הזו ולא, נניח, תוכנה שפולטת 1 אם היא הגרילה 3 או 2?”. מן הסתם התוכנית שכתבתי “תפורה” על המחולל הפסאודו אקראי של xkcd, במיוחד כדי להראות בעיה שיש בו (אם כי, שימו לב שהוא מחולל כה גרוע עד שגם התוכנית השניה הזו “תפיל” אותו). עבור מחוללים מסובכים יותר כלל לא ברור שאדע לכתוב תוכנית שיוצרת הבחנה בינו ובין התפלגות אקראית אמיתית; אבל זה שאני לא יודע לכתוב כזו לא אומר שלא קיימת תוכנית כזו. וזו בדיוק הדרישה ממחולל פסאודו אקראי “מתמטי” - שלא תהיה קיימת תוכנית שכזו.

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

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

בואו ניקח דוגמה ממש אווילית. נניח שאני מעביר למחולל קלט בן סיבית אחת - או 0, או 1. נניח שעל 0 הוא מחזיר 11 ועל 1 הוא מחזיר 01. זה אומר שיש לו בדיוק שני פלטים אפשריים מגודל 2, ובפרט שהפלט 00, למשל, לא יופיע אף פעם. זו הבעיה הבסיסית של מחולל פסאודו אקראי - מכיוון שהוא מבצע “ניפוח”, ולכל קלט אפשרי יש פלט אפשרי יחיד, הוא לא יכול לכסות את כל מרחב הפלטים האפשריים, ולכן אף פעם לא ייראה אקראי “לגמרי”. תמיד אפשר יהיה להריץ אותו על כל הקלטים האפשריים ולראות איזה ערך של פלט אף פעם לא יכול להתקבל, ואז להשתמש בכך כדי להראות שההתפלגות של המחולל היא לא אחידה “באמת” כי היא פוסחת על ערכים. על כן, מעמידים את המחולל במבחן רק עבור ערכים גדולים מספיק של קלט שעבורם לא ניתן לבצע חיפוש ממצה על כל מרחב הקלטים (ההגדרות הפורמליות קצת יותר עדינות ומחוכמות, כמובן; אבל יהיה קשה להסביר אותן כאן בלי הכנה מוקדמת נוספת).

אחת התוצאות המדהימות הראשונות הנוגעות למחוללים פסאודו אקראיים היא שדי במחולל שכל מה שהוא עושה הוא לנפח את הקלט בביט אחד (כלומר, אם הוא מקבל n ביטים כקלט, הוא מוציא n+1 ביטים כפלט - ביטים שיכולים להיראות שונה לגמרי מהקלט שהתקבל) כדי שניתן יהיה לבנות מחולל עם ניפוח פולינומי כלשהו (נניח, מוציא פלט שגדול פי 5 מהקלט). התוצאה הזו מצמצמת מאוד את ה”אתגר” שבבניית מחולל פסאודו אקראי - כל מה שצריך הוא ניפוח שמגדיל בביט אחד. עם זאת, זה לא עזר - עד היום לא ידוע ולו על מחולל פסאודו אקראי אחד. כמובן, קיימים מחוללים רבים שבהם משתמשים בפועל, גם ביישומים קריפטוגרפיים רגישים; אבל אין הוכחה לכך שהם אכן עונים על ההגדרה הפורמלית, ולכן שאלת קיומו של מחולל פסאודו אקראי נותרה בגדר תעלומה.

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

הסיבה לכך היא שאם P=NP, ניתן תמיד לבנות מבחין, עבור כל מחולל פסאודו אקראי, שפועל כמעט באופן זהה למבחין שבניתי עבור המחולל האווילי של xkcd. האבחנה הראשונה היא שתוכנית שמוציאה 1 על כל קלט שיכול להיווצר על ידי המחולל הפסאודו אקראי, ומוציאה 0 על קלטים אחרים, תמיד פולטת 1 כשהיא מופעלת על המחולל הפסאודו אקראי, אבל פולטת 1 בהסתברות שהיא לכל היותר חצי כאשר היא מופעלת על התפלגות אקראית “אמיתית”. הסיבה לכך היא, כמו שראינו כבר, שמחולל פסאודו אקראי מכסה לכל היותר חצי ממרחב הערכים האקראיים האפשריים (זה במקרה שבו הניפוח שלו הוא של ביט בודד; עבור ניפוח גדול יותר הוא מכסה עוד פחות). מכאן שתוכנית שכזו היא המבחין האולטימטיבי. השאלה היא רק מה זמן הריצה של תוכנית שכזו. כמובן, זה תלוי בצורה שבה התוכנית מבצעת את החישוב שלה.

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

כאן נכנסת לתמונה שאלת P=NP. כזכור, NP ניתנת לתיאור כאוסף כל שאלות הכן/לא שאולי קשה לפתור, אבל בהינתן “הוכחה” קצרה לנכונות טענה כלשהי, קל לבדוק אותה. זה מתאים בדיוק לתרחיש הנוכחי, כאשר השאלה היא “האם x יכל להתקבל כפלט של המחולל?” וה”הוכחה” היא פשוט הערך שיש להזין למחולל כדי לקבל את x (החישוב שמבצע המחולל הוא יעיל, כך שהבדיקה ניתנת לביצוע ביעילות). כעת, אם P=NP, נובע מכך שכל שאלת כן/לא שמקיימת את התכונה “קל לבדוק הוכחות”, מקיימת גם את התכונה “קל לפתור”. כלומר, בהינתן x יהיה קל (מבחינה חישובית) לקבוע האם הוא יכול להתקבל כפלט של המחולל או לא. איך? שאלה טובה - זה מה שהוכחה ש-P=NP תצטרך להסביר - אבל אפשר. ואם אפשר, אז קיים מבחין פולינומי עבור המחולל, ולכן הוא לא עונה להגדרה הפורמלית. סוף הסיפור.

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

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

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

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

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