2025-11-23T13:58:16.869352
Multi-Message Secure Aggregation with Demand Privacy
Sun, Zhang, Wan et al.
This paper considers a multi-message secure aggregation with privacy problem, in which a server aims to compute $\sf K_c\geq 1$ linear combinations of local inputs from $\sf K$ distributed users. The problem addresses two tasks: (1) security, ensuring that the server can only obtain the desired linear combinations without any else information about the users' inputs, and (2) privacy, preventing users from learning about the server's computation task. In addition, the effect of user dropouts is considered, where at most $\sf{K-U}$ users can drop out and the identity of these users cannot be predicted in advance. We propose two schemes for $\sf K_c$ is equal to (1) and $\sf 2\leq K_c\leq U-1$, respectively. For $\sf K_c$ is equal to (1), we introduce multiplicative encryption of the server's demand using a random variable, where users share coded keys offline and transmit masked models in the first round, followed by aggregated coded keys in the second round for task recovery. For $\sf{2\leq K_c \leq U-1}$, we use robust symmetric private computation to recover linear combinations of keys in the second round. The objective is to minimize the number of symbols sent by each user during the two rounds. Our proposed schemes have achieved the optimal rate region when $ \sf K_c $ is equal to (1) and the order optimal rate (within 2) when $\sf{2\leq K_c \leq U-1}$.
academicالتجميع الآمن متعدد الرسائل مع خصوصية الطلب
المعلومات الأساسية
- معرّف الورقة: 2504.20639
- العنوان: Multi-Message Secure Aggregation with Demand Privacy
- المؤلفون: Chenyi Sun, Ziting Zhang, Kai Wan (جامعة هوازونغ للعلوم والتكنولوجيا)، Giuseppe Caire (جامعة برلين التقنية)
- التصنيف: cs.IT math.IT
- تاريخ النشر: 13 أكتوبر 2025 (arXiv v2)
- رابط الورقة: https://arxiv.org/abs/2504.20639
الملخص
تدرس هذه الورقة مشكلة التجميع الآمن متعدد الرسائل مع خصوصية الطلب، حيث يهدف الخادم إلى حساب Kc≥1 من التركيبات الخطية للمدخلات المحلية من K مستخدم موزع. تعالج المشكلة مهمتين: (1) الأمان، مما يضمن أن الخادم يمكنه الحصول فقط على التركيبات الخطية المطلوبة دون الكشف عن أي معلومات أخرى عن مدخلات المستخدم؛ (2) الخصوصية، مما يمنع المستخدمين من معرفة مهام الحساب للخادم. بالإضافة إلى ذلك، يتم النظر في تأثير انقطاع الاتصال بالمستخدمين، حيث قد ينقطع اتصال ما يصل إلى K-U مستخدمين ولا يمكن التنبؤ بهويتهم مسبقاً. يقترح المؤلفون مخططين منفصلين للحالتين Kc=1 و 2≤Kc<U. بالنسبة لـ Kc=1، يتم تقديم طريقة استخدام متغيرات عشوائية لتشفير طلبات الخادم بشكل ضربي؛ بالنسبة لـ 2≤Kc<U، يتم استخدام الحساب الخاص المتماثل القوي لاستعادة التركيبات الخطية للمفاتيح في الجولة الثانية.
الخلفية البحثية والدافع
تعريف المشكلة
يسمح التعلم الفيدرالي للمستخدمين الموزعين بالتعاون في تدريب نموذج عام تحت تنسيق خادم مركزي، لكن تحديثات النموذج قد تكشف معلومات عن بيانات المستخدم المحلية. لتعزيز الأمان بشكل أكبر، تم إدخال التجميع الآمن لضمان أن الخادم يمكنه الحصول فقط على التحديثات المجمعة دون الحصول على أي معلومات إضافية عن بيانات المستخدم.
دافع البحث
- احتياجات التعلم متعدد المهام: بالمقارنة مع التعلم أحادي المهمة، يمكن للتعلم متعدد المهام الاستفادة من نتائج متعددة لتحسين الأداء الكلية لتدريب النموذج، من خلال مشاركة المعلومات والموارد لتحسين كفاءة التعلم.
- قيود الطرق الموجودة:
- تركز مشاكل التجميع الآمن ذات الأساس النظري المعلوماتي بشكل أساسي على حالة Kc=1
- تفتقر إلى الحماية من الكشف عن مهام الحساب للخادم
- تحتاج إلى ضمان الأمان والخصوصية في حالة انقطاع الاتصال بالمستخدمين
- متطلبات التطبيق العملي: في سيناريوهات التعلم الفيدرالي الفعلية، قد يحتاج الخادم إلى حساب عدة تركيبات خطية مختلفة، وفي الوقت نفسه، لا يجب أن يعرف المستخدمون احتياجات الحساب المحددة للخادم.
المساهمات الأساسية
- صياغة مشكلة جديدة: تقديم مشكلة التجميع الآمن متعدد الرسائل مع خصوصية الطلب للمرة الأولى، مما يوسع نطاق البحث في التجميع الآمن التقليدي.
- مخطط أمثل (Kc=1): اقتراح مخطط تجميع آمن يجمع بين التشفير الضربي للطلب والتشفير الإضافي للنموذج، مما يحقق منطقة معدل الاتصال الأمثل، والتي تساوي سعة مشكلة التجميع الآمن بدون قيود الخصوصية.
- مخطط قريب من الأمثل (2≤Kc<U): استخدام مخطط الحساب الخاص المتماثل، مما يحسن بشكل كبير من طريقة الأساس المتمثلة في تكرار المخطط الأول Kc مرات، مع معدل الجولة الأولى الأمثل ومعدل الجولة الثانية الأمثل ضمن عامل 2.
- التحليل النظري: توفير إثبات الوصول الكامل وتحليل الحدود العكسية، مما يؤسس الأساس النظري للمشكلة.
شرح الطريقة
نموذج النظام
المشاركون:
- خادم واحد و K مستخدمين غير متواطئين (K≥2)
- يحتفظ المستخدم i بمتجه الإدخال Wi والمفتاح Pi
- يحتوي Wi على L رموز موزعة بشكل مستقل وموحد، معرّفة على الحقل المحدود Fq
دالة الهدف: يحسب الخادم الخريطة الخطية:
حيث F هي مصفوفة المعاملات بحجم Kc×K:
a_{1,1} & \cdots & a_{1,K} \\ \vdots & \ddots & \vdots \\ a_{K_c,1} & \cdots & a_{K_c,K} \end{pmatrix}$$ **نموذج الاتصال**: - **الجولة الأولى**: يرسل الخادم الاستعلام Q1,i للمستخدم i، ويرد المستخدم i بالرسالة Xi - **الجولة الثانية**: يخبر الخادم مجموعة المستخدمين الموجودين U1، ويرسل الاستعلام Q^{U1}_{2,i}، ويرسل المستخدم i الرسالة Y^{U1}_i ### القيود 1. **قابلية فك التشفير**: يمكن للخادم حساب التركيبات الخطية المطلوبة بدون أخطاء 2. **الأمان**: لا يمكن للخادم الحصول على معلومات تتجاوز نتيجة الحساب المستهدفة من مدخلات المستخدم 3. **الخصوصية**: لا يمكن للمستخدمين استنتاج مصفوفة الطلب F للخادم ### مخطط حالة Kc=1 #### الفكرة الأساسية الجمع بين التشفير الضربي للطلب والتشفير الإضافي للنموذج، من خلال متغير عشوائي t لتشفير طلبات الخادم. #### الخطوات التفصيلية **المرحلة 1 (توليد الاستعلام)**: - يختار الخادم عشوائياً t ∈ Fq\{0} - تعريف الاستعلام: $Q_{1,i} = \frac{1}{ta_{1,i}}$، i ∈ [K] **المرحلة 2 (توليد المفتاح)**: - توليد Zi لكل مستخدم i، موزع بشكل موحد على F^L_q - تقسيم Zi إلى U مفاتيح فرعية: [Zi]m ∈ F^{L/U}_q - استخدام مصفوفة MDS M للترميز: $[\tilde{Z}_i]_j = ([Z_i]_1, \ldots, [Z_i]_U) \cdot M_{:,j}$ **المرحلة 3 (نقل الجولة الأولى)**: - يرسل المستخدم i: $X_i = W_i + Q_{1,i}Z_i$ **المرحلة 4 (نقل الجولة الثانية)**: - يرسل المستخدم j ∈ U1 المفاتيح الفرعية المرمزة المجمعة: $\sum_{i \in U_1}[\tilde{Z}_i]_j$ - يستعيد الخادم من خلال فك ترميز MDS $\sum_{i \in U_1} Z_i$ #### عملية فك التشفير يحسب الخادم: $$\sum_{i \in U_1} \frac{1}{Q_{1,i}}X_i = \sum_{i \in U_1} \frac{1}{Q_{1,i}}W_i + \sum_{i \in U_1} Z_i$$ بما أن $t \sum_{i \in U_1} a_{1,i}W_i = \sum_{i \in U_1} \frac{1}{Q_{1,i}}W_i$، يمكن للخادم فك تشفير التركيبة الخطية المستهدفة. ### مخطط حالة 2≤Kc<U #### الفكرة الأساسية استخدام الحساب الخاص المتماثل القوي لضمان الأمان والخصوصية في نقل الجولة الثانية. #### الخطوات التفصيلية **المرحلة 1 (توليد المفتاح)**: - لكل i ∈ [K]، اختيار عشوائي Zi من F^L_q - مشاركة المفتاح بين جميع المستخدمين: Pi = (Zi)i∈[K] - مشاركة L/(U-1) متغيرات عشوائية عامة كأقنعة مفتاح **المرحلة 2 (نقل الجولة الأولى)**: - يرسل المستخدم i: $X_i = W_i + Z_i$ **المرحلة 3 (نقل الجولة الثانية)**: - يحتاج الخادم إلى استعادة Kc من تركيبات المفاتيح: $\sum_{i \in U_1} a_{n,i}Z_i$، n ∈ [Kc] - تقسيم كل مفتاح Zi إلى مفاتيح فرعية بطول L' = U-1 - استخدام مخطط الحساب الخاص المتماثل Kc مرات، للحصول على كل تركيبة خطية على حدة - بناء استعلامات متعددة الحدود باستخدام ترميز لاغرانج لحماية خصوصية المهام الحسابية ## النتائج النظرية ### النتائج الرئيسية **النظرية 3 (الأمثلية عند Kc=1)**: بالنسبة لمشكلة التجميع الآمن متعدد الرسائل (K,U,Kc)، عندما U≤K-1 و Kc=1، تكون منطقة السعة: $$\mathcal{R}^* = \{(R_1,R_2) : R_1 \geq 1, R_2 \geq \frac{1}{U}\}$$ **النظرية 5 (قابلية الوصول عند 2≤Kc<U)**: عندما 2≤Kc<U≤K-1، فإن مجموعة المعدل $(R_1 = 1, R_2 = \frac{K_c}{U-1})$ قابلة للوصول. **النظرية 6 (الحدود العكسية)**: يجب أن يحقق أي معدل قابل للوصول: $R_1 \geq 1, R_2 \geq \frac{K_c}{U}$ ### تحليل الأداء 1. **الأمثلية**: تحقق حالة Kc=1 الأمثلية النظرية 2. **القرب من الأمثلية**: في حالة 2≤Kc<U، معدل الجولة الأولى أمثل، ومعدل الجولة الثانية أمثل ضمن عامل 2: $$\frac{K_c/(U-1)}{K_c/U} = \frac{U}{U-1} \leq 2$$ 3. **المقارنة مع الطريقة الأساسية**: بالمقارنة مع طريقة التكرار المباشر، يقلل المخطط الجديد معدل الجولة الأولى من Kc إلى 1، ويزيد معدل الجولة الثانية من Kc/U إلى Kc/(U-1) ## الأعمال ذات الصلة ### التجميع الآمن - **التجميع الآمن ذو الأساس النظري المعلوماتي**: قدم Zhao و Sun الصياغة الرسمية الأولى، وحققوا منطقة السعة {(R1,R2) : R1≥1, R2≥1/U} - **التجميع الآمن العملي**: يقلل LightSecAgg بشكل كبير من عدد المفاتيح المطلوبة من خلال فصل عملية توليد المفاتيح ### استرجاع المعلومات الخاص والحساب الخاص - **استرجاع المعلومات الخاص (PIR)**: يسمح للخادم باسترجاع الرسائل من قاعدة بيانات موزعة بشكل خاص - **الحساب الخاص (PC)**: يوسع إطار عمل PIR ليشمل الحسابات الخطية للرسائل - **الحساب الخاص المتماثل**: يحمي في نفس الوقت خصوصية مهام الحساب للخادم وأمان بيانات المستخدم ### التعلم متعدد المهام - **التعلم المنسق**: تتعاون مهام متعددة من خلال مشاركة المعلومات والموارد، مما يحسن كفاءة التعلم الكلية - **التمثيل المشترك**: تستفيد المهام من التمثيلات المشتركة والتدرجات أو المكونات المشتركة ## الخلاصة والمناقشة ### الاستنتاجات الرئيسية 1. صياغة مشكلة التجميع الآمن متعدد الرسائل مع خصوصية الطلب للمرة الأولى 2. تحقيق منطقة معدل الاتصال الأمثل لـ Kc=1 3. تحقيق أداء الجولة الأولى الأمثل والجولة الثانية القريبة من الأمثل لـ 2≤Kc<U 4. توفير إطار عمل تحليل نظري كامل ### القيود 1. **المنطقة المفتوحة**: لا تزال مشكلة وصف منطقة السعة عند Kc≥U غير محلولة 2. **حجم المفتاح**: لم يتم تحسين تقليل حجم المفتاح المطلوب 3. **العملية**: يتمتع المخطط النظري بتعقيد تنفيذ عالي في الأنظمة الفعلية 4. **قابلية التوسع**: قابلية التوسع محدودة للمهام الحسابية غير الخطية ### الاتجاهات المستقبلية 1. **وصف منطقة السعة الكاملة**: حل مشكلة الحالة Kc≥U 2. **تحسين المفتاح**: تقليل حجم المفتاح المطلوب لتحسين العملية 3. **التنفيذ النظامي**: تطوير نماذج أولية للنظام قابلة للنشر الفعلي 4. **التوسع غير الخطي**: التوسع إلى المهام الحسابية غير الخطية ## التقييم المتعمق ### المزايا 1. **مساهمة نظرية كبيرة**: دمج رائد للتجميع الآمن وخصوصية الطلب، ملء فراغ نظري مهم 2. **قوة الابتكار في الطريقة**: دمج ذكي للتشفير الضربي والحساب الخاص المتماثل، مسار تقني جديد 3. **تحليل نظري كامل**: توفير إثبات قابلية الوصول الصارمة وتحليل الحدود العكسية 4. **أهمية عملية كبيرة**: حل مشكلة حماية الخصوصية المهمة في التعلم الفيدرالي ### أوجه القصور 1. **نطاق التطبيق محدود**: يقتصر على المهام الحسابية الخطية، قد تتطلب التطبيقات الفعلية عمليات غير خطية 2. **تعقيد التنفيذ عالي**: خاصة في حالة 2≤Kc<U، يكون تنفيذ الحساب الخاص المتماثل معقداً نسبياً 3. **قيود المعاملات**: قد تكون قيود Kc<U صارمة جداً في بعض سيناريوهات التطبيق 4. **غياب التحقق التجريبي**: نقص التنفيذ الفعلي للنظام واختبارات الأداء ### القيمة التأثيرية 1. **القيمة الأكاديمية**: توفير إطار عمل نظري جديد لمجالات الحساب الآمن متعدد الأطراف والتعلم الفيدرالي 2. **الإمكانية العملية**: توفير أساس نظري للتعلم الآلي الموزع المحمي بالخصوصية 3. **قابلية إعادة الإنتاج**: النتائج النظرية واضحة، لكن التنفيذ الفعلي يتطلب عملاً هندسياً كبيراً ### السيناريوهات المطبقة 1. **التعلم الفيدرالي**: التجميع الآمن المحمي بالخصوصية في التعلم الفيدرالي متعدد المهام 2. **الإحصائيات الموزعة**: الأنظمة الموزعة التي تحتاج إلى حساب إحصائيات متعددة 3. **تحليل البيانات المحمية بالخصوصية**: سيناريوهات تحليل البيانات في المجالات المالية والطبية وغيرها التي تتطلب خصوصية صارمة ## المراجع تستشهد الورقة بمراجع مهمة متعددة، بما في ذلك: - أعمال Zhao و Sun في التجميع الآمن ذي الأساس النظري المعلوماتي - نتائج سعة استرجاع المعلومات الخاص والحساب الخاص لـ Sun و Jafar - مخطط الحساب الخاص المتماثل متعدد الحدود لـ Zhu وآخرين - نتائج الأمان المعلوماتي الكلاسيكية لـ Shannon --- **التقييم الإجمالي**: هذه ورقة عالية الجودة في المجال النظري، وقد قدمت مساهمات مهمة في مجال التقاطع بين التجميع الآمن وحماية الخصوصية في الحساب. على الرغم من وجود مجال للتحسين من حيث العملية، فإن ابتكارها النظري وتحليلها الصارم يوفران أساساً متيناً للأبحاث اللاحقة.