ארכיון פוסטים שפורסמו בחודש אוגוסט 2008

שיתוף חידות שיתוף (ועוד העלאה באוב) - הפתרונות

שישי, 22 באוגוסט 2008

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שייך לנושא משחקים וחידות מתמטיות | 6 תגובות »

שיתוף חידות שיתוף (ועוד העלאה באוב)

שני, 18 באוגוסט 2008

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

ניקח גרף מלא בעל n קודקודים - בגרף מלא הכוונה לגרף שבין כל שני צמתים בו יש קשת. השחקנים שלנו במשחק שיתוף הסוד ייוצגו על ידי קשתות הגרף (כלומר, מלכתחילה אנחנו מגבילים את עצמנו רק לקבוצות של שחקנים מגדלים מאוד מסויימים - אילו?). כעת נגדיר שני מבני גישה שונים:

  1. נסמן שני צמתים בגרף בתור s,t. קבוצת שחקנים מסוגלת לשחזר את הסוד אם ורק אם קיים מסלול מ-s אל t שעובר רק דרך קשתות של חברי הקבוצה.
  2. קבוצת שחקנים מסוגלת לשחזר את הסוד אם ורק אם קבוצת הקשתות שלה לא משרה גרף דו-צדדי (גרף דו-צדדי הוא גרף שניתן לחלק את צמתיו לשתי קבוצות, כך שקשתות עוברות רק בין איברים מקבוצה אחת לשניה, ולא “בתוך” אף אחת מהקבוצות).

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

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

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

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

המטרה: שלכל היותר מספר סופי של אנשים יטעו בתשובה שיתנו.

בהצלחה!”

בהצלחה.

שייך לנושא משחקים וחידות מתמטיות | 8 תגובות »

שיתוף, זה כל הסוד

שבת, 16 באוגוסט 2008

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

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

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

הבשורות הטובות של התחום הן שאפשר לעשות זאת, ואפשר לעשות זאת בקלות, ואפשר לעשות זאת בצורה שבה יש בטיחות מושלמת (להבדיל מבטיחות “חישובית” דוגמת זו שדיברתי עליה בפוסט שעסק בסכימות התחייבות). הצורה שבה עושים זאת היא פשוטה למדי וזהה ברעיון לשיטה של צופן פנקס חד פעמי. נניח שהסוד שלנו הוא ביט בודד S (כשיש סודות יותר מורכבים, אפשר לחלק כל ביט בנפרד, כך שהכלליות לא נפגעת). נניח שאנחנו רוצים לחלק את הסוד ל-N “שחקנים” שונים; אנחנו מגרילים בהתפלגות אחידה S_1,\dots,S_n בעלי התכונה הנאה ש-S_1+\dots+S_n=S (החיבור הוא מודולו 2, כלומר 1 ועוד 1 שווה 0); ניתן לבצע הגרלה כזו, למשל, על ידי הגרלת כל הערכים בהסתברות שווה ל-0 ול-1 פרט לאחרון (ואז הוא נקבע באופן יחיד בצורה שמבטיחה שהמשוואה תתקיים). כעת, השחקן מספר i יקבל את החלק S_i. ברור שאם כל השחקנים מתאגדים יחד הם יכולים לשחזר את הסוד המקורי, פשוט על ידי חיבור כל החלקים שלהם; לעומת זאת, אם כל השחקנים פרט לאחד מתאגדים יחד, החלקים שלהם לא מספקים שום אינפורמציה. הסיבה לכך היא שהסבירות שיש לשחקן הנוסף 0 או 1 היא בדיוק 50-50 (למה?). מכאן שבהסתברות של 50%, הסוד שהם מנסים לשחזר הוא 0, ובהסתברות של 50% הוא 1 - אבל זה בעצם לא אומר שום דבר שהם לא ידעו כבר קודם, ובפרט זה אפילו לא רומז מה הסוד עשוי להיות.

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

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

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

ובכן, אנחנו מחלקים את הסוד ל-m חלקים בשיטה שהצגנו קודם, כלומר מוצאים S_1,\dots,S_m שסכומם שווה לסוד; כעת, לכל “חתיכה” של הסוד S_i אנחנו מחלקים אותה לכל שחקן שלא נמצא בקבוצה T_i. זה הכל. עד כדי כך פשוט.

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

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

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

נניח שהסף הוא בסביבות חצי n. כמה קבוצות לא משחזרות מקסימליות יהיו? בסביבות חצי n פחות 1, כלומר בסביבות חצי n. כמה קבוצות שחקנים מגודל כזה יש? {n\choose n/2}\approx 2^{n/2}.לא אכנס כאן לפירוט של הקירוב האחרון - זהו חסם תחתון סטנדרטי למקדמי הבינום, ולא בזה אני רוצה להתעסק כאן. הנקודה היא שמספר הקבוצות המקסימליות הוא אקספוננציאלי ב-n - גדול מאוד. כאן נכנסת לתמונה שיטת שמיר ומציעה פתרון שדורש הרבה פחות חלקים מאשר מספר הקבוצות המקסימליות. ה”מחיר” הוא מתמטיקה מעט יותר מורכבת (אך עדיין אלמנטרית יחסית).

הרעיון הבסיסי הוא לעסוק בפולינומים. פולינומים הם פונקציות מעניינות למדי. מצד אחד, הם פשוטים מאוד, עד כדי כך שמעט מאוד דגימות שלהם מאפשרות לשחזר אותם במדוייק; מצד שני, אם לא משיגים את המספר הדרוש של דגימות, קשה להגיד עליהם משהו - וכשהפולינומים מוגדרים לא מעל המספרים הממשיים אלא מעל שדות סופיים, ה”קשה” הופך ל”בלתי אפשרי”. כדי לא לסבך את החיים לא אכנס כעת לדיון בשדות סופיים - זה ראוי לפוסט בפני עצמו - אלא אתמקד בפולינומים ומה שעושים איתם. מה שחשוב ב”שדות סופיים” הוא שאפשר לבצע בהם כל פעולה אריתמטית שעושים בממשיים, ושיש בהם מספר סופי ומוגבל של איברים, כך שניתן להגריל איברים מתוך השדה באקראי ובהתפלגות אחידה.
פולינום הוא פונקציה מהצורה p(x)=\sum_{i=0}^n a_ix^i, כאשר a_0,a_1,\dots,a_n נקראים “מקדמי הפולינום”, ומניחים ש-a_n\ne 0 (אחרת אפשר היה להשמיט אותו מהתיאור לחלוטין). למספר n - החזקה הגבוהה ביותר של x שעבורו המקדם אינו אפס - קוראים הדרגה של הפולינום.

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

בעתיד אולי אכתוב פוסט על אינטרפולציה של פולינומים שבו אסביר יותר ברצינות איך מוצאים את הפולינום (זה פשוט) ולמה הכמות הזו של ערכים מבטיחה שיהיה בדיוק פולינום יחיד (מדרגה n או קטנה ממנה; מדרגות גדולות יותר יש הרבה פולינומים שמתאימים ל”דגימות” הללו). לעת עתה אנו מעוניינים רק בשימוש, אבל אני מניח שגם השימוש כבר די ברור. הרעיון הוא “להחביא” את הסוד בתוך מקדם של פולינום מדרגה k-1, ששאר מקדמיו נבחרים באקראי (נניח, p(x)=S+\sum_{i=1}^{k-1} a_ix^i, כלומר הסוד מושם בתור “המקדם החופשי” - המקדם של x^0). כעת מחלקים לשחקנים דגימות של הפולינום בערכים שונים ומשונים (למשל, לשחקן מספר i אפשר לחלק את הדגימה S_i=p(i)). אם k שחקנים יתאספו יחד ויחברו את הדגימות שלהם, הם יצליחו לשחזר את הפולינום במדוייק, ולכן על ידי חישוב S(0) הם ימצאו את הסוד; פחות שחקנים לא יוכלו לשחזר שום מידע על הסוד כי מהנתונים שיהיו בידיהם תהיה בדיוק אותה סבירות לאוסף גדול של פולינומים, שהמקדם החופשי שלהם הוא כל דבר שרק תרצו.

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

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

בפועל, אפשר להשתמש בשיטה של שמיר גם כאן. הרעיון הוא כזה: מחלקים את הסוד ל-18 חלקים, עם דרישת סף של 6 חלקים (כלומר, כל מי שיש לו שישה חלקים מתוך ה-18 יוכל לשחזר). כעת מחלקים 6 חלקים למנכ”ל, 3 חלקים לכל אחד מהסגנים, ו-2 חלקים לכל מנהל זוטר. אם כן, המנכ”ל יכול לשחזר לבד, כי יש לו 6 חלקים, וכך גם זוג הסגנים (כי יש להם יחד 3+3=6 חלקים) והמנהלים הזוטרים (2+2+2=6) וגם סגן ושני מנהלים זוטרים (3+2+2=7) אבל כל קבוצה קטנה יותר לא תעבוד (למשל, לסגן ולמנהל זוטר אחד יש יחדיו רק 5 חלקים - לא מספיק). אם כן, מבני סף הם יותר מועילים ממה שאולי נראה מלכתחילה, אך בכל זאת חשוב להדגיש שהם אינם כלליים לחלוטין.

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

שייך לנושא קריפטולוגיה | תגובה אחת »

שאלות ותשובות - מקבץ מס’ 4

חמישי, 14 באוגוסט 2008

ככל שמתרבים הפוסטים שלי, גדל מאגר המילים שמוביל לאתר הזה, ובפרט גדל מספר האומללים שתועים ומגיעים אליו עם שאלות שאין לי עליהן תשובה קיימת. הנה כמה נסיונות תיקון חדשים:
1) “הוכחה שפונקציה a*b היא חד חד ערכית” - כמובן שהטענה לא נכונה אם מרשים גם ל-a וגם ל-b להיות משתנים (למשל, 24=4*6=2*12). אם “מקפיאים” אחד מהם (נניח את b), התוצאה מתקבלת באמצעות שימוש בדיסטריביוטיביות ובכך שניתן “לצמצם”:

a_1b=a_2b\Rightarrow(a_1-a_2)b=0\Rightarrow a_1-a_2=0\Rightarrow a_1=a_2

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

2) “מספר העלים בעץ הוא לפחות” - בעץ “כללי” יכול להיות רק עלה בודד - אם העץ הוא “שרוך”. אם לכל צומת פנימי בעץ יש לפחות שני בנים, ויש בו n צמתים, אז יש בו בדיוק \frac{n}{2} (המספר מעוגל כלפי מעלה) עלים. אפשר להוכיח זאת באינדוקציה: עץ בעל צומת בודד הוא גם בעל עלה בודד (חצי מעוגל כלפי מעלה). לכל עלה שנהפוך לצומת פנימי אנחנו חייבים להוסיף לו שני בנים (עלים, עד שנוסיף גם להם בנים) ולכן קיבלנו שני עלים חדשים תמורת חיסול של עלה אחר - דהיינו, לכל שני צמתים שהוספנו לעץ, קיבלנו עלייה של 1 במספר העלים שבו. תרגיל: לנסות להכליל עבור עצים שבהם לכל צומת פנימי יש עוד יותר בנים. אגב, לאחר שכתבתי את התשובה לשאלה הזו צצה שאלה נוספת - “עץ בינארי מספר הצמתים שדרגתם 2 קטן ב-1 ממספר ה”. אני משער שה”ה” הוא מספר העלים - ושוב, שגם כותב השאלה הזו מניח שלכל צומת יש או שני בנים או כלום.

3) “קשר בין כפל וחילוק במתמטיקה” - נהוג לחשוב על חילוק בתור “הפעולה ההפוכה לכפל”, וניתן להציג זאת כך: החלוקה של c ב-b היא מספר כלשהו a שמקיים את התכונה לפיה אם כופלים את b ב-a מקבלים בדיוק את c. באופן קצת יותר פורמלי, נהוג להגדיר לכל מספר a את המספר ההופכי לו, a^{-1} - המספר שמקיים את התכונה aa^{-1}=1. בגישה זו, חלוקה ב-a מוגדרת ככפל ב-a^{-1}. זה גם מסביר מדוע לא ניתן לחלק באפס - אין לו הופכי, כי אפס כפול כל דבר הוא אפס (ובפרט, אי אפשר לקבל את 1 על ידי כפל משהו באפס).

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

5) “קובץ שגודלו 2k מכיל 2048 תווים” - התשובה חיובית. יחידת המידע הבסיסית ביותר במחשב היא הביט (Bit - סיבית בעברית, אך איני אוהב גם את העברות הזה). ביט מסוגל להחזיק או 0 או 1, ובאמצעות שני ערכים אלו קל לייצג כל ערך אחר שהוא בר-תרגום פשוט למספרים טבעיים. עם זאת, למעבדים לא נוח לעבוד עם סיביות בודדות ויותר קל לעבוד עם קבוצות של ביטים; מסיבות היסטוריות התגלגל שהקבוצה ה”מעניינת” הראשונה היא בגודל 8 ביטים, וקבוצה שכזו נקראת בייט (Byte, ובעברית בית). הבייט הוא יחידת המידה המקובלת לגודל של קובץ. במקרה או שלא במקרה, הטיפוס הבסיסי לתו, שנמצא ברוב שפות התכנות (Char, מלשון Character) תופס בייט בודד (דהיינו, ממש נדרש בסטנדרט של השפה שזה יהיה גודלו).באמצעות בייט אחד ניתן לייצג מספרים בטווח 0-255, כך שזה מספיק כדי לתפוס תווים מעניינים רבים (אבל לא הכל - ולכן יש שיטות קידוד, למשל Unicode, שבהם חלק מהתווים דורשים יותר מבייט אחד).

כעת, מדידת גודל קבצים במחשב נעשית בצורה שעשויה קצת להטעות. מסיבות שונות ומשונות של יעילות, נוח לעבוד בעיקר עם חזקות של 2 במחשב. לכן כשמודדים גודל של קובץ, הקיצורים מתייחסים לחזקות של 2 ולא של 10. כך “k”, שמייצג קילו, אין פירושו “1,000 בייט” אלא “1,024 בייט” - זוהי החזקה של 2 שהיא קרובה ביותר למספר 1,000. בדומה, גם “מגה בייט” איננו 1,000 קילובייט, אלא 1,024 קילובייט (כמה זה יוצא בבייטים?) וכן הלאה. לכן קובץ שגודלו 2k מכיל 2,048 תווים (עם זאת, כמובן שאין הכרח שתוכן הקובץ יהיה תווים - קובץ תמונה, למשל, מכיל מידע על איזה צבע צריך להופיע איפה - אבל אפשר לחשוב על המידע הזה גם בתור תווים, רק שהם לא יצטרפו לטקסט בעל משמעות באנגלית).

6) “לוח כפל חבורה מסדר 5″ - ראשית, יש רק חבורה אחת כזו, כי 5 הוא מספר ראשוני: על פי משפט לגראנז’, סדר של איבר בחבורה חייב לחלק את סדר החבורה; לכן הסדר של כל איבר שאיננו היחידה חייב להיות 5, כי לא קיים מספר בין 1 ו-5 שמחלק את 5. מכאן שחבורה מסדר 5 חייבת להיות ציקלית, ויש רק אחת כזו. כעת קל יחסית לתאר את לוח הכפל שלה: מסמנים כל שורה וכל עמודה בתור החזקה של אחד מהיוצרים (כלומר, בתור a^0, a^1, \dots, a^4) ומה שיופיע בתוך התא המתאים בטבלה יהיה החזקה שמתאימה לחיבור מודולו 5 (למשל, בתא של a^3 ו-a^4 יופיע a^2).

7) “כל מספר שהמעריך שלו הוא אפס שווה לאחד” - כלומר x^0=1 לכל x. זו לא טענה שאפשר להוכיח, אלא הגדרה; אנחנו הרי מתחילים בכך שאנו מגדירים חזקות רק למעריכים שהם טבעיים שונים מאפס (x^1=x, x^{k+1}=x^k\cdot x). לכן אם מדברים על מעריכים אחרים, צריך להגדיר אותם, לרוב באמצעות מה שכבר הגדרנו, ועם נסיון לשמור על אחידות מסויימת. במקרה של מעריך אפס, אנחנו מנסים לשמור על כלל החזקות הידוע \frac{x^a}{x^b}=x^{a-b} שתקף כל עוד a>b והם טבעיים; אם הם היו שווים, אז היינו מקבלים בצורה “פורמלית” את המשוואה 1=\frac{x^a}{x^a}=x^{a-a}=x^0, כך שאנחנו נדחפים להגדרה של החזקה בתור 1. מתי בכל זאת זה לא עובד? כשמדברים על החזקה של 0, כי הרי לא ניתן לחלק באפס ולכן המוטיבציה הקודמת לא ממש תקפה. לכן לפעמים משאירים את הביטוי 0^0 בלתי מוגדר. מצד שני, לפעמים נוח להגדיר אותו פורמלית בתור 0^0=1 למרות זאת - למשל, כשרוצים לכתוב את נוסחת הבינום של ניוטון ולהרשות לאחד המחוברים להיות 0.

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

9) “בכמה דרכים ניתן להציג את המספר 19 כסכום” - כמובן שהשאלה  לא מוגדרת היטב: סכום של מה? אם, למשל, רוצים סכום של מספרים שלמים, אז יש אינסוף דרכים להציג אותו ככזה (19 ועוד 0; 20 ועוד מינוס 1; 21 ועוד מינוס 2, וכו’). אם רוצים סכום של שני ראשוניים (למה? לא יודע) אז יש אחת: 17+2. אבל מה שעולה לי לראש כשמדברים על סכום שכזה הוא פשוט סכום של מספרים טבעיים. כך למשל 19 הוא אפשרות אחת להציג את 19 כסכום; אפשרות אחרת היא 1+18; עוד אפשרות היא 5+5+5+3, וכן הלאה. באופן כללי, בהינתן מספר טבעי, הבעיה של מציאת מספר החלוקות שלו - מספר הדרכים להציג אותו כסכום מספרים טבעיים - היא בעיה קשה בקומבינטוריקה ולא ידוע לה פתרון מוצלח, לא כל שכן נוסחה. עבור 19 יש עוד מספר קטן יחסית של חלוקות, אז אפילו בשיטה של “Brute force” אפשר לגלות את התשובה: 490.

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

11) “טקסטים של הצגות” - זו בדיחה דלוחה, ובכל זאת: אני ממליץ בתור התחלה על הטקסט “Linear Representations of Finite Groups” של Serre.

שייך לנושא שאלות ותשובות | 10 תגובות »

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

שני, 04 באוגוסט 2008

יצא לי פעם לראות קטע משעשע מאוד מתוכנית האירוח של יהורם גאון. הוא אירח את ליאור מנור, והלה ניבא איזו נבואה עתידית של משהו שאין לו עליו שליטה ושם את הנבואה בכספת באחריות מפיקי התוכנית. לאחר זמן מה, שוב בתוכנית ולאחר שתוצאת האירוע המנובא הייתה ידועה לכל, פתח גאון את הכספת והוציא את הנבואה, שהתגלתה כנכונה לחלוטין, כמובן. מי שהראה לי את הוידאו השתעשע בעיקר ממה שהיה גלוי לחלוטין כאשר גאון פתח את הכספת - הקוד שלה היה 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 שכזה).

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

שייך לנושא קריפטולוגיה | 3 תגובות »