CKKS – הבדלי גרסאות

באופן כללי הצפנה הומומורפית (Homomorphic Encryption) היא שיטת הצפנה המאפשרת לבצע חישוב מסוים על מסרים מוצפנים שתוצאתו היא מסר מוצפן אחר השקול לתוצאה שהייתה מתקבלת מהצפנת פעולת החישוב האמורה על המסרים המקוריים. למשל חיבור של ההצפנה של X עם ההצפנה של Y יתן את ההצפנה של X+Y. סְכֶמַת הצפנה הומומורפית היא "מלאה" (Fully Homomorphic Encryption) אם היא מאפשרת לבצע ''כל'' חישוב רצוי על הצפנים באופן יעיל. הביטחון של סְכֶמַת CKKS מתבסס על הנחת הקושי הנובעת מ־[[Learning With Errors]] של [[עודד רגב (מדען מחשב)|עודד רגב]].

אחרישיטת פרסוםCKKS המאמרפורסמה המקורילראשונה במאמר משנת ב-2017, ואח"כ פורסמו מאמריםעוד נוספיםמאמרים (ע"י המחברים המקוריים ואחרים) המראים איך ניתן להפוך את CKKS לסְכֶמַת הצפנה הומומורפית מלאה ע"י פעולת Bootstrap מתאימה{{הערה|שם=CKKS-BS1|{{Citation | title=Bootstrapping for Approximate

Homomorphic Encryption | author1=Hao Chen |author2=Ilaria Chillotti |author3=Yongsoo Song| publisher=Springer, Cham | journal=Annual International Conference on the Theory and Applications of Cryptographic Techniques |year=2019}}}}. מאזפרסומים פורסמונוספים עבודותהציגו רבותדרכים ע"ישונות חוקרים שונים ששיפרולשפר את הביצועים והדיוק של סְכֶמַת ה-CKKS המקורית, וכיום הסְכֶמָה ממומשת ברוב הספריות המציעות שירותי הצפנה הומומורפית, כמו HEAAN (הראשונה להציע מימוש של CKKS), Palisade, SEAL, HElib, ועוד (ראו ברשימת הקישורים למטה).

ההסבר להלן נועד לתת הבנה כללית על שיטת CKKS ואינו מוצג באופן מתמטי פורמאלי. כמו בשיטות הצפנה הומומורפיות אחרות, CKKS מבצעת חישובים על וקטורים גדולים של [[מספר מרוכב|מספרים מרוכבים]] בבת-אחת, למשל בספרית SEAL ניתן להצפין ווקטור של עד 16,384 איברים. במקרה של CKKS המספרים שבווקטור המוצפן הם [[מספר מדומה|מספרים מדומים]]. כל הצפנה מצפינה ווקטור אחד שכזה ופעולות החישוב מבוצעות על הצפנה בודדת או על זוג הצפנות כשהפעולה מבוצעת איבר-איבר. למשל חיבור של שני צפנים עם 16,384 איברים יתן הצפנה חדשה של וקטור עם 16,384 איברים שבו כל איבר הוא סכום האיברים התואמים בווקטורים של ההצפנות המחוברות. ישנן גם פעולות הפועלות על הצפנה בודדת, כמו למשל פעולת הרוֹטַציָה המסובבת את איברי הוקטור המוצפן במספר התזוזות הרצוי.

תהליך ההצפנה פותח בשלב הקידוד שבו הווקטור עם המספרים המרוכבים המיועדים להצפנה "מקודד" כפולינום עם מקדמים שלמים. סְכֶמָה שהוגדרה להצפין וקטורים עם n איברים תקודד את הווקטור כפולינום עם 2n מקדמים שלמים (כלומר מדרגה 2n-1). שלב הקידוד נועד בעיקר לאפשר את שלבי ההצפנה והחישוב הבאים בתור, ואשר פועלים כאמור על פולינומים, ואינו מבטיח את סודיות הנתונים המקודדים כלל וכלל (הסודיות של הצופן תושג בשלב ההצפנה הבא בתור). הפולינום המקודד הוא הפולינום (היחידי) שכאשר מציבים בו את 2n [[שורש יחידה|שורשי היחידה הפרימיטיבים]] המרוכבים מסדר n4n מקבלים את n האיברים שבמערך המוצפן, ועוד n איברים השווים לצמודיםל[[שדה המספרים המרוכבים|צמודים]] (conjugates) של אותם איברים מוצפנים. בגלל התכונות המיוחדות של שורשי היחידה ניתן למצוא ביעילות את הפולינום המקודד (בעזרת שיטות המבוססות על [[התמרת פורייה]]). כאשר רוצים "לפתוח" את הקוד, כלומר להמיר בחזרה את הפולינום לווקטור של מספרים מרוכבים, ניתן להציב את n שורשי היחידה הפרימיטיבים הראשונים בתוך הפולינום ולקבל את n האיברים של הווקטור (אין צורך להציב את שאר n שורשי היחידה בשלב זה, כי הצבתם תוביל באופן מיותר לקבלת הצמודים של n האיברים המפוענחים). גם שלב זה ניתן להאצה בעזרת שיטות המבוססות על התמרת פורייה.

'''דוגמא''': נניח שהווקטור המוצפן הוא באורך n=2, וכולל את זוג המספרים המרוכבים <math>3+4i</math>, <math>2-i</math>. הפולינום שמקודד זוג מספרים זה (יחד עם שני הצמודים שלהם <math>3-4i</math>, <math>2+i</math>) הוא <math>\ \frac{1}{4}(10+4\sqrt{2}x+10x^2+2\sqrt{2}x^3) </math>. ארבעת שורשי היחידה הפרימיטיבים מסדר 2n4n=48 הם

<math>(\frac{\sqrt{2}}{2},\frac{\sqrt{2}}{2}), (-\frac{\sqrt{2}}{2},\frac{\sqrt{2}}{2}), (-\frac{\sqrt{2}}{2},-\frac{\sqrt{2}}{2}), (\frac{\sqrt{2}}{2},-\frac{\sqrt{2}}{2})</math>. שימוניתן לבלראות שאמנם החזקה ה-8 של מספרים אלה היא 1, וששאר שורשי היחידה מסדר 8 (1, 1-, i, i-) אינם פרימיטיבים כייוון שהחזקה הקטנה ביותר שלהם המביאה אותם ל-1 הינה קטנה מ-8. כמו כן כשמציבים בפולינום את שורש היחידה הראשון <math>(\frac{\sqrt{2}}{2},\frac{\sqrt{2}}{2})</math> מקבלים את הערך המוצפן <math>3+4i</math>, וכשמציבים את שורש היחידה השלישי <math>(-\frac{\sqrt{2}}{2},-\frac{\sqrt{2}}{2})</math> מקבלים את הערך המוצפן <math>2-i</math>. כשמציבים את שורשי היחידה השני והרביעי מקבלים את הערכים הצמודים לערכים אלה. כמו כן, שימו לב שוב שכיווןכיוון ששורשי היחידה כמובן גלויים לכל, הרי שאין צורך במפתח סודי כדי לפתוח את הפולינום המקודד ולקבל בחזרה את הערכים המוצפנים, וכפי שנאמר שלב הקידוד אינו תורם לבטיחות של סכמת ההצפנה.

הבעיה בפולינום שבדוגמא הוא שהמקדמים שלו אינם שלמים, כפי שנדרש ע"י הסְכֶמָה. לכן מכפילים את כל המקדמים בפקטור גדול מספיק ומעגלים את התוצאה. ככל שהפקטור גדול יותר, כך מאבדים פחות דיוק בשלב העיגול. למשל בדוגמא למעלה, אם נכפיל את המקדמים בפקטור 64 ונעגל, נקבל את הפולינום <math>\ 160+91x+160x^2+45x^3 </math>, שכל מקדמיו שלמים כנדרש. כמובן, שאם נפתח את הקידוד החדש ע"י הצבת שורשי היחידה נקבל ערכים גדולים פי 64, ולכן יש לקפיד ולחלק את הערכים הסופיים ב-64 בסוף שלב פתיחת הקידוד. בדוגמא למעלה הערכים המוצפנים כללו רכיבים שלמים (3, 4, 2, 1-), אבל שיטת הקידוד תעבוד גם כאשר הערכים המוצפנים כוללים רכיבים שאינם שלמים. צריך רק להקפיד ולהשתמש ב"פקטור"בפקטור גדול מספיק כדי לאפשר חישובים עם הדיוק הדרוש. כלומר ה"פקטור"הפקטור בעצם מגדיר את ה'''סְקָאלָה''' או רמת הדיוק של החישובים. למשל פקטור של <math>2^{40}</math> יתאים לחישובים עם דיוק של 40 ביטים. ראו פרטים נוספים על "תחזוקת" הסְקָאלָה במהלך החישוב ועל הבעיות הקשורות בכך בסעיף למטה.

הפולינום שהתקבל בשלב הקידוד שתואר למעלה משמש כמסר המוצפן (ה-plaintext). ההצפנה של מסר (כלומר פולינום) m הוא זוג של פולינומים (a,b) כך ש <math> a + b * sk = m + e </math>, כאשר e הוא רעש קטן אקראי (החיבורים והכפלים המופיעים כאן הם פעולות על פולינומים מעל חוג המנה כפי שתואר למעלה). כלומר, מי שמחזיק בזוג הפולינומים של ההצפנה וגם ב-sk יכול בקלות לבצע את החישוב הנ"ל ולפענח את המסר המקורי m, עם רעש קטן. השגיאה שברעש היא חיונית ומוכנסת באופן מכוון להצפנה כיוון שבלעדיה יהיה קל מדי לפענח את הצופן גם בלי sk. השגיאה הופכת את בעית הפענוח לבעיה קשה (השקולה לבעית [[Learning With Errors]] של [[עודד רגב (מדען מחשב)|עודד רגב]]). המפתח הפומבי '''pk''' מכיל מספיק מידע כדי לאפשר בקלות מציאת זוג פולינומים (a,b) שכאלה בהנתן m, והוא מכיל בתוכו אתרעש הרעשקטן הדרוששיוביל לרעש בהצפנה הנובעת ממנו. תהליך ההצפנה מוסיף עוד רעש אקראי נוסף כדי להביאלהבטיח לרעששהצפנות מספיקחוזרות בהצפנהשל וכדיאותו למנועמסר אתיהיו מציאתשונות זו skמזו.

במילים אחרות אם (a1,b1) מצפין את m1 ו- (a2,b2) מצפין את m2, אז (a1+a2,b1+b2) מצפין את m1+m2, והרעש גדל להיות עד סכום הרעשים של ההצפנות המחוברות. כך גם קל לראות שאם (a,b) מצפין את m, ו-w הוא מספר מרוכב כלשהו אז (a,b)*w מצפין את w*m. הכפלה של זוג הצפנות היא מורכבת מעט יותר ונעזרת במפתח פומבי נוסף שהונפק מראש למען מטרה זו. הכפלה גם מגדילה את הרעש שבתוצאה במידה ניכרת יותר, היא איטית יותר לחישוב, וגם יוצרת בעיות בתחזוקת הסְקָאלָה כפי שיתואר בסעיף הבא. לכן בד"כ מכפלות בסְכֶמָה הומומורפית הן "משאב" יקר, ומחקר רב מושקע בדרכים לחסוך במספר הכפלים הדרוש בחישוב ובביצוע נקי וזריז יותר של הכפלים הנחוצים.

כפי שתואר למעלה, להצפנה "צמודה" סְקָאלָה מתאימה שמציינת את הפקטור שיש לחלק בו כדי לקבל את המסר המוצפן בסוף תהליך הפענוח ופתיחת הקוד. למשל את המסר שערכו 0.32 ניתן לייצג כמספר השלם 32 עם סְקָאלָה של 100, או באופן שקול גם כמספר השלם 320,000 עם סקאלה של 1,000,000. כשמכפילים זוג מספרים עם סקאלות, יש להכפיל גם את הסקאלות. כך למשל 32 עם סְקָאלָה של 100 (כלומר 0.32) מוכפל ב-4 עם סקאלה 1000 (כלומר 0.004) נותן 128 עם סקאלה 100,000 (כלומר 0.00128).

בעיה קשה יותר הקשורה בתחזוקת הסקאלה, היא שמסתבר שאחרי rescale שמחלק את הערך ואת הסקאלה במידה כלשהי, נדרש לחלק גם את q (כלומר את הגבול העליון של הערכים) באותה המידה. כך בדוגמא שהובאה למעלה פעולת ה -rescale חילקה את הערך ואת הסקאלה שלו ב-10,000, ולכן אם q היה נניח מלכתחילה 1,000,000, הרי שאחרי ה-rescale הערך של q יקטן ל-100 ויגביל מאוד את החישוב בהמשך. לכן בד"כ מתחילים עם q גדול מאוד (למשל <math>2^{800}</math>), אבל בכל זאת אחרי מספיק מכפלות התקרה של q תרד נמוך מדי כדי לאפשר את המשך החישוב. כדי לאפשר חישוב בלתי מוגבל (כלומר סְכֶמַת הצפנה הומומורפית "מלאה") יש להסיר מגבלה זו, ואמנם כותבי המאמר המקורי הציעו כאמור מספר דרכים לבצע פעולת "bootstrap" המחזירה את q לתחום הערכים הגבוהים שיאפשרו את המשך החישוב. יש לשים לב שפעולת ה-bootstrap של CKKS נועדה לאפשר את המשך החישוב והיא אינה מסירה את הרעש שהצטבר בערכים המוצפנים (למעשה היא מגדילה מעט את הרעש הנובע מחישוב פעולת ה-bootstrap עצמה). זאת בשונה מסכמות הומומורפיות אחרות, כמו BGV, שם ה-bootstrap מאפשר את המשך החישוב ע"י הסרת הרעש שבהצפנה עצמה.

Approximate Homomorphic Encryption | author1=Jung Hee Cheon |author2=Kyoohyung Han |author3=Andrey Kim | |author4=Miran Kim |author5=Yongsoo Song| publisher=Springer, Cham | journal=International Conference on Selected Areas in Cryptography |year=2018}}}} המאפשרות ביצועים סבירים לחישובים שימושיים כמו [[למידת מכונה]] עם [[רשת עצבית|רשתות ניורונים]] מוצפנתמוצפנות, שירותי מסד נתונים מוצפן ועוד. אלה כוללות בין השאר: