ושאינו יודע מה שאלו

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

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

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

איך עושים את זה?

טוב, הפתרון המיידי כנראה קופץ לרובכם לראש מייד - פשוט תבקש מהשרת את כל \( n \) הביטים ששמורים בו, וזהו; היריב לא לומד בכך כלום על זהות הביט \( i \) שאתם רוצים (הוא לומד, כמובן, שאתם רוצים ביט כלשהו מתוך ה-\( n \)-ים; אבל אם פניתם לשרת זה היה ברור מלכתחילה וזה לא משהו שאפשר לשפר). השיטה הזו היא בזבזנית למדי - סיבוכיות התקשורת שלה (כמות הביטים שנשלחים מצד לצד) היא \( O\left(n\right) \), וזו לא סיבוכיות טובה במיוחד (חשבו על סיטואציה שבה מסד הנתונים הוא בן כמה טרהבייטים של מידע ואנחנו צריכים לשאול כ-1,000 שאילתות ביום ויש עוד הרבה משתמשים כמונו). בפוסט הזה אני רוצה להציג שיפור שנובע מהקלה בכללי המשחק - נניח שיש יותר משרת אחד שבו מסד הנתונים מאוחסן, ונניח (וזו הנחה לא טריוויאלית) שאין קשר בין השרתים, דהיינו שהאויב המרושע שלנו מצותת רק לאחד מהם (במקרה הכי גרוע על כל שרת מתעלק אויב מרושע אחר, אבל כל אויב מרושע כזה יודע רק על מה שקורה בשרת “שלו”). האם עכשיו אפשר לשפר? התשובה היא שכן, משמעותית.

איך עושים את זה?

בואו נתחיל מהמקרה שבו יש לנו שני שרתים. הפתרון עדיין יהיה בעל סיבוכיות תקשורת \( O\left(n\right) \) אבל יהיה קל להכליל אותו אחר כך לפתרון שנותן שיפור משמעותי כשמספר השרתים גדול יותר. באופן די מפתיע, עכשיו יהיה די לנו בכך שכל שרת ישלח לנו ביט בודד, וסיבוכיות התקשורת תהיה טמונה בכך שאנחנו נצטרך לשלוח להם הרבה מידע. השיטה פשוטה: נגריל סדרה \( S_{0} \) של \( n \) ביטים כשהערך של כל ביט נבחר בהסתברות שווה בין 0 ו-1 ובאופן בלתי תלוי ביתר, נבנה סדרה \( S_{1} \) הזהה ל-\( S_{0} \) פרט לכך שהערך של הביט במקום ה-\( i \) הפוך, ונשלח את \( S_{0} \) לשרת הראשון ואת \( S_{1} \) לשרת השני. כל שרת יבצע פעולת XOR לביטים שהאינדקס שלהם בסדרה שהוא קיבל מסומן ב-1, וישלח חזרה את התוצאה. כשנקבל את התוצאה משני השרתים נבצע לה XOR, וגמרנו.

למי שלא מכיר, פעולת XOR בין שני ביטים (מלשון Exclusive Or) היא פעולה שלוקחת שני ביטים ומחזירה 1 רק אם ערכיהם שונים, ו-0 אם הם זהים (כלומר, \( 0\oplus0=0 \) ו-\( 1\oplus1=0 \) אבל \( 1\oplus0=0\oplus1=1 \)). הסיבה שבגללה השיטה עובדת היא שכל ביט \( j \) שאיננו הביט שרצינו או שמופיע ב-XOR של כל אחד משני השרתים ולכן שני המופעים שלו מבטלים זה את זה, או שהוא אינו מופיע כלל ולכן אינו משפיע. היחיד שבא לידי ביטוי באחד השרתים אבל לא בשני הוא הביט ה-\( i \). נסו זאת בעצמכם על מקרים פרטיים פשוטים (למשל \( n=3 \)) ותראו שזה עובד.

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

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

בואו נניח שיש לנו 4 שרתים. נניח גם, לצורך פשטות, ש-\( n \) הוא ריבוע של מספר טבעי כלשהו, כלומר \( n=k^{2} \) (תמיד אפשר להגדיל את \( n \) עד לריבוע הקרוב ביותר). כעת אפשר לחשוב על מסד הנתונים לא בתור שורה ארוכה של ביטים שלכל אחד אינדקס מ-1 ועד \( n \); במקום זה אפשר לחשוב על טבלה של ביטים שלכל אחד מהם שני אינדקסים - שורה ועמודה, ששניהם מספרים מ-1 ועד \( k \).

כעת לתעלול. נניח שאנחנו רוצים את הביט שבשורה ה-\( i \) ובעמודה ה-\( j \). אנחנו מגרילים שתי סדרות, \( S_{0}^{1},S_{0}^{2} \), בראשונה אנו הופכים את הביט שבמקום ה-\( i \), בשניה את הביט שבמקום ה-\( j \) ומקבלים שתי סדרות חדשות \( S_{1}^{1},S_{1}^{2} \). כעת אנו שולחים לשרת הראשון את \( \left(S_{0}^{1},S_{0}^{2}\right) \); לשרת השני את \( \left(S_{1}^{1},S_{0}^{2}\right) \); לשלישי את \( \left(S_{0}^{1},S_{1}^{2}\right) \) ולרביעי את \( \left(S_{1}^{1},S_{1}^{2}\right) \). אתם כבר מצליחים לנחש מה הם ישלחו בחזרה?

כל שרת שולח בחזרה את ה-XOR של הביטים שנמצאים בתת-הטבלה שמתקבלת אם מצטמצמים רק לאותן שורות ועמודות שהאינדקסים שלהן היו 1 בסדרה המוגרלת. כמקודם, כל ביט שאיננו במקום ה-\( \left(i,j\right) \) מופיע בפלטים ששולחים אלינו מספר זוגי של פעמים (לא בהכרח 4 או 0; נסו לבנות דוגמה שבה ביט שכזה נשלח בדיוק פעמיים), ואילו רק הביט במקום \( \left(i,j\right) \)נשלח פעם אחת בדיוק. לכן ביצוע XOR לכל הפלטים שקיבלנו מניב בדיוק את הביט שרצינו. הבטיחות נובעת מאליה מאותם שיקולים כמו קודם.

מה הסיבוכיות הפעם? ובכן, לכל שרת אנו שולחים שתי סדרות של \( k \) ביטים, ולכן בסך הכל אנו שולחים \( 8k \) ביטים. אלא שכזכור, \( k^{2}=n \) ולכן סיבוכיות התקשורת שלנו היא \( O\left(\sqrt{n}\right) \) - וזה שיפור משמעותי מאוד ביחס ל-\( n \). אם מסד הנתונים הוא בגודל של טרהבייט, אנחנו שולחים רק 8 מגהבייט; אני משער שתסכימו שזה שיפור משמעותי ביותר.

אבל למה לעצור בדו מימד? אפשר להכליל את השיטה גם ל-\( d \) ממדים. אם עומדים לרשותנו \( 2^{d} \) שרתים, אנו בונים שתי סדרות של סדרות \( \left(S_{0}^{1},\dots,S_{0}^{d}\right) \) ו-\( \left(S_{1}^{1},\dots,S_{1}^{d}\right) \), שולחים לשרתים את כל האפשרויות (כל האפשרויות לסדרה של \( d \) סדרות שהאיבר הראשון שלה הוא אחד מבין \( S_{0}^{1},S_{1}^{1} \), השני הוא אחד מבין \( S_{0}^{2},S_{1}^{2} \) וכן הלאה) ועושים XOR לתוצאה. כאן מתקיים \( n=k^{d} \) ולכן סיבוכיות התקשורת שלנו היא \( O\left(\sqrt[d]{n}\right) \). עם זאת, כדאי להתייחס גם ל-\( d \) כחלק מהפרמטר שמודד את הסיבוכיות, מכיוון שאי אפשר להגדיל את \( d \) באופן חופשי בלי מחיר - מספר השרתים קופץ משמעותית כשמגדילים את \( d \) (מוכפל פי שתיים בכל פעם שבה מגדילים את \( d \) ב-1) וכך גם סיבוכיות התקשורת גדולה - לכל שרת שולחים \( d\cdot k \) ביטים, ולכן בסך הכל הסיבוכיות היא \( O\left(d\cdot2^{d}\cdot\sqrt[d]{n}\right) \) ביטים.

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