💻 computer science

Low-Latency Bootstrapping for CKKS using Roots of Unity

تقدم هذه الورقة "جذور الوحدة المتناثرة" (SPRU)، وهي خوارزمية إعادة تشغيل (bootstrapping) مبتكرة لمخطط التشفير المتماثل CKKS، تدمج الحساب النمطي في جذور الوحدة المركبة لتقليل العمق الضربي بشكل كبير وتحقيق تحسن في زمن الاستجابة يصل إلى 5 أضعاف مقارنة بالطرق التقليدية.

المؤلفون الأصليون: Jean-Sebastien Coron, Robin Koestler

نُشر 2026-07-31

📖 6 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Jean-Sebastien Coron, Robin Koestler

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك تحاول إرسال رسالة سرية إلى صديق، لكنك لا تثق في مكتب البريد. تقوم بقفل رسالتك داخل صندوق، لكن مكتب البريد يحتاج إلى فرز الصندوق، وتكديسه، وربما فتحه للتحقق من العنوان دون رؤية ما بداخله أبداً. هذا هو سحر التشفير المتماثل كلياً (Fully Homomorphic Encryption - FHE). فهو يسمح للحواسيب بإجراء عمليات حسابية على البيانات وهي لا تزال مغلقة في شكلها المشفر. فكر في الأمر كأنه مطبخ سحري حيث يمكنك خبز كعكة باستخدام مكونات لا تزال داخل عبواتها المختومة وغير المفتوحة؛ الفرن يقوم بالعمل، وعندما تفتح الصندوق في النهاية، تجد كعكة طازجة، لكن الفرن لم يعرف أبداً ما هي المكونات.

ومع ذلك، هناك عقبة. في كل مرة يقوم فيها الكمبيوتر بعملية حسابية على هذه البيانات المغلقة، يُضاف جزء ضئيل من "الضجيج" أو التشويش إلى الصندوق، مثل تراكم الغبار على عدسة. إذا قمت بالكثير من العمليات الحسابية، يصبح الضجيج عالياً جداً لدرجة أن الرسالة تصبح مشوشة وغير قابلة للقراءة. ولإصلاح ذلك، يستخدم العلماء عملية تسمى Bootstrapping (إعادة التمهيد). إنها تشبه زر إعادة ضبط سحري: يأخذ الكمبيوتر الصندوق المغلق والمشوش، ويقوم بحيلة معقدة لتنظيف الغبار، ثم يضع الرسالة في صندوق جديد ونظيف حتى يمكن استكمال العمليات الحسابية. المشكلة هي أن حيلة التنظيف هذه بطيئة وثقيلة للغاية، مثل محاولة غسل سيارة بفرشاة أسنان. فهي تستهلك الكثير من قدرة المعالجة مما يجعل التطبيقات الواقعية تبدو بطيئة.

هنا يأتي دور ورقة بحثية جديدة من إعداد جان-سيبيستين كورون وروبن كوستلر. لقد قدموا طريقة جديدة ذكية لأداء عملية "التنظيف" هذه، تسمى SPRU bootstrapping (إعادة تمهيد جذور الوحدة المتفرقة). فبدلاً من الطريقة القديمة الثقيلة التي تحاول تقريب منحنى معقد (مثل موجة جيبية)، وجدوا طريقة لتعيين البيانات مباشرة على دائرة من الأرقام تسمى "جذور الوحدة". تخيل بدلاً من محاولة تنظيف السيارة بفرشاة أسنان، أنك تقوم فقط بتمرير السيارة على دوار (كاروسيل) ضخم يدور ويمسح الغبار عنها بشكل طبيعي أثناء دورانه. طريقتهم أسرع وأخف وزناً بكثير، خاصة عندما تتعامل مع عدد صغير من عناصر البيانات في وقت واحد. ومن خلال استخدام هذا النهج الجديد، أظهروا أن الوقت المستغرق لإعادة ضبط التشفير يمكن تقليله بنسبة تصل إلى 5 أضعاف مقارنة بالطريقة القياسية، مما يجعل الحوسبة السرية تبدو أكثر واقعية من كونها مجرد حلم بعيد.

الطريقة القديمة: الرافعة الثقيلة

لفهم سبب تميز هذه الحيلة الجديدة، دعونا ننظر إلى كيفية عمل الطريقة القديمة. في نظام تشفير CKKS القياسي (الأكثر شيوعاً للقيام بالعمليات الحسابية على الأعداد العشرية)، كانت عملية الـ bootstrapping تشبه محاولة تخمين شكل جبل عن طريق رسم خط سلس فوقه. كان على الكمبيوتر تقييم كثير حدود معقد (معادلة رياضية متطورة) يقرب عملية "الاختزال النمطي" (Modular Reduction). فكر في الاختزال النمطي كوسيلة لطي خط أعداد طويل في دائرة ليناسب العودة إلى صندوق صغير. حاولت الطريقة القديمة رسم موجة جيبية (خط متموج) لمحاكاة عملية الطي هذه.

بينما نجح هذا، إلا أنه كان مجهداً. فقد تطلب الأمر تكدساً عميقاً من العمليات الرياضية، مما يعني أن الكمبيوتر كان عليه استخدام "بُعد حلقة" (Ring Dimension) كبير جداً (وهو مقياس لحجم الملعب الرياضي). كان هذا يشبه محاولة الجري في ماراثون وأنت تحمل حقيبة ظهر ثقيلة؛ مما أدى إلى إبطاء كل شيء وحد من كمية العمل المفيد الذي يمكن القيام به بعد إعادة الضبط. ويشير المؤلفون إلى أن "العمق الضربي" العالي هذا (عدد طبقات الرياضيات التي يجب المرور بها) كان هو العائق الرئيسي، مما جعل العملية بطيئة جداً للاستخدام العملي، خاصة عندما تحتاج لمعالجة عدد قليل من الأرقام في المرة الواحدة.

الطريقة الجديدة: دوار الجذور

تغير فكرة المؤلفين الجديدة، SPRU bootstrapping، قواعد اللعبة عبر تخطي عملية التقريب الثقيلة تماماً. فبدلاً من محاولة رسم خط متموج لمحاكاة عملية الطي، أدركوا أنه يمكنهم ببساطة دمج (Embed) البيانات مباشرة في "جذور الوحدة".

إليك تشبيه بسيط: تخيل أن الطريقة القديمة كانت تشبه محاولة ترجمة شفرة سرية عن طريق كتابة مدخل قاموس طويل ومعقد لكل حرف على حدة؛ كان الأمر يستغرق وقتاً طويلاً. أما الطريقة الجديدة فهي كإدراك أن الشفرة السرية هي في الواقع مجموعة من المفاتيح التي تناسب قفلاً معيناً تماماً. بدلاً من الترجمة، أنت فقط تقوم بتدوير المفتاح.

من الناحية التقنية، يقومون بتعيين المجموعة الجمعية (الطريقة التي تُجمع بها الأرقام) مباشرة في جذور الوحدة المركبة (نقاط على دائرة في نظام الأعداد المركبة). وبما أن نظام تشفير CKKS يفهم هذه الأعداد المركبة بشكل أصيل، يمكن للكمبيوتر إجراء عملية "التنظيف" مباشرة، دون الحاجة لتقريب موجة جيبية. إنه يشبه الانتقال من بناء جسر باستخدام طوب فردي إلى استخدام قوس جاهز يناسب المكان تماماً.

الخلطة السرية: التفرق والتعبئة

لم يتوقف البحث عند الخريطة الجديدة فحسب؛ بل قدم المؤلفون أيضاً تحسينين ذكيين لجعل العملية أسرع، خاصة عند التعامل مع عدد قليل من خانات البيانات (مثل بضعة أرقام في قائمة).

تعبئة البتات (Packing the Bits): في الأيام الخوالي، إذا كان لديك مفتاح سري يحتوي على 1,000 بت، كان على الكمبيوتر التعامل مع كل بت على حدة. أدرك المؤلفون أنه يمكنهم "تعبئة" هذه البتات في خانات التشفير، مثل حشر 1,000 رسالة في صندوق بريد واحد عالي الكفاءة. قلل هذا من عدد العمليات الحسابية الثقيلة المطلوبة من كمية هائلة إلى كمية لوغاريتمية (فكر في الأمر كاختصار قائمة طويلة إلى ملخص قصير).
خدعة الكتلة المتفرقة (The Sparse Block Trick): افترضوا أيضاً أن المفتاح السري له هيكل خاص: بدلاً من البتات العشوائية، يتم تقسيم المفتاح إلى كتل حيث يوجد بت واحد فقط "1" في كل كتلة والبقية "0". هذا يشبه وجود صف من مفاتيح الإضاءة حيث يكون مفتاح واحد فقط في كل مجموعة من عشرة في وضع التشغيل. باستخدام هذا الهيكل "المتفرق"، تمكنوا من استبدال العديد من خطوات الضرب الصعبة بخطوات جمع بسيطة. هذا هو الفرق بين ضرب قائمة طويلة من الأرقام وبين مجرد جمع عدد قليل منها. لقد قلل هذا من "العمق" الحسابي بشكل أكبر، من برج شاهق إلى درج صغير.

النتائج: تسريع السحر

اختبر المؤلفون طريقتهم الجديدة باستخدام مكتبة OpenFHE، وهي أداة شائعة لبناء برمجيات التشفير. وقارنوا بين عملية SPRU bootstrapping وبين الطريقة القديمة الثقيلة.

كانت النتائج مذهلة في سيناريوهات محددة. فعندما يتم عمل bootstrapping لرموز تشفير ذات عدد قليل من الخانات (وهو أمر شائع في العديد من التطبيقات الواقعية)، كانت طريقتهم الجديدة أسرع بما يصل إلى 5 مرات (تقليل زمن الاستجابة بمقدار 5 أضعاف). وهذا أمر بالغ الأهمية لأن "زر إعادة الضبط" لا يضطر للانتظار طويلاً، مما يسمح للكمبيوتر بالعودة إلى القيام بعمل مفيد بسرعة أكبر.

ومع ذلك، تشير الورقة البحثية بحذر إلى أن هذا ليس حلاً سحرياً لـ كل حالة. فإذا كنت تحاول معالجة عدد هائل من الخانات (قائمة ضخمة من البيانات)، فقد تظل الطريقة الأصلية أكثر كفاءة. ولكن في حالات كثة نتعامل فيها مع دفعات صغيرة من البيانات، يوفر هذا النهج الجديد تسريعاً كبيراً.

لماذا يهم هذا؟

إن جمال هذا العمل يكمن في أنه لا يكتفي فقط بتعديل الأرقام؛ بل يغير بشكل جذري طريقة تفكيرنا في عملية الـ bootstrapping. ومن خلال الابتعاد عن تقريبات كثيرات الحدود الثقيلة واستغلال القدرات الأصلية لنظام التشفير، أثبت المؤلفون أنه يمكننا جعل التشفير المتماثل كلياً أكثر عملية.

لقভাবে أثبتوا أنه باستخدام "جذور الوحدة" هذه وتقنيات التعبئة الذكية، يمكننا تقليل الوقت وقدرة المعالجة اللازمة للحفاظ على البيانات المشفرة صالحة للاستخدام بشكل كبير. وبينما تركز الورقة البحثية على التفاصيل التقنية والرياضيات الكامنة وراء الكواليس، فإن الخلاصة واضحة: إن الحلم بإجراء حسابات معقدة على بيانات سرية دون تباطؤ يقترب أكثر من أن يصبح حقيقة. لقد قدم المؤلفون طريقة أخف وأسرع للحفاظ على استمرارية السحر، مما يجعل من الممكن تخيل مستقبل حيث يمكن معالجة بياناتك الخاصة في السحابة دون أن تُرى أبداً، ودون انتظار النتائج للأبد.

ملخص تقني: بدء التشغيل منخفض التأخير لـ CKKS باستخدام جذور الوحدة

بيان المشكلة

يدعم مخطط التشفير المتماثل CKKS الحساب التقريبي على الأعداد المركبة التقريبية، مما يجعله مناسبًا للتعلم الآلي الآمن والحوسبة السحابية. ومع ذلك، فإن عملية بدء التشغيل (bootstrapping) في CKKS تمثل عنق زجاجة حرج، وهي عملية مطلوبة لتحديث النصوص المشفرة وتمكين عمق حسابي غير محدود.

تعتمد طريقة بدء التشغيل الأصلية في CKKS [CHK+18a] على التقييم المتماثل لمتعدد حدود يقرب دالة الاختزال النمطي (تحديدًا دالة الجيب الموزونة). يعاني هذا النهج من عيبين رئيسيين:

العمق الضربي العالي: يتطلب تقريب متعدد الحدود دائرة عميقة، مما يستلزم معامل نص مشفر كبير.
عدم الكفاءة لعدد الفتحات الصغير: تتناسب تعقيد الطريقة الأصلية مع عدد الفتحات ( $n$ ) وأبعاد الحلقة ( $N$ )، وغالبًا ما تتطلب عمليات بمقدار $O(\log n + \log N)$ . هذا العمق العالي يجبر على استخدام أبعاد حلقة أكبر للحفاظ على الأمان، مما يؤدي إلى زيادة زمن التأخير.

حدد المؤلفون الحاجة إلى خوارزمية بدء تشغيل تقلل من العمق الضربي، مما يسمح باستخدام أبعاد حلقة أصغر وزمن تأخير أقل بشكل ملحوظ، خاصة بالنسبة للنصوص المشفرة ذات عدد الفتحات الصغير.

المنهجية: جذور الوحدة المتناثرة (SPRU)

يقدم البحث بدء تشغيل جذور الوحدة المتناثرة (SPRU)، وهي خوارزمية مبتكرة تغير بشكل جذري كيفية إجراء الاختزال النمطي في CKKS.

المفهوم الأساسي: التضمين الأصيل

بدلاً من تقريب الاختزال النمطي عبر دالة الجيب، يقوم بدء تشغيل SPRU بتضمين المجموعة الجمعية $\mathbb{Z}_q$ مباشرة في المجموعة الضربية لجذور الوحدة المركبة. يستخدم المؤلفون التشاكل:
$f: \mathbb{Z}_q \to \mathbb{C}, \quad x \mapsto \exp(2i\pi \cdot x/q)$

لمعادلة فك التشفير من نوع LWE $m = \langle s, c \rangle \pmod q$ ، يلاحظ المؤلفون أن:
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} \exp(2i\pi \cdot c_k s_k / q)$
بما أن بتات مفتاح السر $s_k \in \{0, 1\}$ تعمل كأدوات اختيار، يمكن إعادة كتابة هذا الضرب كالتالي:
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} (1 + (\exp(2i\pi \cdot c_k/q) - 1) \cdot s_k)$
من خلال عزل الجزء التخيلي وتطبيق عامل قياس خطي، يمكن استعادة الرسالة الأصلية $m$ . ويمكن تقييم هذه المعادلة متماثليًا داخل مخطط CKKS دون الحاجة لتقريب دالة الجيب بمتعدد حدود.

التحسينات الرئيسية

لجعل هذا النهج عمليًا، قدم المؤلفون تحسينين حاسمين:

تعبئة بتات مفتاح السر:
بدلاً من تشفير كل بت من مفتاح السر بشكل فردي، يتم تعبئة الـ $N$ بت في الـ $N/2$ فتحة من نصين مشفرين من نوع CKKS. كما يتم تعبئة الحدود $(\exp(2i\pi \cdot c_k/q) - 1)$ بنفس الطريقة. يتم حساب حاصل ضرب هذه الحدود باستخدام عامل الضرب ( $Pr_{N/2 \to 1}$ )، والذي يقلل عدد الضربات المتماثلة من $O(N)$ إلى $O(\log N)$ .
مفتاح السر ذو الكتل المتناثرة:
يفترض المؤلفون مفتاح سر مهيكل مقسم إلى $h$ من الكتل، حيث حجم كل كتلة $B = N/h$ ، وتحتوي كل كتلة بالضبط على بت واحد غير صفري (واحد '1'). هذا الهيكل يسمح باستبدال الضرب داخل كل كتلة بعملية جمع.

يتم حساب الجمع داخل الكتل باستخدام عامل الأثر (Trace Operator) ( $Tr_{N/2 \to h}$ )، والذي يتضمن فقط عمليات الجمع والتحويلات الذاتية (بدون عمق ضربي).
يتم إجراء الضرب النهائي على نتائج الكتل الـ $h$ .
النتيجة: انخفض العمق الضربي من $\log_2 N + 2$ إلى $\log_2 h + 1$ . وبما أن $h \ll N$ ، فإن هذا يقلل بشكل كبير من حجم المعامل المطلوب.

التوسع ليشمل فتحات متعددة

تم تعميم الطريقة للتعامل مع $n$ من الفتحات (حيث $n \le N/2$ ). يتم استخراج مصفوفة فك التشفير، وتُطبق معادلة بدء التشغيل بالتوازي على كل مكون من مكونات الرسالة الـ $n$ . التعقيد هو $O(n + \log N)$ ، وهو أعلى تقاربيًا من بدء تشغيل CKKS الأصلي ( $O(\log n + \log N)$ ) بالنسبة لـ $n$ الكبيرة. ومع ذلك، بالنسبة لـ $n$ الصغيرة، يوفر العمق الضربي المنخفض أداءً عمليًا متفوقًا.

المساهمات الرئيسية

خوارزمية بدء تشغيل SPRU: تقنية جديدة لبدء تشغيل CKKS تستبدل تقريب دالة الجيب بالتقييم الأصيل لجذور الوحدة.
تقليل العمق الضربي: من خلال الاستفងادة من مفاتيح السر ذات الكتل المتناثرة وعامل الأثر، تحقق الخوارزمية عمقًا ضربيًا قدره $O(\log h)$ ، وهو أقل بكثير من $O(\log N)$ في الطريقة الأصلية.
تنفيذ محسن: يوفر المؤلفون تنفيذًا مفتوح المصدر باستخدام مكتبة OpenFHE بلغة ++C، مما يوضح التوافق مع حسابات نظام الباقي (RNS) وتحسينات التحويل الخطي الموجودة (SlotToCoeff).
التحليل الأمني: تحليل رسمي لتوزيع مفتاح الثنائي الكتلي، مما يظهر أنه لا يضعف أمان مشكلة RLWE ضد الهجمات المعروفة (الهجمات الهجينة المزدوجة ولقاء المنتصف)، بشرط ضبط المعلمات بشكل صحيح.

النتائج

قام المؤلفون باختبار أداء بدء تشغيل SPRU مقابل بدء تشغيل CKKS الأصلي باستخدام مكتبة OpenFHE مع معايير أمان 128 بت.

تقليل زمن التأخير: بالنسبة للنصوص المشفرة ذات عدد فتحات صغير، يحقق بدء تشغيل SPRU تقليلًا في زمن التأخير يصل إلى 5 أضعاف.
الكفاءة: يسمح تقليل العمق الضربي باستخدام أبعاد حلقة أصغر، مما يساهم بشكل أكبر في تسريع الأداء.
التوازي: الطريقة قابلة للتوازي بشكل كبير؛ فمع وجود $n$ من المعالجات، يمكن تحقيق تعقيد $O(\log N)$ مشابه للطريقة الأصلية.

الأهمية والادعاءات

يزعم البحث أن بدء تشغيل SPRU يقدم بديلًا عمليًا لبدء تشغيل CKKS الأصلي، مستهدفًا تحديدًا السيناريوهات التي يكون فيها زمن التأخير المنخفض أمرًا بالغ الأهمية وعدد الفتحات فيها صغيرًا. ومن خلال تجنب التقريبات متعددة الحدود المكلفة وتقليل العمق الضربي، تمكن الطريقة من تجديد النصوص المشفرة بشكل أكثر كفاءة.

يضع المؤلفون عملهم كخطوة مهمة نحو جعل التشفير المتماثل الكامل أكثر جدوى للتطبيقات الواقعية التي تتطلب بدء تشغيل متكرر. ويشيرون إلى أنه بينما تم تحسين طريقتهم لعدد فتحات صغير، فإنها تكمل الأعمال الحالية (مثل العمل المستقل لـ Cheon et al. [CHKS25] الذي يركز على بدء تشغيل كامل لـ $N/2$ فتحة) عبر تقديم مقايضة مختلفة تفضل زمن التأخير على التوازي الضخم لمجموعات البيانات الصغيرة.

يخلص البحث إلى أن تقليل العمق الضربي هو المحرك الأساسي للكفاءة، مما يحرر المزيد من مستويات الحساب للعمليات المفيدة بعد بدء التشغيل ويسمح باستخدام أبعاد حلقة أصغر وأسرع.