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

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

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

הגדרה

נסמן ב-$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, אז הודגמה לראשונה הצפנה הומומורפית מלאה.

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