CKKS

בקריפטוגרפיה, CKKS היא שיטת הצפנה הומומורפית פופולרית, המיועדת לבצוע חישובים על צפנים המצפינים מספרים ממשיים, וזאת בניגוד לשיטות קודמות שהתמקדו בחישובים על הצפנות של שלמים. שם הסְכֶמָה מורכב מהאותיות הפותחות את שמות מחברי המאמר המקורי שבו הוצגה השיטה, Kim, Kim, Cheon ו-Song.

באופן כללי הצפנה הומומורפית (Homomorphic Encryption) היא שיטת הצפנה המאפשרת לבצע חישוב מסוים על מסרים מוצפנים שתוצאתו היא מסר מוצפן אחר השקול לתוצאה שהייתה מתקבלת מהצפנת פעולת החישוב האמורה על המסרים המקוריים. למשל חיבור של ההצפנה של X עם ההצפנה של Y יתן את ההצפנה של X+Y. סְכֶמַת הצפנה הומומורפית היא "מלאה" (Fully Homomorphic Encryption) אם היא מאפשרת לבצע כל חישוב רצוי על הצפנים באופן יעיל.

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

שיטת 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, וכולל את זוג המספרים המרוכבים $3+4i$, $2-i$. הפולינום שמקודד זוג מספרים זה (יחד עם שני הצמודים שלהם $3-4i$, $2+i$) הוא $\ {\frac {1}{4}}(10+4{\sqrt {2}}x+10x^{2}+2{\sqrt {2}}x^{3})$. ארבעת שורשי היחידה הפרימיטיבים מסדר 4n=8 הם $({\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}})$. ניתן לראות שאמנם החזקה ה-8 של מספרים אלה היא 1, וששאר שורשי היחידה מסדר 8 (1, 1-, i, i-) אינם פרימיטיבים כייוון שהחזקה הקטנה ביותר שלהם המביאה אותם ל-1 היא קטנה מ-8. כמו כן כשמציבים בפולינום את שורש היחידה הראשון $({\frac {\sqrt {2}}{2}},{\frac {\sqrt {2}}{2}})$ מקבלים את הערך המוצפן $3+4i$, וכשמציבים את שורש היחידה השלישי $(-{\frac {\sqrt {2}}{2}},-{\frac {\sqrt {2}}{2}})$ מקבלים את הערך המוצפן $2-i$. כשמציבים את שורשי היחידה השני והרביעי מקבלים את הערכים הצמודים לערכים אלה. כמו כן, כיוון ששורשי היחידה גלויים לכל, הרי שאין צורך במפתח סודי כדי לפתוח את הפולינום המקודד ולקבל בחזרה את הערכים המוצפנים, וכפי שנאמר שלב הקידוד אינו תורם לבטיחות של סכמת ההצפנה.

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

הצפנה ופיענוח

ב-CKKS המפתח הפרטי sk הוא פולינום (מעל חוג המנה שתואר למעלה) שבו המקדמים הם ערכים שלמים אקראיים ו"קטנים". למשל ברוב הספריות המממשות את CKKS כל המקדמים של sk הם 0, 1, או 1-. הפולינום שהתקבל בשלב הקידוד שתואר למעלה משמש כמסר המוצפן (ה-plaintext). ההצפנה של מסר (כלומר פולינום) m היא זוג של פולינומים (a,b) כך ש $a+b*sk=m+e$, כאשר e הוא רעש קטן אקראי (החיבורים והכפלים המופיעים כאן הם פעולות על פולינומים מעל חוג המנה כפי שתואר למעלה). כלומר, מי שמחזיק בזוג הפולינומים של ההצפנה וגם ב-sk יכול בקלות לבצע את החישוב הנ"ל ולפענח את המסר המקורי m, עם רעש קטן.

השגיאה שבהצפנה היא חיונית ומוכנסת באופן מכוון כיוון שבלעדיה יהיה קל מדי לפענח את הצופן גם בלי sk. השגיאה הופכת את בעיית הפענוח לבעיה קשה (השקולה לבעיית Learning With Errors של עודד רגב). המפתח הפומבי pk מכיל מספיק מידע כדי לאפשר בקלות מציאת זוג פולינומים (a,b) שכאלה בהינתן m, והוא מכיל בתוכו רעש קטן שיוביל לרעש בהצפנות הנובעות ממנו. תהליך ההצפנה מוסיף עוד רעש אקראי נוסף כדי להבטיח שהצפנות חוזרות של אותו מסר יהיו שונות זו מזו.

ביצוע חישובים הומומורפים על ההצפנות

המטרה של סְכֶמַת הצפנה הומומורפית היא כאמור לאפשר חישוב על הנתונים המוצפנים בעזרת ביצוע חישובים על ההצפנות בלבד. קל לראות למשל שאם

$a1+b1*sk=m1+e1$

וגם

$a2+b2*sk=m2+e2$

אז גם

$(a1+a2)+(b1+b2)*sk=(m1+m2)+(e1+e2)$.

במילים אחרות אם (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 פולינומים. כדי לפענח הצפנה שכזאת יש לחשב את $a3+b3*sk+c3*sk^{2}$. באופן דומה ניתן גם להחזיק הצפנות עם מספר גדול יותר של רכיבים פולינומיים. הבעיה היא שמספר הרכיבים ילך ויגדל אחרי כל חישוב מכפלה, ויכביד על דרישות הזיכרון וזמן החישוב מעל ההצפנות. לכן נתמכת פעולת "יישור" relinearization, המחזירה את ההצפנה לצורה הכוללת רק זוג רכיבים. פעולה זו נעזרת במפתח פומבי מיועד שהונפק מראש למען מטרה זו.

תחזוקת הסקאלה של הצופן ו-Bootstrap

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

הבעיה היא שהחישובים על ההצפנות הם כאמור מודולארים מעל חוג שאריות של מספר q כלשהו, ולכן יש להקפיד שהערכים המוצפנים לא יחרגו מגבול זה. לכן מדי פעם יש להקטין את הסקאלה על ידי בצוע פעולת rescale הכוללת בין השאר את חלוקת הערך יחד עם הסקאלה שלו במספר כלשהו. כך כאמור את היצוג "320,000 עם סקאלה של 1,000,000" ניתן להחליף ביצוג השקול של "32 עם סקאלה של 100". בדוגמה הזו פעולת ה-rescale הייתה מדויקת, אך בדרך כלל החלוקה הכלולה בפעולת ה-rescale גם דורשת עיגול הגורר אחריו רעש תואם. לכן הפרקטיקה המקובלת היא לדחות את פעולת ה-rescale עד כמה שניתן, כדי לחסוך בפעפוע השגיאה שיגביר את הרעש בהמשך החישוב. פעולת ה-rescale היא גם לעיתים נחוצה כדי לאפשר חיבור בין הצפנות. בניגוד לכפל אשר ניתן לבצע בין זוג הצפנות בעלות סקאלות שונות (כמו בדוגמה למעלה), הרי שאי אפשר לחבר בין זוג הצפנות שכזה. לשם כך יש להקדים לפעולת החיבור את פעולת ה-rescale שתביא את הסקאלה של המחובר עם הסקאלה הגבוהה להיות שווה לסקאלה של המחובר השני.

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

אופטימיזציות מקובלת ל CKKS

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

• יצוג המקדמים הענקיים של הפולינומים על ידי אוסף של שאריות קטנות בעזרת משפט השאריות הסיני. שיטה זו מאפשרת גם לבצע את כל החישובים על המספרים הענקיים בעזרת פקודות המכונה הבסיסיות של המעבד, המוגבלות על ידי גודל האוגרים\רגיסטרים של המכונה, ובכך להאיץ את החישובים עוד יותר.
• יצוג הפולינומים רבי המקדמים בעזרת התמרת NTT (Number Theoretic Transform). זוהי התמרה של פולינומים עם מקדמים בחוג השלמים עם שארית, הדומה להתמרת פורייה ואשר מאפשרת כָּמוֹהָ להיעזר באלגוריתם דמוי FFT כדי להאיץ את הפעולה של מכפלת זוג פולינומים מסיבוכיות $O(N^{2})$ לסיבוכיות $O(N\cdot \log {N})$.

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

• HEAAN - ספריה פתוחה המממשת את סְכֶמַת CKKS
• HElib - ספריה פתוחה המממשת סכמות הצפנה הומומורפית
• Palisade - ספריה פתוחה המממשת סכמות הצפנה הומומורפית
• Microsoft SEAL ספריה פתוחה המממשת סכמות הצפנה הומומורפית