آموزش الگوریتم رمزنگاری همومورفیک CKKS؛ پیاده‌سازی جمع و ضرب رمزنگاری‌شده

این مقاله بخشی از یک سری آموزشی درباره طرح رمزنگاری همومورفیک (Homomorphic Encryption) به نام CKKS است. در مقاله قبلی با روتین‌های رمزنگاری متقارن و نامتقارن و حساب چندجمله‌ای مدولار آشنا شدیم. در این بخش، تمرکز بر روی اجرای عملیات جمع و ضرب روی سایفرتکست‌ها (Ciphertexts) بدون استفاده از ریلینیرایزاسیون (Relinearization) است.

برای سادگی در این آموزش، از فرم RNS صرف‌نظر شده و از یک مدولار ۶۴ بیتی $Q$ استفاده می‌کنیم که به این معنی است که فعلاً امنیت رمزنگاری را کنار گذاشته‌ایم تا روی منطق ریاضی الگوریتم تمرکز کنیم.

ساختار سایفرتکست در CKKS

سایفرتکست‌های CKKS در قالب زوجی از چندجمله‌ای‌ها $(c_0, c_1)$ در حلقه مدولار تعریف می‌شوند. روتین رمزگشایی در هر دو حالت متقارن و نامتقارن با محاسبه ضرب داخلی (Dot Product) با بردار $(1, s(x))$ انجام می‌شود که در آن $s(x)$ چندجمله‌ای کلید مخفی است. اگر میزان خطا (Error) به اندازه کافی کوچک باشد، الگوریتم رمزگشایی با تقسیم بر فاکتور مقیاس (Scale)، خطا را حذف کرده و پیام را استخراج می‌کند.

جمع سایفرتکست‌ها

جمع دو سایفرتکست بسیار ساده است. اگر دو سایفرتکست $(c_0, c_1)$ و $(d_0, d_1)$ داشته باشیم که به ترتیب به پیام‌های رمزنگاری‌شده مربوط می‌شوند، مجموع آن‌ها به صورت زیر تعریف می‌شود:

(c0 + d0, c1 + d1)

این تعریف برای هر دو حالت متقارن و نامتقارن یکسان است. در تحلیل خطا، جمع متغیرهای تصادفی ساب‌گوسی (Sub-Gaussian) منجر به انفجار خطا نمی‌شود، بلکه واریانس آن‌ها با یکدیگر جمع می‌شود. به عبارت دیگر، خطا به صورت خطی رشد می‌کند و الگوریتم پایداری خود را حفظ می‌کند.

ضرب سایفرتکست‌ها

ضرب سایفرتکست‌ها چالش‌برانگیزتر است. اگر تلاش کنیم ضرب را به صورت ساده و مشابه جمع تعریف کنیم، با عدم تطابق درجه چندجمله‌ای‌ها مواجه می‌شویم؛ زیرا ضرب دو عبارت خطی بر اساس کلید مخفی، جمله‌ای با درجه دو ($s^2$) تولید می‌کند.

بنابراین، ساختار سایفرتکست حاصل از ضرب به یک سه‌تایی تبدیل می‌شود:

(t0, t1, t2)

که برای رمزگشایی آن به ضرب داخلی با پایه کلید جدید یعنی $(1, s, s^2)$ نیاز داریم. این ساختار سه‌تایی سه ویژگی مهم دارد:

• رشد خطا: خطای حاصل از ضرب به صورت درجه‌دویی (Quadratic) رشد می‌کند.
• وابستگی به پین‌تکست: جمله خطی شامل مقادیر پیام و فاکتور مقیاس ($ riangle$) است.
• افزایش مقیاس: فاکتور مقیاس به توان دو ($ riangle^2$) می‌رسد و برای ادامه محاسبات باید به مقدار اولیه بازگردد.

چرا این موضوع برای مهندسان نرم‌افزار مهم است؟

رمزنگاری همومورفیک کلید اصلی محاسبات امن در فضای ابری (Cloud Computing) و یادگیری ماشین محرمانه (Privacy-Preserving Machine Learning) است. درک جزئیات پیاده‌سازی ریاضیاتی مانند نحوه مدیریت فاکتور مقیاس، کنترل خطای انباشته و ساختارهای سه‌تایی سایفرتکست به مهندسان کمک می‌کند تا کتابخانه‌های رمزنگاری را با بهینه‌سازی بالا و بدون نشت اطلاعات پیاده‌سازی کنند.