שיטת CKKS פורסמה לראשונה במאמר משנת 2017, ואחר כך פורסמו עוד מאמרים (על ידי המחברים המקוריים ואחרים) המראים איך ניתן להפוך את CKKS לסְכֶמַת הצפנה הומומורפית מלאה על ידי פעולת Bootstrap מתאימה. פרסומים נוספים הציגו דרכים שונות לשפר את הביצועים והדיוק של סְכֶמַת ה-CKKS המקורית, וכיום הסְכֶמָה ממומשת ברוב הספריות המציעות שירותי הצפנה הומומורפית, כמו HEAAN (הראשונה להציע מימוש של CKKS), Palisade, SEAL, HElib, ועוד (ראו ברשימת הקישורים למטה).
המרכיבים העיקריים של סכמת CKKS.
ההסבר להלן נועד לתת הבנה כללית על שיטת CKKS ואינו מוצג באופן מתמטי פורמלי. CKKS היא סְכֶמַת הצפנה עם מפתח ציבורי, כלומר מפתח ציבורי מאפשר לכל מי שמחזיק בו להצפין מידע, אך רק מי שמחזיק במפתח הפרטי יכול אחר כך לפענח את הצופן. במקרה של סכמות הצפנה הומומורפיות כמו CKKS, המפתח הפומבי מאפשר בנוסף לכך גם לבצע חישובים מעל ההצפנות (אך לא לגלות את תוצאת החישובים הללו).
כמו בשיטות הצפנה הומומורפיות אחרות, CKKS מבצעת חישובים על וקטורים גדולים של מספרים בבת-אחת, למשל בספרית SEAL ניתן להצפין ווקטור של עד 16,384 איברים. במקרה של CKKS המספרים שבווקטור המוצפן הם מספרים מרוכבים. כל הצפנה מצפינה ווקטור אחד שכזה ופעולות החישוב מבוצעות על הצפנה בודדת או על זוג הצפנות כשהפעולה מבוצעת איבר-איבר. למשל חיבור של שני צפנים עם 16,384 איברים יתן הצפנה חדשה של וקטור עם 16,384 איברים שבו כל איבר הוא סכום האיברים התואמים בווקטורים של ההצפנות המחוברות. ישנן גם פעולות הפועלות על הצפנה בודדת, למשל פעולת הרוֹטַציָה המסובבת את איברי הווקטור המוצפן במספר התזוזות הרצוי.
סְכֶמַת CKKS מחזיקה את ההצפנות בצורה של פולינומים, ובאופן מדויק יותר של פולינומים בחוג המנה מעל פולינום ציקלוטומי עם מקדמים שלמים בחוג השאריות מודולו q כלשהו. כך, כל החישובים ההומומורפים המבוצעים על ההצפנות הם חיבורים והכפלות של פולינומים מעל חוג המנה הזה. במילים פשוטות יותר אולי, אם במהלך החישוב מתקבל מקדם פולינום גדול מ-q אז יש להשאיר רק את השארית שלו אחרי חלוקה ב-q, ואם מתקבל פולינום הגדול מפולינום המנה אז יש להשאיר רק את השארית של הפולינום כולו אחרי חלוקה שלו בפולינום המנה.
תהליך ההצפנה פותח בשלב הקידוד שבו הווקטור עם המספרים המרוכבים המיועדים להצפנה מקודד כפולינום עם מקדמים שלמים. שלב הקידוד נועד בעיקר לאפשר את שלבי ההצפנה והחישוב הבאים בתור, ואשר פועלים כאמור על פולינומים, ואינו מבטיח את סודיות הנתונים המקודדים כלל וכלל. כל הסודיות של הצופן מושגת בשלב ההצפנה הבא לאחר שלב הקידוד. אחר כך מבוצעים החישובים ההומומורפים מעל ההצפנות השונות, ועם סיום החישוב, נשלחת התוצאה המוצפנת בחזרה למשתמש המחזיק במפתח הפענוח הפרטי. ההצפנה מפוענחת עם המפתח הפרטי כדי לקבל את הפולינום המקודד את התוצאה, ולסיום ממירים את הפולינום הזה בחזרה לווקטור התוצאה עצמו.
שלב הקידוד המוקדם ופתיחת הקידוד הסופי.
סְכֶמָה שהוגדרה להצפין וקטורים עם n איברים תקודד את הווקטור כפולינום עם 2n מקדמים שלמים (כלומר מדרגה 2n-1). הפולינום המקודד הוא הפולינום (היחידי) שכאשר מציבים בו את 2n שורשי היחידה הפרימיטיבים המרוכבים מסדר 4n מקבלים את n האיברים שבמערך המוצפן, ועוד n איברים השווים לצמודים (conjugates) של אותם איברים מוצפנים. בגלל התכונות המיוחדות של שורשי היחידה ניתן למצוא ביעילות את הפולינום המקודד (בעזרת שיטות המבוססות על התמרת פורייה). כאשר רוצים "לפתוח" את הקוד, כלומר להמיר בחזרה את הפולינום לווקטור של מספרים מרוכבים, ניתן להציב את n שורשי היחידה הפרימיטיבים הראשונים בתוך הפולינום ולקבל את n האיברים של הווקטור (אין צורך להציב את שאר n שורשי היחידה בשלב זה, כי הצבתם תוביל באופן מיותר לקבלת הצמודים של n האיברים המפוענחים). גם שלב זה ניתן להאצה בעזרת שיטות המבוססות על התמרת פורייה.
דוגמה: נניח שהווקטור המוצפן הוא באורך n=2, וכולל את זוג המספרים המרוכבים formula_1, formula_2. הפולינום שמקודד זוג מספרים זה (יחד עם שני הצמודים שלהם formula_3, formula_4) הוא formula_5. ארבעת שורשי היחידה הפרימיטיבים מסדר 4n=8 הם
formula_6. ניתן לראות שאמנם החזקה ה-8 של מספרים אלה היא 1, וששאר שורשי היחידה מסדר 8 (1, 1-, i, i-) אינם פרימיטיבים כייוון שהחזקה הקטנה ביותר שלהם המביאה אותם ל-1 היא קטנה מ-8. כמו כן כשמציבים בפולינום את שורש היחידה הראשון formula_7 מקבלים את הערך המוצפן formula_1, וכשמציבים את שורש היחידה השלישי formula_9 מקבלים את הערך המוצפן formula_2. כשמציבים את שורשי היחידה השני והרביעי מקבלים את הערכים הצמודים לערכים אלה. כמו כן, כיוון ששורשי היחידה גלויים לכל, הרי שאין צורך במפתח סודי כדי לפתוח את הפולינום המקודד ולקבל בחזרה את הערכים המוצפנים, וכפי שנאמר שלב הקידוד אינו תורם לבטיחות של סכמת ההצפנה.
הבעיה בפולינום שבדוגמה היא שהמקדמים שלו אינם שלמים, כפי שנדרש על ידי הסְכֶמָה. לכן מכפילים את כל המקדמים בפקטור גדול מספיק ומעגלים את התוצאה. ככל שהפקטור גדול יותר, כך מאבדים פחות דיוק בשלב העיגול. למשל בדוגמה למעלה, אם נכפיל את המקדמים בפקטור 64 ונעגל, נקבל את הפולינום formula_11, שכל מקדמיו שלמים כנדרש. אם נפתח את הקידוד החדש על ידי הצבת שורשי היחידה נקבל ערכים גדולים פי 64, ולכן יש לקפיד ולחלק את הערכים הסופיים ב-64 בסוף שלב פתיחת הקידוד. בדוגמה למעלה הערכים המוצפנים כללו רכיבים שלמים (3, 4, 2, 1-), אבל שיטת הקידוד תעבוד גם כאשר הערכים המוצפנים כוללים רכיבים שאינם שלמים. צריך רק להקפיד ולהשתמש בפקטור גדול מספיק כדי לאפשר חישובים עם הדיוק הדרוש. כלומר הפקטור בעצם מגדיר את הסְקָאלָה או רמת הדיוק של החישובים. למשל פקטור של formula_12 יתאים לחישובים עם דיוק של 40 ביטים. ראו פרטים נוספים על תחזוקת הסְקָאלָה במהלך החישוב ועל הבעיות הקשורות בכך בסעיף למטה.
הצפנה ופיענוח.
ב-CKKS המפתח הפרטי sk הוא פולינום (מעל חוג המנה שתואר למעלה) שבו המקדמים הם ערכים שלמים אקראיים ו"קטנים". למשל ברוב הספריות המממשות את CKKS כל המקדמים של sk הם 0, 1, או 1-. הפולינום שהתקבל בשלב הקידוד שתואר למעלה משמש כמסר המוצפן (ה-plaintext). ההצפנה של מסר (כלומר פולינום) m היא זוג של פולינומים (a,b) כך ש formula_13, כאשר e הוא רעש קטן אקראי (החיבורים והכפלים המופיעים כאן הם פעולות על פולינומים מעל חוג המנה כפי שתואר למעלה). כלומר, מי שמחזיק בזוג הפולינומים של ההצפנה וגם ב-sk יכול בקלות לבצע את החישוב הנ"ל ולפענח את המסר המקורי m, עם רעש קטן.
השגיאה שבהצפנה היא חיונית ומוכנסת באופן מכוון כיוון שבלעדיה יהיה קל מדי לפענח את הצופן גם בלי sk. השגיאה הופכת את בעיית הפענוח לבעיה קשה (השקולה לבעיית Learning With Errors של עודד רגב). המפתח הפומבי pk מכיל מספיק מידע כדי לאפשר בקלות מציאת זוג פולינומים (a,b) שכאלה בהינתן m, והוא מכיל בתוכו רעש קטן שיוביל לרעש בהצפנות הנובעות ממנו. תהליך ההצפנה מוסיף עוד רעש אקראי נוסף כדי להבטיח שהצפנות חוזרות של אותו מסר יהיו שונות זו מזו.
ביצוע חישובים הומומורפים על ההצפנות.
המטרה של סְכֶמַת הצפנה הומומורפית היא כאמור לאפשר חישוב על הנתונים המוצפנים בעזרת ביצוע חישובים על ההצפנות בלבד.
קל לראות למשל שאם
formula_14
וגם
formula_15
אז גם
formula_16.
במילים אחרות אם (a1,b1) מצפין את m1 ו- (a2,b2) מצפין את m2, אז (a1+a2,b1+b2) מצפין את m1+m2, והרעש גדל להיות עד סכום הרעשים של ההצפנות המחוברות. כך גם קל לראות שאם (a,b) מצפין את m, ו-w הוא מספר מרוכב כלשהו אז (a,b)*w מצפין את w*m. הכפלה של זוג הצפנות היא מורכבת מעט יותר ונעזרת במפתח פומבי נוסף שהונפק מראש למען מטרה זו. הכפלה גם מגדילה את הרעש שבתוצאה במידה ניכרת יותר, היא איטית יותר לחישוב, וגם יוצרת בעיות בתחזוקת הסְקָאלָה כפי שיתואר בסעיף הבא. לכן בדרך כלל מכפלות בסְכֶמָה הומומורפית הן משאב יקר, ומחקר רב מושקע בדרכים לחסוך במספר הכפלים הדרוש בחישוב ובביצוע נקי וזריז יותר של הכפלים הנחוצים.
מסר שהוצפן מורכב כאמור מזוג פולינומים, אך במהלך החישוב, מספר הפולינומים בהצפנה יכול לגדול. למשל אחרי כפל של ההצפנה (a1,b1) עם ההצפנה (a2,b2) תתקבל הצפנה (a3,b3,c3) המורכבת מ-3 פולינומים. כדי לפענח הצפנה שכזאת יש לחשב את
formula_17. באופן דומה ניתן גם להחזיק הצפנות עם מספר גדול יותר של רכיבים פולינומיים. הבעיה היא שמספר הרכיבים ילך ויגדל אחרי כל חישוב מכפלה, ויכביד על דרישות הזיכרון וזמן החישוב מעל ההצפנות. לכן נתמכת פעולת "יישור" relinearization, המחזירה את ההצפנה לצורה הכוללת רק זוג רכיבים. פעולה זו נעזרת במפתח פומבי מיועד שהונפק מראש למען מטרה זו.
תחזוקת הסקאלה של הצופן ו-Bootstrap.
כפי שתואר למעלה, להצפנה צמודה סְקָאלָה מתאימה שמציינת את הפקטור שיש לחלק בו כדי לקבל את המסר המוצפן בסוף תהליך הפענוח ופתיחת הקוד. למשל את המסר שערכו 0.32 ניתן לייצג כמספר השלם 32 עם סְקָאלָה של 100, או באופן שקול גם כמספר השלם 320,000 עם סקאלה של 1,000,000. כשמכפילים זוג מספרים עם סקאלות, יש להכפיל גם את הסקאלות. כך למשל 32 עם סְקָאלָה של 100 (כלומר 0.32) מוכפל ב-4 עם סקאלה 1000 (כלומר 0.004) נותן 128 עם סקאלה 100,000 (כלומר 0.00128).