הצפנה הומומורפית

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

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

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

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

נסמן ב-E_p(x) את הצופן המצפין את המסר x עם המפתח הפומבי p. תהי f פונקציה n-מקומית שניתנת לחישוב יעיל. שיטת ההצפנה היא הומומורפית ביחס לפונקציה f אם קיימת פונקציה g‏, n+1 מקומית, שניתנת לחישוב יעיל ומקיימת: g(p,E_p(x_1),\ldots,E_p(x_n)) = E_p(f(x_1,\ldots,x_n)). ו-g לא מוסרת שום מידע על המסרים x_1,\ldots,x_n, על f(x_1,\ldots,x_n) או על ערך כלשהו שמתקבל בזמן החישוב של f (ניתן לפרמל תנאי זה במספר דרכים שונות).

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

  • צופן קיסר הוא הומומורפי (כצופן סימטרי) ביחס לפעולת השרשור: אפשר קודם לשרשר שתי מחרוזות ואז להסיט אותן או שאפשר להסיט כל אחת בנפרד ואז לשרשר. התוצאה זהה.
  • RSA הומומרפי ביחס לכפל. המסר x מוצפן עם המפתח (e,n) כ-E(x) = x^e\ \bmod\ n ולכן:
    E(x_1) \cdot E(x_2) = x_1^e x_2^e \;\bmod\; n = (x_1x_2)^e \;\bmod\; n = E(x_1 \cdot x_2)
    לצופן אל-גמאל תכונת הומומורפיות זהה.

הצפנה הומומורפית מלאה[עריכת קוד מקור | עריכה]

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