CKKS – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 31:
<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 שמחלק את הערך ואת הסקאלה במידה כלשהי, נדרש לחלק את את q (כלומר את הגבול העליון של הערכים) באותה מידה. כך בדוגמא שהובאה למעלה ה rescale חילקה את הערך ואת הסקאלה ב-10,000, ולכן אם q היה נניח מלכתחילה 1,000,000, הרי שאחרי ה-rescale הוא יקטן ל-100 ויגביל מאוד את החישוב בהמשך. לכן בד"כ מתחילים עם q גדול מאוד (למשל <math>2^800</math>), אבל בכל זאת אחרי מספיק מכפלות התקרה של q תרד נמוך מדי כדי לאפשר את המשך החישוב. כדי לאפשר חישוב בלתי מוגבל (כלומר סכמת הצפנה הומומורפית "מלאה") יש להסיר מגבלה זו, ואמנם כותבי המאמר המקורי הציעו כאמור מספר דרכים לבצע פעולת "
===אופטימיזציות מקובלת ל CKKS===
| |||