העברה עלומה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

היסטוריה[עריכת קוד מקור | עריכה]

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

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

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

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

פרוטוקול העברה עלומה של רבין[עריכת קוד מקור | עריכה]

בוב ואליס המשתתפים בפרוטוקול מחזיקים כל אחד בסודות \ s_B ו-\ s_A בהתאמה, אותם הם מעוניינים להחליף ביניהם. הסודות יכולים להיות, למשל, סיסמת גישה לקובץ מוצפן. ההנחה היא שאליס ובוב לא ינסו לעשות שימוש בסוד שהם קיבלו מבלי שהם יהיו בטוחים בוודאות שהסוד נכון (למשל, אפשר להניח שבמקרה של טעות בהקלדת קוד הגישה לקובץ המוצפן, הקובץ יימחק). ולמען הפשטות נניח שהסוד של אליס ובוב הוא סיבית אחת. פרוטוקול EOS של רבין מסתמך על הצפנת מפתח פומבי ועל כן מניח כי ברשות אליס ובוב מפתחות פומביים \ k_A ו-\ k_B בהתאמה איתם הם יכולים להשתמש הן להצפנה והן לחתימה דיגיטלית. וכן כל מסרי הפרוטוקול חתומים באמצעות מפתח החתימה הפרטי של כל אחד מהם בהתאמה.

מהלכי הפרוטוקול[עריכת קוד מקור | עריכה]

  1. אליס ובוב בוחרים כל אחד בנפרד זוג ראשוניים שונים \ p_1,q_1 וכן \ p_2,q_2 ומכינים מפתחות הצפנה חד פעמיים \ n_A=p_1q_1 וכן \ n_B=p_2q_2. אליס שולחת לבוב מסר חתום המכיל את \ n_A ובוב מחזיר במסר חתום משלו המכיל \ n_B.
  2. בוב בוחר מספר שלם אקראי \ x כאשר \ x\le n_A ומחשב את \ c=x^2\mbox{ mod }n_A ושולח לאליס את \ c ואת: \ E_{k_B}(x) שהוא הצפנה של המספר האקראי שבחר באמצעות המפתח הפומבי שלו \ k_B.
  3. אליס מחשבת את \ x_1 המקיים \ x^2_1\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^2_A\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 פרוטוקולים‏[1] יעילים המיישמים רעיונות אילו. ביל איילו (Bill Aiello), יובל ישי ועומר רינגולד פרסמו פרוטוקול‏[2] המשתמש בהעברה עלומה לצורך מסחר דיגיטלי המגן על פרטיות הלקוחות באופן שהמוכר אינו יודע מה, כמה או מתי הלקוח רכש סחורה. סוון לאור (Sven Laur) והלגר ליפמאה (Helger Lipmaa) הציעו פרוטוקול[3] דומה הנקרא Conditional Disclosure of Secrets המשתמש בהעברה עלומה כדי לאפשר ללקוח לרכוש סחורה משרת רק אם ההצעה שהציע תואמת את הרצוי. הפרוטוקול מונע מהשרת לחשוף את הסוד במקרה שההצעה שקיבל עבור הסוד אינה רצויה לו.

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]