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

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

הצפנה הומומרפית מאפשרת לבצע חישוב באופן פומבי מבלי לחשוף את מרכיביו ואת תוצאתו. מדובר בכלי חזק מאוד שאף כונה "הגביע הקדוש של הקריפטוגרפיה"^[1]. שימוש חשוב הוא כפתרון בעיות של ביטחון מידע במחשוב ענן, מפני שניתן לבצע פעולות חישוב בענן על מידע המוצפן הומומורפית בלי פיענוח שלו, תוך שמירה על סודיותו גם במקרה של פריצה למערכות הענן^[2]. חברות ענק טכנולוגיות עוסקות בפיתוח הצפנה כזו לשימושים שונים, כגון פייסבוק שמפתחת מערכת לניתוח נתונים מוצפנים שתשמש להתאמת מודעות מדויקת יותר למשתמשים בוואטסאפ^[3][4].

הגדרה

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

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

הצפנה הומומורפית חלקית

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

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

• צופן קיסר הוא הומומורפי (כצופן סימטרי) ביחס לפעולת השרשור: אפשר קודם לשרשר שתי מחרוזות ואז להסיט אותן או שאפשר להסיט כל אחת בנפרד ואז לשרשר. התוצאה זהה.
• RSA הומומרפי ביחס לכפל. המסר ${\displaystyle x}$ מוצפן עם המפתח ${\displaystyle (e,n)}$ כ-${\displaystyle E(x)=x^{e}\ {\bmod {\ }}n}$ ולכן:

  ${\displaystyle E(x_{1})\cdot E(x_{2})=x_{1}^{e}x_{2}^{e}\;{\bmod {\;}}n=(x_{1}x_{2})^{e}\;{\bmod {\;}}n=E(x_{1}\cdot x_{2})}$

  לצופן אל-גמאל תכונת הומומורפיות זהה.

• הצפנת גולדווסר מיקאלי הומומורפית ביחס לחיבור.

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

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

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

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

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

הבנייה של ג'נטרי ורעיון ה־Bootstrapping הביאו לפריחה בתחום. בשנים שעברו מאז פרסום עבודתו פורסמו סכמות הצפנה רבות (כמו TFHE, CKKS, BGV, ואחרים) המבוססות על רעיונות דומים שמנסות להתגבר על חלק מהחסרונות בבנייתו^[8]. כיום רוב הסכמות מתבססות על הנחת הקושי הנובעת מ־Learning With Errors של עודד רגב, שהיא הנחת קושי מקובלת יותר בניגוד להתבססות על סריגים אידיאליים. בנוסף, הסכמות היום יעילות יותר, אך עדיין לא יעילות מספיק לשימוש המוני.

ראו גם

• CKKS

קישורים חיצוניים

• אז מה זו הצפנה הומומורפית, שתאפשר לפייסבוק להבין על מה אנחנו מדברים, בלי לשבור את ההצפנה, באתר גיקטיים, ‏2021-08-13

הערות שוליים

1. Daniele Micciancio, A First Glimpse of Cryptography's Holy Grail, Association for Computing Machinery. p. 96. 2010-03-01.
2. אז מה זו הצפנה הומומורפית, שתאפשר לפייסבוק להבין על מה אנחנו מדברים, בלי לשבור את ההצפנה, באתר גיקטיים, ‏2021-08-13
3. צבי קצבורג, פייסבוק מפתחת מערכת לניתוח נתונים מוצפנים ללא פענוח של התוכן בפועל - בשביל מודעות, באתר TGspot, ‏2021-08-04
4. פייסבוק תבין על מה אתם מדברים, בלי לפענח את ההודעות המוצפנות שלכם, באתר גיקטיים, ‏2021-08-09
5. Ronald L. Rivest, Leonard M. Adleman, and Michael Dertouzos, On data banks and privacy homomorphisms, In Found. of Sec. Comp., 1978, pp.169-180
6. 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
7. Craig Gentry, A fully homomorphic encryption scheme, PhD thesis, Stanford University, 2009, [1].
8. לדוגמה - 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.