CKKS – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ הגהה |
|||
שורה 57:
החישובים ההומומורפים המבוצעים על ידי CKKS כוללים כאמור פעולות חיבור וכפל של פולינומים. פולינומים אלה בדרך כלל כוללים אלפים רבים של מקדמים, והמקדמים עצמם גם כן בדרך כלל גדולים מאוד. כך, החישוב ההומורמופי הוא איטי בכמה סדרי גודל יחסית לחישוב המקביל על הנתונים המקוריים שלא תחת הצפנה. מאז הפרסום המקורי של השיטה ב-2017 הוצעו ומומשו מספר אופטמיזציות ל-CKKS{{הערה|שם=CKKS-2|{{Citation | title=A Full RNS Variant of
Approximate Homomorphic Encryption | author1=Jung Hee Cheon |author2=Kyoohyung Han |author3=Andrey Kim | |author4=Miran Kim |author5=Yongsoo Song| publisher=Springer, Cham | journal=International Conference on Selected Areas in Cryptography |year=2018}}}} המאפשרות ביצועים סבירים לחישובים שימושיים כמו [[למידת מכונה]] עם [[רשת עצבית|רשתות ניורונים]] מוצפנות, שירותי מסד נתונים מוצפן ועוד. אלה כוללות בין השאר:
* יצוג המקדמים הענקיים של הפולינומים על ידי אוסף של שאריות קטנות בעזרת [[משפט השאריות הסיני]]. שיטה זו מאפשרת גם לבצע את כל החישובים על המספרים הענקיים בעזרת פקודות המכונה הבסיסיות של המעבד, המוגבלות על ידי גודל ה[[אוגר (מחשבים)|אוגרים]]\רגיסטרים של המכונה, ובכך
* יצוג הפולינומים רבי המקדמים בעזרת התמרת NTT (Number Theoretic Transform). זוהי התמרה של פולינומים עם מקדמים בחוג השלמים עם שארית, הדומה להתמרת פורייה ואשר מאפשרת כָּמוֹהָ להיעזר באלגוריתם דמוי [[FFT]] כדי להאיץ את הפעולה של מכפלת זוג פולינומים מסיבוכיות <math>O(N^2)</math> לסיבוכיות <math>O(N\cdot\log{N})</math>.
| |||