העברה עלומה

בקריפטוגרפיה, העברה עלומה (Oblivious Transfer, בראשי תיבות OT) הוא פרוטוקול קריפטוגרפי המאפשר לשחקן אחד לשלוח סוד אחד מתוך כמה סודות לשחקן שני, באופן שמה שהתקבל בצד השני נותר נעלם מידיעתו. ומצד שני השחקן השני מקבל בדיוק סוד אחד בלבד מתוכם. הפרוטוקול הראשון להעברה עלומה, שהומצא על ידי פרופסור מיכאל רבין דן בסוגיה איך להעביר סוד אחד לצד השני באופן שהשולח יודע אם הוא התקבל בצד השני בהסתברות 1/2 בלבד, כלומר הדבר "נעלם" מידיעתו האם המידע התקבל או לא ומכאן שם הפרוטוקול.

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

היסטוריה

במאמר מאת סטיבן ויסנר (Stephen Wiesner), שפורסם ב-1983 (אף על פי שנכתב ב-1968), מתואר מושג קידוד מזווג (Conjugate coding) ככלי אלגברי ליישום קוד תיקון שגיאות קוונטי. מה שהיווה בסיס ל-CSS - אלגוריתם תיקון שגיאות קוונטי שפותח על ידי שור וקלדרבנק ב-1995. הרעיון של ויזנר שקול להעברה עלומה 1 מתוך 2 המתוארת להלן, אם כי ויזנר עצמו לא התייחס בזמנו לנושא מהיבט קריפטוגרפי. מאוחר יותר עלה רעיון ניצול מושג זה לצורכי קריפטוגרפיה ואומץ השם "העברה עלומה".

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

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

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

הגדרה כללית

פרוטוקול העברה עלומה מתחלק לשלושה סוגים:

• העברה עלומה. שחקן אחד מעביר סוד אחד לשחקן השני באופן כזה שהשולח אינו יודע האם הסוד התקבל בצד השני בהסתברות טובה מחצי באופן משמעותי.
• העברה עלומה 1 מתוך 2. שחקן אחד מחזיק בשני סודות $x_{0},x_{1}$ והוא שולח אותם לשחקן השני שמחזיק בסיבית אחת $b\in \{0,1\}$. השחקן השני מקבל את הסוד $x_{b}$ בלבד כשהסוד השני נעלם מידיעתו לגמרי, בעוד שהשולח אינו יודע מהו הסוד שהתקבל משניהם בהסתברות גבוהה מחצי באופן משמעותי. במילים אחרות הוא אינו יודע מהו $b$.
• העברה עלומה 1 מתוך $\mathbf {n}$. השחקן הראשון מחזיק ב-$n$ סודות $\{x_{1},x_{2},x_{3},...,x_{n}\}$ ואילו השחקן השני מחזיק בשלם כלשהו $m\leq n$ והוא רוצה ללמוד את הסוד $x_{m}$. השחקן הראשון שולח את הסודות באופן כזה שהמקבל רואה רק את הסוד $x_{m}$ וכל יתר הסודות נעלמים מעיניו ואילו השולח אינו יודע איזה מהסודות נחשף, כלומר $m$ נותר נעלם מידיעתו.

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

פרוטוקול העברה עלומה מתוך תמורה חד-כיוונית

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

קלט השולח: $x_{0},x_{1}\in \{0,1\}$.

קלט המקבל: $i\in \{0,1\}$.

1. השולח בוחר תמורה חד-כיוונית $f$ מתוך משפחה של תמורות חד-כיווניות $\{0,1\}^{n}\rightarrow \{0,1\}^{n}$ ושולח אותה למקבל (במילים אחרות הוא מכין הצפנת מפתח ציבורי כמו RSA עם מפתח פרטי ומפתח ציבורי מתאים ושולח את המפתח הציבורי).
2. המקבל בוחר באקראי את $x_{1-i}$ ב-$\{0,1\}^{n}$ (שלם אקראי באורך $n$ סיביות), מחשב את: $x_{i}=f(w)$ כאשר $w$ נבחר באקראי מתוך $\{0,1\}^{n}$ ושולח את $x_{0},x_{1}$ בחזרה.
3. השולח מגריל שני שלמים $r_{0},r_{1}\leftarrow _{R}\{0,1\}^{n}$, מחשב את $w_{i}=f^{-1}(x_{i})$ ושולח למקבל את $r_{i},r_{i}\odot w_{i}\oplus x_{i}$ עבור $i=0,1$.

כאשר $\oplus$ ו-$\odot$ הם פעולות החיבור והכפל בחבורה. כעת המקבל יוכל לחשב את הסוד שלו.

פרוטוקול העברה עלומה של רבין

בוב ואליס המשתתפים בפרוטוקול מחזיקים כל אחד בסודות $\ s_{B}$ ו-$\ s_{A}$ בהתאמה, אותם הם מעוניינים להחליף ביניהם. הסודות יכולים להיות, למשל, סיסמת גישה לקובץ מוצפן. ההנחה היא שאליס ובוב לא ינסו לעשות שימוש בסוד שהם קיבלו מבלי שהם יהיו בטוחים בוודאות שהסוד נכון (למשל, אפשר להניח שבמקרה של טעות בהקלדת קוד הגישה לקובץ המוצפן, הקובץ יימחק). ולמען הפשטות נניח שהסוד של אליס ובוב הוא סיבית אחת. פרוטוקול EOS של רבין מסתמך על הצפנת מפתח פומבי ועל כן מניח כי ברשות אליס ובוב מפתחות פומביים $\ k_{A}$ ו-$\ k_{B}$ בהתאמה איתם הם יכולים להשתמש הן להצפנה והן לחתימה דיגיטלית. וכן כל מסרי הפרוטוקול חתומים באמצעות מפתח החתימה הפרטי של כל אחד מהם בהתאמה.

מהלכי הפרוטוקול

1. אליס ובוב בוחרים כל אחד בנפרד זוג ראשוניים שונים $\ p_{1},q_{1}$ וכן $\ p_{2},q_{2}$ ומכינים מפתחות הצפנה חד פעמיים $\ n_{A}=p_{1}q_{1}$ וכן $\ n_{B}=p_{2}q_{2}$. אליס שולחת לבוב מסר חתום המכיל את $\ n_{A}$ ובוב מחזיר במסר חתום משלו המכיל $\ n_{B}$.
2. בוב בוחר מספר שלם אקראי $\ x$ כאשר $\ x\leq n_{A}$ ומחשב את $\ c=x^{2}{\mbox{ mod }}n_{A}$ ושולח לאליס את $\ c$ ואת: $\ E_{k_{B}}(x)$ שהוא הצפנה של המספר האקראי שבחר באמצעות המפתח הפומבי שלו $\ k_{B}$.
3. אליס מחשבת את $\ x_{1}$ המקיים $\ x_{1}^{2}\equiv c\ ({\mbox{mod }}n)$ (כלומר אחד מהשורשים הריבועיים של $\ c$ מודולו $\ n_{A}$) ושולחת לבוב מסר חתום המכיל את $\ x_{1}$.
4. בוב מחשב את $\ d={\mbox{gcd}}(x-x_{1},n_{A})$ (הפונקציה gcd מייצגת מחלק משותף מקסימלי). בהסתברות של חצי $\ d=p$ או $\ d=q$, על כן בהסתברות של חצי בוב מצליח לפרק לגורמים את $\ n_{A}$ ובמידה וכן יוכל לפענח את המסר המוצפן המכיל את $\ s_{A}$. בשלב זה אליס אינה יכולה לדעת האם בוב הצליח לגלות את הגורמים הראשוניים של $\ n_{A}$ כיוון שהיא אינה יודעת מהו $\ x$ שבוב שלח במסר המוצפן בשלב קודם.
5. שלושת המהלכים האחרונים מבוצעים גם בכיוון ההפוך, כך שבסיכומם ההסתברות שאליס תצליח לפרק את $\ n_{B}$ לגורמים היא $\ 1/2$ בעוד שבוב אינו יודע האם הצליחה לעשות זאת אם לאו.

נגדיר כעת את הסיבית $\ v_{B}$ כדלהלן:

$\ v_{B}=\left\{{\begin{matrix}0,&{\mbox{if gcd}}(x-x_{1},n_{A})=p\\1,&{\mbox{otherwise}}\end{matrix}}\right.$

כלומר הסיבית $\ v_{B}$ מייצגת את ידיעתו של בוב לגבי הגורמים הראשוניים של $\ n_{A}$ וכן להפך הסיבית $\ v_{A}$ מייצגת את ידיעתה של אליס לגבי הגורמים הראשוניים של המודולוס $\ n_{B}$.

1. כזכור סודם של אליס ובוב הוא סיבית אחת בלבד. בוב מחשב את $\ e_{B}=s_{B}\oplus v_{B}$ ושולח לאליס את $\ e_{B}$. $\ e_{B}$ מייצג XOR של סודו $\ s_{B}$ עם $\ v_{B}$ המייצג את ידיעתו באשר לגורמים הראשוניים של $\ n_{A}$. ידיעת $\ e_{B}$ אינה תורמת לאליס דבר על מנת ללמוד את סודו של בוב, כיוון שהיא אינה יודעת האם בוב אכן גילה את הגורמים הראשוניים של $\ n_{A}$. אליס פועלת באותה הדרך ושולחת לבוב את $\ e_{A}$ הנגזר מ-XOR של סודה $\ s_{A}$ עם $\ v_{A}$.

1. בשלב האחרון בפרוטוקול, אליס מצפינה מסר אקראי כלשהו $\ m_{A}$ כאשר סיבית אחת בו היא הסוד שלה $\ s_{A}$ באמצעות הצפנת מפתח פומבי כלשהי: $\ d_{A}=E_{n_{A}}(m_{A})$, היא יכולה לעשות זאת למשל על ידי הצפנת רבין: $\ d_{A}=m_{A}^{2}{\mbox{ mod }}n_{A}$, במידה וניתן יהיה לזהות את התוצאה הנכונה מבין ארבע התוצאות האפשריות (למשל על ידי תחילית מוסכמת). אליס שולחת את $\ d_{A}$ לבוב במסר חתום. ובוב פועל בדרך דומה ושולח לאליס הצפנה של מסר אקראי המכיל בתוכו את סיבית הסוד שלו.

הפרוטוקול המתואר מספק מענה לבעיית החלפת סוד האמורה בכך שההסתברות שהצדדים יקבלו את סודם היא $\ 1/4$. ברור שאם אחד מהצדדים יחדל מהשתתפות בפרוטוקול לפני שמתבצע השלב האחרון, אף אחד מהם לא יוכל ללמוד מאומה בקשר לסודו של האחר. אם $\ v_{B}=0$ פירושו של דבר שבוב יכול לפענח את $\ d_{A}$ כיוון שהגורמים הראשוניים של $\ n_{A}$ ידועים לו, אחרת תהיה זו בעיה קשה, כידוע. אם בוב ינסה להשתמש בסוד שקיבל, אליס תדע מכך (שוב ההנחה היא שבוב יעשה זאת רק אם יהיה משוכנע מעל לכל ספק שהסוד $\ s_{A}$ אכן ידוע לו) מה שיאפשר לאליס להסיק מכך מידית מהו הסוד $\ s_{B}$ כיוון ש-$\ e_{B}=s_{B}\oplus v_{B}$. הדברים האמורים נכונים גם להפך. עצם הניסיון לעשות שימוש בסוד מהווה הוכחה לידיעת הסוד המקביל בצד השני. ההסתברות במקרה שהפרוטוקול בוצע בשלמותו שאף אחד מהם לא ידע את הסוד של השני הוא $\ (1/2)^{2}$.

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

פרוטוקול העברה עלומה 1 מתוך 2

בפרוטוקול העברה עלומה 1 מתוך 2 שהוצע על ידי אבן, גולדרייך ולמפל, השולח $\ S$ מחזיק בשני סודות $\ M_{0}$ ו-$\ M_{1}$ והמקבל $\ R$ מחזיק בסיבית אקראית כלשהי $\ r$ והוא מעוניין לקבל את $\ M_{r}$, מבלי שהשולח יידע מהו $\ r$. בעוד ש-$\ S$ מבטיח כי $\ R$ קיבל רק סוד אחד מהשניים ששלח. הפרוטוקול מוגדר באופן כללי ללא תלות בסוג ההצפנה. אפשר לממש את הפרוטוקול עם RSA כדלקמן:

1. $\ S$ מייצר מפתחות RSA (מודולוס $\ N$, מעריך פומבי $\ E_{x}$ ומפתח פרטי $\ D_{x}$), בוחר שני מספרים אקראיים שונים $\ m_{0},m_{1}<N$ ושולח ל-$\ R$ את: $\ (N,E_{x},m_{0},m_{1})$.
2. $\ R$ בוחר ערך אקראי $\ r\in \{0,1\}$ וערך אקראי $\ k<N$, מחשב את: $\ q=E_{x}(k)+m_{r}{\mbox{ mod }}N$ ושולח את $\ q$ ל-$\ S$.
3. $\ S$ מפענח את $\ k_{0}^{'}=D_{x}(q-m_{0}\ ({\mbox{mod }}N)),k_{1}^{'}=D_{x}(q-m_{1}\ ({\mbox{mod }}N))$ באמצעות המפתח הפרטי שלו $\ D_{x}$, בוחר ערך אקראי $\ s\in \{0,1\}$ ושולח ל-$\ R$ את $\ d_{0}=(M_{0}+k_{s}^{'})\ {\mbox{mod }}N$, את $d_{1}=(M_{1}+k_{s\oplus 1}^{'})\ {\mbox{mod }}N$ ואת $\ s$ (הסמל $\ \oplus$ מייצג XOR).
4. כעת $\ R$ יכול לחלץ את הסוד $\ M_{r}=M_{s\oplus r}$ על ידי חישוב $\ M_{r}=(d_{r}-k){\mbox{ mod }}N$ היות ש-$\ k=k_{r}^{'}$ ו-$\ r$ ידוע לו. כמו כן אפשר לראות ש-$\ d_{r}$ שנשלח אליו במסר 3 שקול ל-$\ (M_{s\oplus r}+k_{s\oplus (s\oplus r)}^{'}){\mbox{ mod }}N$.

בהנחה שפונקציית המפתח הפומבי שבחר השולח בטוחה, המקבל $\ R$ אינו יכול למצוא $\ q$ כך שהוא ידע מהו $\ M_{0}$ בהסתברות גבוהה יותר מחצי, אם הפרוטוקול הושלם במלואו. כמו כן המקבל $\ R$ יכול לגלות רמאות בהסתברות של חצי, אם לא קיבל בשלב 3 את $\ M_{s\oplus r}$, היות שהוא בחר את $\ r$ וכאמור $\ s$ נשלח אליו.

העברה עלומה והערכה עלומה

הרעיון הכללי של העברה עלומה מתחלק לכמה סוגים; פרוטוקול העברה עלומה 1 מתוך N שבו אליס יודעת N סודות ומעוניינת לאפשר לבוב לבחור אחד מהסודות שירצה בדרך כזו שהוא לא יידע יותר מסוד אחד בלבד, בעוד אליס לא תדע איזה מהם בוב בחר, וכן פרוטוקול הערכה עלומה המאפשר לאליס ובוב, המחזיקים כל אחד בסודות $\ x$ ו-$\ y$ בהתאמה, לחשב פונקציה פומבית $\ f(x,y)$ מבלי שאף אחד מהם ילמד לגבי הסוד של האחר מעבר למה שניתן ללמוד מהפונקציה $\ f$ של שני הסודות (דוגמת בעיית המליונרים לעיל). מוני נאור ובני פנקס (מכון ויצמן למדע) פרסמו ב-1999 פרוטוקולים יעילים המיישמים רעיונות אלו. ביל איילו (Bill Aiello), יובל ישי ועומר רינגולד פרסמו פרוטוקול המשתמש בהעברה עלומה לצורך מסחר דיגיטלי המגן על פרטיות הלקוחות באופן שהמוכר אינו יודע מה, כמה או מתי הלקוח רכש סחורה. סוון לאור (Sven Laur) והלגר ליפמאה (Helger Lipmaa) הציעו פרוטוקול דומה הנקרא Conditional Disclosure of Secrets המשתמש בהעברה עלומה כדי לאפשר ללקוח לרכוש סחורה משרת רק אם ההצעה שהציע תואמת את הרצוי. הפרוטוקול מונע מהשרת לחשוף את הסוד במקרה שההצעה שקיבל עבור הסוד אינה רצויה לו.

ראו גם

• הוכחה באפס ידיעה
• חישוב רב משתתפים בטוח
• חלוקת סוד

קישורים חיצוניים

• Wiesner, S. 1983. Conjugate coding. SIGACT News 15, 1 (Jan. 1983), 78-88
• Michael O. Rabin. "How to exchange secrets by oblivious transfer." Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981
• Joe Kilian. "Founding Cryptography on Oblivious Transfer", Proceedings, 20th Annual ACM Symposium on the Theory of Computation (STOC), 1988
• Even, S., Goldreich, O., and Lempel, A. 1985. A randomized protocol for signing contracts. Commun. ACM 28, 6 (Jun. 1985), 637-647.
• Oblivious Transfer or Private Information Retrieval