קריפטוגרפים מעצבים גישה לפרטיות חיפוש כוללת | מגזין קוונטה

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

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

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

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

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

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

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

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

בעד דניאל וויץ, קריפטוגרף באוניברסיטת Northeastern ומחבר שותף של המאמר החדש, זה נראה טוב מכדי להיות אמיתי. בסביבות 2011, הוא התחיל לנסות להוכיח שתוכנית מסוג זה היא בלתי אפשרית. "הייתי משוכנע שאין סיכוי שאפשר לעשות את זה", אמר.

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

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

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

השיטה הזו לא הניבה שיפורים, והקבוצה התקרבה לוותר - עד שתהה האם הכלי הזה עשוי באמת לעבוד במקרה הנחשק של שרת יחיד. בחר פולינום בקפידה מספיק, הם ראו, ושרת בודד יוכל לעבד אותו מראש על סמך התוצאה של 2011 - מה שמניב את שיטת החיפוש המאובטחת והיעילה ש-Wichs הרהר במשך שנים. פתאום הם פתרו את הבעיה הקשה יותר.

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

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

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

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

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

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

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

Quanta עורכת סדרה של סקרים כדי לשרת טוב יותר את הקהל שלנו. קח את שלנו סקר קוראי מדעי המחשב ותוכלו לזכות בחינם Quanta סחורה.