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

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

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

הצפנה הומומרפית מאפשרת לבצע חישוב באופן פומבי מבלי לחשוף את מרכיביו ואת תוצאתו. מדובר אם כן בכלי חזק מאוד שאף כונה "הגביע הקדוש של הקריפטוגרפיה"‏[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]. ההומומורפיזם שדובר עליו במאמר הוא הומומורפיזם חלקי, הוא אפשרי אך ורק לפעולת הכפל. אחת השאלות שעלו במאמר היא האם קיימת סכמת הצפנה שתהיה הומומורפית לכל פונקציה חשיבה.

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

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

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

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

בשנת 2009 הוכיח קרייג ג'נטרי, אז דוקטורנט באוניברסיטת סטנפורד וחוקר בקבוצת ווטסון בחברת IBM, בעבודת הדוקטורט שלו‏[4] שהצפנה כזו קיימת. הסכמה היא הצפנה מבוססת סריגים ומתבססת על הנחות בנוגע לסריגים אידאליים. הבנייה התחלקה לשני שלבים עיקריים:

  1. ראשית בנה ג'נטרי הצפנה הומומורפית מלאה לעומק קבוע (Levelled FHE), הצפנה שהומומורפית לכל פונקציה שניתנת לחישוב על ידי מעגל בעומק נתון מראש, במקרה הנוכחי - יכולת להעריך כל פולינום עד למעלה מסוימת. ההגבלה על העומק נוצרה מכך שסכמת ההצפנה כלל רעש על המסר המוצפן, כך שיכולת השחזור אפשרית רק לבעלי סוד מסוים - הוא המפתח הפרטי. בסכמות כאלה הרעש גדל בסדר גודל מסוים בכל שלב במעגל, ולכן פלט של מעגל בעומק גבוה מדיי יהיה עם יותר מדיי רעש ולא יהיה ניתן לשחזור.
  2. לאחר בניית הסכמה הזו, הגדיר ג'נטרי והוכיח את תהליך ה־Bootstrapping. פריצת הדרך של ג'נטרי נבעה מהתייחסותו אל תהליך הפענוח כאל עוד פונקציה שניתנת להערכה באופן הומומורפי על המסר המוצפן. מכאן, מרגע שהמסר המוצפן מכיל כמות גבוהה של רעש, כל שיש לעשות הוא להריץ הומומורפית את סכמת הפענוח, בעזרת פרסום הצפנה של המפתח הפרטי, וכך לקבל הצפנה של המסר המוצפן המפוענח - נניח שלאחר מספר פעולות הומומורפיות התקבל המסר המוצפן C=E_{pk}\left(M\right) שמכיל רעש רב. אנחנו נרצה לקבל הצפנה חדשה של M עם רעש חדש וקטן יחסית, את זאת נוכל לקבל על ידי הפעלת פונקציית הפענוח - E_{pk}\left(M\right)\rightarrow E_{pk}\left(D_{sk}\left(E_{pk}\left(M\right)\right)\right)
 . בצורה פורמלית - סכמת הצפנה תיקרא ניתנת ל־Bootstrapping אם היא הומומורפית לכל מעגל בעומק לכל היותר D+1, כאשר D הוא עומק המעגל של פונקציית הפענוח של הסכמה. כעת לאחר כל מספר פעולות הומומורפיות וכאשר הרעש גדל, מפעילים הומומורפית את פוקנציית הפענוח וממשיכים.

הבנייה של ג'נטרי ורעיון ה־Bootstrapping הביאו לפריחה בתחום. בשנים שעברו מאז פרסום עבודתו פורסמו סכמות הצפנה רבות המבוססות על רעיונות דומים שמנסות להתגבר על חלק מהחסרונות בבנייתו‏[5]. כיום רוב הסכמות מתבססות על הנחת הקושי הנובעת מ־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. ^ D. Boneh, E. Goh, and K. Nissim, Evaluating 2-DNF Formulas on Ciphertexts, In proceedings of Theory of Cryptography (TCC) '05, LNCS 3378, pp. 325-341, 2005
  4. ^ Craig Gentry, A fully homomorphic encryption scheme, PhD thesis, Stanford University, 2009, [1].
  5. ^ לדוגמה - Nigel P. Smart and Frederik Vercauteren, Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes, In Phong Q. Nguyen, David Pointcheval (Eds.), Public Key Cryptography 2010, Lecture Notes in Computer Science 6056, Springer 2010, p. 420-443., Craig Gentry, Amit Sahai Brent Waters, Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Identity-Based, CRYPTO 2013 ו־ Zvika Brakerski and Vinod Vaikuntanathan, Lattice-Based FHE as Secure as PKE, ITCS 2014.