Intro to Secret Sharing - מבוא לחלוקת סוד

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

התחום הכללי שנדבר עליו הוא קריפטוגרפיה (ולא בינה מלאכותית, כפי שנהוג בימינו:)), כותרת התזה היא "הסיבוכיות של סכמות לחלוקת סוד" - The Complexity of Secret Sharing Schemes, וכדי להבין במה מדובר כדאי להבין כמה דברים בנוגע לסיבוכיות, וכמה בנוגע לסכמות לחלוקת סוד.

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

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

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

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

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

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

גם כאן, קל יחסית לראות שהתכונות שרצינו מתקיימות:

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

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

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

שתי הערות למתקדמים: 

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

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

הנושא שלי - חלוקת סוד למבני גישה כלליים:

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

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

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

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

כמה קישורים מועילים:

חלוקת סוד וסיבוכיות בויקיפדיה

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

דף גוגל סקולר עם קישורים למאמרים שלי

בדף Research פה באתר ישנם קישורים להרצאות שנתתי בנושא