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