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

ב[[קריפטוגרפיה]], '''CKKS''' היא שיטת [[הצפנה הומומורפית]] פופולאריתפופולרית המיועדת לבצוע חישובים על צפנים המצפינים מספרים ממשיים, וזאת בניגוד לשיטות קודמות שהתמקדו בחישובים על הצפנות של שלמים. שם הסְכֶמָה מורכב מהאותיות הפותחות את שמות מחברי המאמר המקורי שבו הוצגה השיטה{{הערה|שם=CKKS|{{Citation | title=Homomorphic Encryption

for Arithmetic of Approximate Numbers | author1=Jung Hee Cheon |author2=Andrey Kim | |author3=Miran Kim |author4=Yongsoo Song| publisher=Springer, Cham | journal=International Conference on the Theory and Application of Cryptology and Information Security |year=2017}}}}, Kim, Kim, Cheon ו-Song.

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

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

Homomorphic Encryption | author1=Jung Hee Cheon |author2=Kyoohyung Han |author3=Andrey Kim | |author4=Miran Kim |author5=Yongsoo Song| publisher=Springer, Cham | journal=Annual International Conference on the Theory and Applications of Cryptographic Techniques |year=2018}}}} {{הערה|שם=CKKS-BS2|{{Citation | title=Improved 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 היא סְכֶמַת הצפנה עם [[מפתח ציבורי]], כלומר מפתח ציבורי מאפשר לכל מי שמחזיק\ה בו להצפין מידע, אך רק מי שמחזיק\ה במפתח הפרטי יכול\ה אח"כאחר כך לפענח את הצופן. במקרה של סכמות הצפנה הומומורפיות כמו CKKS, המפתח הפומבי מאפשר בנוסף לכך גם לבצע חישובים מעל ההצפנות (אך לא לגלות את תוצאת החישובים הללו).

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

סְכֶמַת CKKS מחזיקה את ההצפנות בצורה של [[פולינום|פולינומים]], ובאופן מדויק יותר של פולינומים ב[[חוג מנה|חוג המנה]] מעל [[פולינום ציקלוטומי]] עם מקדמים שלמים בחוג השאריות מודולו q כלשהו. כך, כל החישובים ההומומורפים המבוצעים על ההצפנות הם חיבורים והכפלות של פולינומים מעל חוג המנה הזה. במילים פשוטות יותר אולי, אם במהלך החישוב מתקבל מקדם פולינום גדול מ-q אז יש להשאיר רק את השארית שלו אחרי חלוקה ב-q, ואם מתקבל פולינום הגדול מפולינום המנה אז יש להשאיר רק את השארית של הפולינום כולו אחרי חלוקה שלו בפולינום המנה.

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

'''דוגמאדוגמה''': נניח שהווקטור המוצפן הוא באורך 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>. ארבעת שורשי היחידה הפרימיטיבים מסדר 4n=8 הם

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

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

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

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

<math> a1 + b1 * sk = m1 + e1 </math> וגם

<math> a2 + b2 * sk = m2 + e2 </math> אז גם

<math> (a1+a2) + (b1+b2) * sk = (m1+m2) + (e1+e2) </math>.

במילים אחרות אם (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 פולינומים. כדי לפענח הצפנה שכזאת יש לחשב את

<math>a3+b3*sk+c3*sk^2</math>. באופן דומה ניתן גם להחזיק הצפנות עם מספר גדול יותר של רכיבים פולינומיים. הבעיה היא שמספר הרכיבים ילך ויגדל אחרי כל חישוב מכפלה, ויכביד על דרישות הזכרוןהזיכרון וזמן החישוב מעל ההצפנות. לכן נתמכת פעולת "יישור" relinearization, המחזירה את ההצפנה לצורה הכוללת רק זוג רכיבים. פעולה זו נעזרת במפתח פומבי מיועד שהונפק מראש למען מטרה זו.

כפי שתואר למעלה, להצפנה צמודה סְקָאלָה מתאימה שמציינת את הפקטור שיש לחלק בו כדי לקבל את המסר המוצפן בסוף תהליך הפענוח ופתיחת הקוד. למשל את המסר שערכו 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 גדול מאוד (למשל <math>2^{800}</math>), אבל בכל זאת אחרי מספיק מכפלות התקרה של q תרד נמוך מדי כדי לאפשר את המשך החישוב. כדי לאפשר חישוב בלתי מוגבל (כלומר סְכֶמַת הצפנה הומומורפית מלאה) יש להסיר מגבלה זו, ואמנם כותבי המאמר המקורי הציעו כאמור מספר דרכים לבצע פעולת bootstrap המחזירה את q לתחום הערכים הגבוהים שיאפשרו את המשך החישוב. יש לשים לב שפעולת ה-bootstrap של CKKS נועדה לאפשר את המשך החישוב והיא אינה מסירה את הרעש שהצטבר בערכים המוצפנים (למעשה היא מגדילה מעט את הרעש הנובע מחישוב פעולת ה-bootstrap עצמה). זאת בשונה מסכמות הומומורפיות אחרות, כמו BGV, שם ה-bootstrap מאפשר את המשך החישוב ע"יעל ידי הסרת הרעש שבהצפנה עצמה.

החישובים ההומומורפים המבוצעים ע"יעל ידי CKKS כוללים כאמור פעולות חיבור וכפל של פולינומים. פולינומים אלה בד"כבדרך כלל כוללים אלפים רבים של מקדמים, והמקדמים עצמם גם כן בד"כבדרך כלל גדולים מאוד. כך, החישוב ההומורמופי הוא איטי בכמה סדרי גודל יחסית לחישוב המקביל על הנתונים המקוריים שלא תחת הצפנה. מאז הפרסום המקורי של השיטה ב-2017 הוצעו ומומשו מספר אופטמיזציות ל-CKKS{{הערה|שם=CKKS-2|{{Citation | title=A Full RNS Variant of

* יצוג המקדמים הענקיים של הפולינומים ע"יעל ידי אוסף של שאריות קטנות בעזרת [[משפט השאריות הסיני]]. שיטה זו מאפשרת גם לבצע את כל החישובים על המספרים הענקיים בעזרת פקודות המכונה הבסיסיות של המעבד, המוגבלות ע"יעל ידי גודל ה[[אוגר (מחשבים)|אוגרים]]\רגיסטרים של המכונה, ובכך והאיץ את החישובים עוד יותר.

* יצוג הפולינומים רבי המקדמים בעזרת התמרת NTT (Number Theoretic Transform). זוהי התמרה של פולינומים עם מקדמים בחוג השלמים עם שארית, הדומה להתמרת פורייה ואשר מאפשרת כָּמוֹהָ להעזרלהיעזר באלגוריתם דמוי [[FFT]] כדי להאיץ את הפעולה של מכפלת זוג פולינומים מסיבוכיות <math>O(N^2)</math> לסיבוכיות <math>O(N\cdot\log{N})</math>.