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

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

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

הצפנה הומומרפית מאפשרת לבצע חישוב באופן פומבי מבלי לחשוף את מרכיביו ואת תוצאתו. מדובר אם כן בכלי חזק מאוד שאף כונה "הגביע הקדוש של הקריפטוגרפיה"‏[1]. שימוש חשוב הוא כפתרון בעיות של ביטחון מידע במחשוב ענן.

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

בהינתן סכמת הצפנה עם פונקציית הצפנה E_{pk}(m) שמצפיה את המסר m עם המפתח הפומבי pk ופונקציית פענוח D_{sk}(c) המפענחת את המסר המוצפן c עם המפתח הפרטי sk. נסמן ב־M את מרחב ההודעות וב־C את מרחב ההודעות־המוצפנות של הסכמה. סכמת הצפנה תיקרא הומומומורפית ביחס לפונקציה f:M^n:\rightarrow M ב־n משתנים אם לסכמה קיימת פונקציית הערכה V(pk, f, c_1, \dots, c_n) כך שלכל n הצפנות c_1,\dots,c_n\in C של הודעות m_1,\dots ,m_n\in M מתקיים כי V(pk, f, c_1, \dots, c_n) מוציאה כפלט צופן c שהוא הצפנה של f(m_1,\dots ,m_n) באמצעות E_{pk}(m). ופירושו שניתן לבצע חישוב על המסר המוצפן ותוצאתו תהיה הצפנה של תוצאת החישוב על המסר טרם ההצפנה.

ברוב המקרים יש דרישה כחלק מההגדרה שהסכמה תהיה בטוחה סמנטית.

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

בשנת 1978, מעט לאחר פרסום הצופן RSA ריבסט, אדלמן ודרטוזוס הגדירו את המושג לראשונה ודנו בחשיבות של הומומורפיזם בהצפנה‏[2]. ההומומורפיזם שדובר עליו במאמר הוא הומומורפיזם חלקי, הוא אפשרי אך ורק לפעולת הכפל. אחת השאלות שעלו במאמר היא האם קיימת סכמת הצפנה שתהיה הומומורפית לכל פונקציה חשיבה.

דוגמאות להומומורפיזם חלקי:

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

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


  1. ^ Daniele Micciancio, "A First Glimpse of Cryptography's Holy Grail", Association for Computing Machinery. p. 96. 2010-03-01.
  2. ^ Ronald L. Rivest, Leonard M. Adleman, and Michael Dertouzos, On data banks and privacy homomorphisms, In Found. of Sec. Comp., 1978, pp.169-180