💻 computer science

Multi-Input Ciphertext Multiplication for Homomorphic Encryption

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

المؤلفون الأصليون: 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 - HE). فهو يسمح للحواسيب بإجراء عمليات حسابية على "البيانات المشفرة" (عجينة الكعكة داخل القفازات) دون الحاجة أبدًا لفك تشفيرها (خلع القفازات). هذا يحافظ على سرية بياناتك، سواء كانت سجلاتك الطبية أو رصيدك البنكي.

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

تقدم هذه الورقة البحثية طريقة جديدة فائقة الكفاءة لضرب هذه المكونات المشفرة، وتحديدًا لنوع شائع من التشفير يسمى CKKS. إليك تفصيل هذا الإنجاز باستخدام تشبيهات بسيطة:

1. المشكلة: "المطبخ الفوضوي"

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

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

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

2. الحل: "خط التجميع الذكي"

يقترح المؤلفون ترقيتين رئيسيتين لجعل هذه العملية أسرع وأصغر حجمًا:

أ. "التنظيف في خطوة واحدة" (تحسين ضرب الثلاث مدخلات)

في تصميمهم الجديد لضرب ثلاثة مكونات، أدرك المؤلفون أنهم كانوا يقومون بعملية التنظيف (إعادة القياس) وإعادة الترتيب (Relinearization) بطريقة مربكة وغير مباشرة.

التشبيه: تخيل أن لديك ثلاثة أوعية من العجين. الطريقة القديمة كانت تتمثل في خلطهم، ثم سكب الخليط في وعاء جديد، ثم تنظيف الأوعية القديمة، ثم سكب الخليط مرة أخرى، ثم التنظيف مجددًا.
الإصلاح: أعادوا تصميم العملية بحيث يمكنك الخلط والتنظيف في حركة واحدة سلسة. لقد عرفوا كيفية دمج خطوات التنظيف حتى لا تضطر للتوقف لمسح الطاولة عدة مرات.
النتيجة: "خلاط الثلاث أوعية" الجديد الخاص بهم أسرع بنسبة 50% (من حيث زمن الاستجابة/Latency) ويشغل مساحة أقل بنسبة 15% على الشريحة (المساحة/Area) مقارنة بأفضل تصميم سابق لهم.

ب. "التنظيف الجماعي" (ضرب المدخلات المتعددة)

ماذا لو كنت بحاجة لضرب أربعة، أو خمسة، أو حتى اثني عشر مكونًا في وقت واحد؟

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

3. لماذا يهم هذا (وفقًا للورقة البحثية)

تركز الورقة البحثية حصريًا على بنية العتاد (Hardware Architecture) — التصميم الفيزيائي لشريحة الكمبيوتر التي تقوم بهذه العمليات الحسابية.

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

ملخص

فكر في هذه الورقة البحثية كأنها ابتكار لمطبخ جديد فائق الكفاءة لطاهٍ لا يستطيع خلع قفازات الفرن.

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

لم يختبر المؤلفون هذا على مرضى حقيقيين أو حسابات بنكية حقيقية في هذه الورقة؛ لقد أثبتوا فقط أن الآلة المصممة للقيام بهذا العمل أفضل بكثير من الآلات التي كانت لدينا من قبل.

ملخص تقني: ضرب التشفير متعدد المدخلات في التشفير المتماثل

بيان المشكلة
يتيح التشفير المتماثل (HE)، ولا سيما مخطط RNS-CKKS، العمليات الحسابية على البيانات المشفرة، وهو أمر بالغ الأهمية للتطبيقات التي تحافظ على الخصوصية مثل تعلم الآلة والتشخيص الطبي. ومع ذلك، فإن مخططات التشفير المتماثل القياسية تُعرف ضرب التشفير لمدخلين فقط. تتطلب العديد من التطبيقات العملية، مثل التقريبات متعددة الحدود عالية الرتبة لدوال التنشيط في الشبكات العصبية (مثل ReLU)، وأشجار القرار، وتسلسل الجينوم، ضرب عدة تشفيرات ( $n > 2$ ).

تعتمد النهج الحالية للتعامل مع ضرب متعدد المدخلات عادةً على ربط عدة وحدات ضرب ثنائية المدخلات في هيكل شجرة ثنائية. تعاني هذه الطريقة من عدم كفاءة أساسي في جانبين:

الكمون والمساحة العالية: يؤدي ضرب $n$ من التشفيرات بالتتابع باستخدام وحدات ذات مدخلين إلى عبء إضافي كبير على الأجهزة وزيادة في زمن التأخير (Latency).
نمو الضجيج وعبء إعادة القياس (Rescaling): تزيد كل عملية ضرب من مستوى الضجيج، مما يستلزم عملية إعادة قياس لاستعادة مقياس الرسالة. في الشجرة الثنائية القياسية، يجب إجراء إعادة القياس بعد كل خطوة ضرب لمنع النمو الأسي للضجيج. ينتج عن ذلك عدد كبير من وحدات إعادة القياس، والتي تتطلب كل منها عمليات تحويل "عدد نظري" (NTT) وتحويل "عدد نظري عكسي" (INTT) مكلفة، مما يزيد بشكل كبير من التعقيد الحسابي واستخدام موارد الأجهزة.

المنهجية
يقترح البحث إطار عمل لضرب التشفير المباشر متعدد المدخلات ( $n$ -input) الذي يقلل من عمق الضرب ومن تعقيد الأجهزة. تنقسم المنهجية إلى مساهمتين رئيسيتين:

محسن ضرب ثلاثة مدخلات:
قام المؤلفون أولاً بإعادة صياغة عملية ضرب الثلاث مدخلات. في العمل التمهيدي [26]، كانت عمليات إعادة الخطية (relinearization) وإعادة القياس (rescaling) تُنفذ بشكل منفصل، مما يتطلب عمليات ModUp/ModDown متعددة وكتل (I)NTT عديدة. التصميم الجديد:

إعادة صياغة إعادة الخطية: من خلال نقل عامل القياس $P^{-1}$ إلى تحويل الأساس (BConv) وضرب مفتاح التقييم، يلغي التصميم خطوات القياس المنفصلة.
تحسين إعادة القياس: أعاد المؤلفون هيكلة مسار البيانات لإجراء إعادة القياس في المجال الأصلي قبل عملية الـ NTT النهائية، بدلاً من إجرائها في مجال الـ NTT. وهذا يسمح بإلغاء عمليات (I)NTT الزائدة.
النتيجة: قللت هذه التغييرات من عدد كتل (I)NTT في مسار البيانات من ثمانية إلى أربعة، مما أدى فعلياً إلى تقليص طول مسار البيانات إلى النصف.

التوسيع متعدد المدخلات مع إعادة القياس المدمجة:
لتوسيع عملية الضرب لتشمل $n > 3$ من المدخلات دون زيادة عمق الضرب، قدم البحث ما يلي:

مفاتيح التقييم المعممة: تم تقديم مفاتيح تقييم جديدة ( $ek_t$ ) لإعادة خطية حدود الدرجة الأعلى ( $d_t s^t$ ) الناتجة عن ضرب $n$ من التشفيرات، مما يقلل النتيجة مرة أخرى إلى تنسيق مكون من مضلعين.
خوارزمية إعادة القياس المتعدد (Multi-RS): حدد تحليل نظري الشروط التي يمكن بموجبها تأخير ودمج عمليات إعادة قياس متعددة. اقترح المؤلفون خوارزمية تقوم بإجراء $\mu$ من عمليات إعادة القياس المتتالية باستخدام نفس عدد عمليات (I)NTT لعملية إعادة قياس واحدة. ويتم تحقيق ذلك عن طريق تحويل المدخل إلى مجال الـ INTT، وإجراء إعادة القياس المتكررة في مجال المعاملات (coefficient domain)، ثم التحويل مرة أخرى، باستخدام ثوابت محسوبة مسبقاً لدمج العمليات.
إرشادات تقسيم المدخلات: يقدم البحث إرشادات لتقسيم $n$ من المدخلات إلى مجموعات (على سبيل المثال، $(n_1, n_2, \dots, n_m)$ ) لتعظيم عدد عمليات إعادة القياس المدمجة مع الحفاظ على العمق الأمثل للضرب $\lceil \log_2 n \rceil$ . يتضمن ذلك إنشاء هياكل أشجار غير متوازنة حيثما أمكن لتجميع المزيد من المدخلات قبل خطوة إعادة القياس.

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

إعادة الصياغة الخوارزمية: صياغة جديدة لضرب الثلاث مدخلات تدمج الحسابات الوسيطة، مما يقلل من عمليات (I)NTT ويقصر مسار البيانات.
إطار العمل متعدد المدخلات: توسيع ضرب التشفير ليشمل أي عدد $n$ من المدخلات باستخدام مفاتيح تقييم معممة وضرب هيكلي (tree-structured multiplier).
إعادة القياس المدمجة: خوارزمية إعادة قياس متعددة مبتكرة تقلل من تعقيد إجراء عمليات إعادة قياس متعددة لتصبح مساوية لتعقيد عملية إعادة قياس واحدة، بغض النظر عن عدد الخطوات المدمجة ( $\mu$ ).
بنية الأجهزة: تصميم بنيات أجهزة كاملة التدفق (fully-pipelined) للمضاعفات المقترحة، بما في ذلك وحدات ModUp وModDown وإعادة القياس المحسنة.

النتائج
تم تصنيع التصاميم المقترحة باستخدام عملية GlobalFoundries 22FDX مع المعلمات $N=2^{16}$ ، $L=K=24$ ، و $w=64$ .

مضاعف الثلاث مدخلات: مقارنة بالعمل السابق [26]، يحقق مضاعف الثلاث مدخلات المحسن انخفاضاً بنسبة 15% في مساحة المنطق وانخفاضاً بنسبة 50% في زمن التأخير. كما يقلل متطلبات الذاكرة بنسبة تقارب 20% بسبب قلة وحدات (I)NTT.
المضاعفات متعددة المدخلات ( $n=4$ إلى $12$): مقارنة بالتنفيذ المرجعي الذي يستخدم شجرة ثنائية من مضاعفات ثنائية المدخلات، يحقق الأسلوب المقترح متوسط انخفاض بنسبة 32% في المساحة الإجمالية وانخفاض بنسبة 45% في زمن التأخير.
كفاءة إعادة القياس: بالنسبة للمدخلات غير القائمة على قوى العدد 2 (مثل $n=17$ )، يقلل التقسيم المحسن مع إعادة القياس المتعدد من إجمالي عدد وحدات إعادة القياس (وعمليات (I)NTT المرتبطة بها) بنسبة تقارب 47% مقارنة بنهج الشجرة الثنائية القياسي.

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