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

מדוע שיתוף רשימות עלול לסכן פרטיות

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

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

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

דליפות חבויות בשיטות מהירות מוקדמות

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

נעלת פריטים מאחורי הסוות אקראיות

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

הקטנת העלות באמצעות מבנה נתונים חכם יותר

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

מה שהניסויים מראים במציאות

כדי לבחון את הרעיונות שלהם, המחברים מימשו את הפרוטוקול והשוו אותו לעיצוב המתקדם הקיים תחת אותם מטרות פרטיות מחמירות. במגוון רחב של גדלי רשימות ותנאי רשת, השיטה שלהם צמצמה באופן עקבי את התקשורת בכ‑1.1 עד 3 פעמים והאיצה את זמן הריצה בכ‑כ‑1.0 עד 1.7 פעמים. החשוב הוא שהשיפורים הללו נשמרים גם לאחר הוספת השכבה הקריפטוגרפית הנוספת שמונעת דליפה מבוססת גיבוב — סוגיית אבטחה שדרישות היעילות הקודמות התעלמו ממנה. התוצאות מרמזות שהגנה חזקה יותר לא חייבת לבוא עם מחיר ביצועים גבוה.

למה זה חשוב לשיתוף נתונים בעולם האמיתי

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

ציטוט: Liu, Q., Bae, J. & Lee, JW. Towards an improved efficient leakage-resilient enhanced private set union. Sci Rep 16, 10134 (2026). https://doi.org/10.1038/s41598-026-40531-5

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