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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
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 הוכיח קרייג ג'נטרי בעבודת הדוקטורט שלו‏[3] שהצפנה כזו קיימת. בנייתו התחלקה לשלושה שלבים. ראשית הוא בנה הצפנה הומומורפית מלאה לעומק קבוע (Levelled FHE), הצפנה שהומומורפית לכל פונקציה שניתנת לחישוב על ידי מעגל בעומק נתון מראש. ההגבלה על העומק נוצרה מכך שסכמת ההצפנה כלל רעש על המסר המוצפן, כך שרק מי שיודע סוד מסויים יוכל לשחזר. בסכמות כאלה הרעש גדל בסדר גודל מסויים בכל שלב במעגל, ולכן פלט של מעגל בעומק גבוה מדיי יהיה עם יותר מדיי רעש ולא יהיה ניתן לשחזור. סכמת ההצפנה הזו מבוססת על הנחות בנוגע לסריגים אידאליים. לאחר בניית הסכמה הזו, הגדיר ג'נטרי והוכיח את תהליך ה־Bootstrapping. סכמת הצפנה תיקרא ניתנת ל־Bootstrapping אם היא הומומורפית לכל מעגל בעומק לכל היותר D+1, כאשר D הוא עומק המעגל של פונקציית הפענוח של הסכמה. עתה, ניתן להתייחס לפונקציית הפענוח של הסכמה בתור פונקציה רגילה לכל דבר, וכשהרעש במסר המוצפן בעומק מסויים בסכמה נעשה גדול מדיי, נוכל להשתמש בפונקציית הפענוח על המסר המוצפן הומומורפית וכך לקבל מסר מוצפן לאותה הודעה, אך עם רמת רעש נמוכה יותר, כך שנוכל לשוב ולהשתמשו מחדש כקלט לכל פונקציה.

הבנייה של ג'נטרי הוכרזה על ידי חברת IBM, שבה עבד כחוקר, ב־25 ביוני של אותה שנה‏[4].

הבנייה של ג'נטרי ורעיון ה־Bootstrapping הביאו לפריחה בתחום. בשנים שעברו מאז פרסום עבודתו פורסמו סכמות הצפנה רבות המבוססות על רעיונות דומים שמנסות להתגבר על חלק מהחסרונות בבנייתו. כיום רוב הסכמות מתבססות על הנחת הקושי הבעיה Learning With Errors של עודד רגב, שהיא הנחת קושי סטנדרטית יותר בניגוד להתבססות על סריגים אידיאליים. בנוסף, הסכמות היום יעילות יותר, אך עדיין לא יעילות מספיק לשימוש המוני.


  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
  3. ^ Craig Gentry, A fully homomorphic encryption scheme, PhD thesis, Stanford University, 2009, [1].
  4. ^ [2]