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

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

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

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