💻 computer science

Triple-Hoisted Baby-Step Giant-Step Linear Transformation over CKKS Homomorphic Encryption and Hardware Accelerator

تقدم هذه الورقة خوارزمية "خطوة الطفل والخطوة العملاقة" ثلاثية الرفع ومسرع أجهزة FPGA مُحسَّن للذاكرة، مما يقلل بشكل كبير من تدويرات النص المشفر، والوصول إلى الذاكرة خارج الرقاقة، وزمن انتقال الحوسبة للتحويلات الخطية في التشفير المتماثل CKKS.

المؤلفون الأصليون: Sajjad Akherati, Xinmiao Zhang

نُشر 2026-05-19

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Sajjad Akherati, Xinmiao Zhang

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

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

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

إليك تفصيل حلهم باستخدام تشبيهات بسيطة:

1. المشكلة: "الجهد الشاق" لنقل البيانات

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

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

2. الحل: نظام المصعد "ثلاثي الرفع"

يقترح المؤلفون خوارزمية جديدة تسمى خطوة الطفل العملاقة الثلاثية الرفع (Triple-Hoisted Baby-Step Giant-Step - TH-BSGS).

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

3. الأجهزة: "خط تجميع" مخصص

حتى مع وجود خوارزمية أفضل، يجب أن تُبنى الأجهزة لتلائمها. صمم المؤلفون مسرع FPGA مخصصاً (شريحة كمبيوتر متخصصة).

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

4. تحسين الذاكرة: مطبخ "في الوقت المناسب"

أعاد الورقة أيضاً تصميم مسار البيانات لتقليل الرحلات إلى "متجر البقالة" (الذاكرة خارج الشريقة).

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

الخلاصة

اختبر المؤلفون نظامهم الجديد على شريحة عالية الأداء (Xilinx Virtex UltraScale+). مقارنة بأفضل مسرعات الأجهزة الموجودة حالياً لهذه المهمة:

السرعة: جعلوا الحساب أسرع بـ 5.8 مرة (من حيث وقت الحساب الصافي).
الكفاءة: قللوا الحاجة لجلب البيانات من الذاكرة الخارجية بمقدار 2.9 مرة.
التكلفة: حققوا ذلك دون الحاجة إلى موارد أجهزة (شرائح وذاكرة) أكثر بكثير من أفضل التصاميم السابقة.

باختاً، وجدوا طريقة أذكى لتنظيم العمل وبنوا أداة متخصصة للقيام بذلك، محولين عملية بطيئة ومزدحمة بالمرور إلى عملية انسيابية عالية السرعة.

ملخص تقني: التحويل الخطي بخوارزمية "خطوة الطفل والخطوة العملاقة" ثلاثية الرفع فوق التشفير المتماثل من نوع CKKS ومسرع الأجهزة

بيان المشكلة
يتيح التشفير المتماثل (HE)، ولا سيما مخطط CKKS، الحسابات التي تحافظ على الخصوصية على البيانات المشفرة، وهو أمر بالغ الأهمية لتطبيقات مثل التشخيص الطبي، والتحليل المالي، وتسلسل الجينوم. وتعد عملية التحويل الخطي (HE-LT) عملية أساسية في الشبكات العصبية والمحولات القائمة على التشفير المتماثل. وبينما تسمح طريقة الأقطار (diagonal method) بإجراء HE-LT عن طريق حزم أقطار المصفوفات في كثيرات حدود، إلا أنها تتطلب عدداً باهظاً من عمليات تدوير التشفير (ciphertext rotations) للمصفوفات عالية الأبعاد. وتتضمن هذه الدورات عمليات التغيير الذاتي (automorphism) وتبديل المفاتيح (key-switching) المعقدة، مما يؤدي إلى عبء حسابي كبير ووصول هائل إلى الذاكرة خارج الرقاقة (off-chip memory). كما أن مسرعات الأجهزة الحالية، حتى تلك التي تستخدم تفكيك "خطوة الطفل والخطوة العملاقة" (BSGS) وتقنيات الرفع المزدوج (double-hoisting)، لا تزال تعاني من زمن انتقال كبير واختناقات في عرض نطاق الذاكرة، حيث تتطلب غالباً مئات الجيجابايت من نقل البيانات خارج الرقاقة لمجموعات المعلمات النموذجية.

المنهجية
يقترح البحث حلاً شاملاً يعالج التعقيد الخوارزمي وتدفق بيانات الأجهزة:

خوارزمية BSGS ثلاثية الرفع (TH-BSGS):
يقوم المؤلفون بتوسيع خوارزمية BSGS ذات الرفع المزدوج الحالية من خلال تفكيك "خطوة الطفل" (baby step) بشكل أكبر إلى طبقتين، مما يخلق بنية مكونة من ثلاث طبقات ( $n = n'_1 n'_2 n'_3$ ).

الرفع الثلاثي (Triple Hoisting): يتم تطبيق تقنية الرفع عبر جميع الطبقات الثلاث لعمليات التدوير. ومن خلال إعادة ترتيب الحسابات وتطبيق التغييرات الذاتية العكسية على مفاتيح التبديل، تضمن الخوارزمية أن عملية "التفكيك" (Decompose) — وهي خطوة تبديل مفاتيح مكلفة — تُنفذ مرة واحدة فقط لجميع الدورات الداخلية في طبقة ما.
تأخير تقليل المقياس (Delayed ModDown): على غرار طرق الرفع السابقة، يتم تأخير عمليات ModDown ودمجها. وفي التصميم المقترح، يتم تطبيق ModDown فقط على المجامع بدلاً من النواتج الوسيطة، مما يقلل بشكل كبير من عدد العمليات القياسية المطلوبة.
مرونة المقايضة (Trade-off Flexibility): من خلال ضبط عوامل التفكيك $n'_1, n'_2, n'_3$ ، تسمح الخوارزمية بمقايضات مرنة بين عدد مفاتيح التبديل المطلوبة (الذاكرة) والتعقيد الحسابي.

مسار بيانات محسّن للذاكرة:
لمعالجة زمن الانتقال الناتج عن الوصول إلى الذاكرة خارج الرقاقة، تم تقسيم خوارزمية TH-BSGS إلى ست مراحل متميزة.

تقسيم المراحل (Phase Partitioning): تمت إعادة هيكلة الخوارزمية بحيث تُقرأ البيانات من الذاكرة خارج الرقاقة، وتُعالج مع تخزين النتائج الوسيطة وإعادة استخدامها داخل الرقاقة، ثم تُكتب مرة أخرى فقط في نهاية كل مرحلة.
إعادة استخدام البيانات (Data Reuse): يعمل التصميم على تعظيم إعادة استخدام الذاكرة داخل الرقاقة من خلال جدولة دقيقة لتحميل مفاتيح التبديل وأجزاء كثيرات الحدود (polynomial limbs). على سبيل المثال، في الطبقات الوسطى، يتم تحميل مفاتيح التبديل في الذاكرة داخل الرقاقة وإعادة استخدامها عبر دورات متعددة لتقليل حركة البيانات.
ضبط التوازي (Parallelism Tuning): تم تقديم ستة معاملات توازي ( $m_1$ إلى $m_6$ ) لموازنة معالجة مفاتيح التبديل، وأجزاء كثيرات الحدود، والتشفيرات، لضمان ملاءمة التصميم لقيود ذاكرة FPGA داخل الرقاقة (مثل 43 ميجابايت على Xilinx U280).

بنية مسرع الأجهزة:
تم تصميم مسرع فعال يعتمد على FPGA لتنفيذ الخوارزمية المقترحة.

دائرة التبديل المحسّنة (Optimized Permutation Circuit): تم تقديم دائرة تبديل مبتكرة لتنفيذ التغيير الذاتي $\phi_r$ . ومن خلال استغلال الخصائص المحددة للتغيير الذاتي في مجال NTT وترتيب التخزين المعكوس لـ bit-reversed لمعاملات، يقلل التصميم من عدد المجمعات (multiplexers) إلى النصف مقارنة بالأعمال السابقة ويلغي الحاجة إلى أجهزة تخزين مؤقت (scratchpad memory buffers). وهذا يقلل زمن انتقال عملية التبديل إلى النصف.
المكونات النمطية (Modular Components): تتضمن البنية مصفوفة عناصر معالجة (PE) تدعم NTT و INTT والعمليات المعتمدة على المعاملات؛ ومصفوفة جامع شجري (Tree Adder) لعمليات الجمع؛ ومصفوفة دائرة التبديل (PC).

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

الابتكار الخوارزمي: اقتراح خوارزمية TH-BSGS، التي تفكك "خطوة الطفل" بشكل أكبر لتقليل عدد دورات التشفير وعمليات Decompose مقارنة بمنهج الرفع المزدوج (DH-BSGS).
تحسين مسار البيانات: استراتيجية تحسين الذاكرة القائمة على المراحل التي تقلل بشكل جذري من حركة البيانات خارج الرقاقة عبر تعظيم إعادة استخدام البيانات داخل الرقاقة، والمصممة خصيصاً للحسابات المعاد ترتيبها لخوارزمية TH-BSGS.
كفاءة الأجهزة: تطوير مسرع أجهزة يتميز بدائرة تبديل مبسطة تقلل من زمن انتقال التغيير الذاتي بنسبة 50% وتلغي الحاجة إلى ذاكرة تخزين مؤقت إضافية.

النتائج التجريبية
تم تصنيع التصميم على أجهزة Xilinx Virtex UltraScale+ (U280) وتقييمه مقابل أحدث مسرعات الأجهزة (بما في ذلك FAME و CHAM والتصاميم من [25]) تحت ثلاث مجموعات مختلفة من معلمات HE (المجموعات A و B و C) التي تدعم أمان 128 بت.

الوصول إلى الذاكرة خارج الرقاقة: يقلل التصميم المقترح من الوصول إلى الذاكرة خارج الرقاقة بنسبة 2.9× إلى 4.2× مقارنة بأفضل تصميم سابق (FAME) تحت نفس إعدادات المعلمات. وبالتوازي مع طريقة الأقطار، تصل التحسينات في تقليل الوصول إلى الذا "خارج الرقاقة" إلى 10.6×.
زمن انتقال الحساب (Computational Latency): يحقق المسرع المقترح انخفاضاً في زمن انتقال الحساب بنسبة 2.9× إلى 10.6× مقارنة بمسرعات الأجهزة السابقة.
استغلال الموارد: يحافظ التصميم على متطلبات موارد الأجهزة (LUTs, FFs, DSPs, BRAMs) بمستويات مماثلة أو أفضل قليلاً من الحلول الحالية، رغم المكاسب الكبيرة في الأداء.
المقارنة الخوارزمية: بينما تقلل خوارزمية TH-BSGS من متطلبات الذاكرة لمفاتيح التبديل بنحو 3.65× مقارنة بخوارزمية DH-BSHS، فإن التعقيد الحسابي الإجمالي يظل مشابهاً لـ DH-BSGS و BSGS لأن عمليات ضرب كثيرات الحدود هي التي تهيمن على إجمالي التعقيد.

الأهمية
يزعم البحث أن خوارزمية TH-BSGS المقترحة ومسرع الأجهزة المرتبط بها يمثلان تقدماً كبيراً في كفاءة HE-LT. ومن خلال معالجة العبء الخوارزمي لتبديل المفاتيح واختناق الوصول إلى الذاكرة خارج الرقاقة في الأجهزة في آن واحد، يتيح التصميم تحويلات خطية أسرع وأكثر قابلية للتوسع في مجال الحفاظ على الخصوصية. إن تقليل حركة البيانات خارج الرقاقة أمر بالغ الأهمية، حيث تشكل عمليات نقل البيانات الجزء الأكبر من زمن الانتقال في عمليات HE-LT. ويظهر العمل أن المزيد من التفكيك لـ "خطوة الطفل"، جنباً إلى جنب مع تحسين مسار البيانات الصارم والأجهزة المتخصصة، يمكن أن يؤدي إلى تحسينات كبيرة في الأداء دون زيادة تكاليف موارد الأجهزة. وقد تمت الإشارة إلى أن العمل المستقبلي سيركز على تحسين التحويلات الخطية لتطبيقات محددة.

1. المشكلة: "الجهد الشاق" لنقل البيانات

2. الحل: نظام المصعد "ثلاثي الرفع"

3. الأجهزة: "خط تجميع" مخصص

4. تحسين الذاكرة: مطبخ "في الوقت المناسب"

الخلاصة

أبحاث مشابهة