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बहु-संदेश सुरक्षित एकत्रीकरण मांग गोपनीयता के साथ
बुनियादी जानकारी
- पेपर ID: 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
सारांश
यह पेपर मांग गोपनीयता के साथ बहु-संदेश सुरक्षित एकत्रीकरण समस्या का अध्ययन करता है, जहां सर्वर K वितरित उपयोगकर्ताओं से Kc≥1 रैखिक संयोजनों की गणना करना चाहता है। यह समस्या दो कार्यों को संबोधित करती है: (1) सुरक्षा, यह सुनिश्चित करना कि सर्वर केवल आवश्यक रैखिक संयोजन प्राप्त करे और उपयोगकर्ता इनपुट की कोई अन्य जानकारी न लीक हो; (2) गोपनीयता, उपयोगकर्ताओं को सर्वर के कम्प्यूटेशनल कार्यों के बारे में जानने से रोकना। इसके अतिरिक्त, उपयोगकर्ता ड्रॉपआउट के प्रभाव पर विचार किया जाता है, जहां अधिकतम K-U उपयोगकर्ता ड्रॉप आउट हो सकते हैं और उनकी पहचान पहले से अनुमानित नहीं की जा सकती। लेखकों ने Kc=1 और 2≤Kc<U दोनों मामलों के लिए दो अलग-अलग योजनाएं प्रस्तावित की हैं। Kc=1 के लिए, यादृच्छिक चर का उपयोग करके सर्वर की मांग को गुणात्मक रूप से एन्क्रिप्ट करने की विधि प्रस्तुत की गई है; 2≤Kc<U के लिए, दूसरे दौर में कुंजियों के रैखिक संयोजन को पुनः प्राप्त करने के लिए मजबूत सममित निजी गणना का उपयोग किया जाता है।
अनुसंधान पृष्ठभूमि और प्रेरणा
समस्या परिभाषा
संघीय शिक्षा वितरित उपयोगकर्ताओं को केंद्रीय सर्वर के समन्वय में वैश्विक मॉडल को सहयोगी रूप से प्रशिक्षित करने की अनुमति देती है, लेकिन मॉडल अपडेट अभी भी उपयोगकर्ता के स्थानीय डेटा की जानकारी लीक कर सकते हैं। सुरक्षा को और बढ़ाने के लिए, सुरक्षित एकत्रीकरण को सर्वर को केवल एकत्रित अपडेट प्राप्त करने के लिए पेश किया गया है, न कि उपयोगकर्ता डेटा की किसी अतिरिक्त जानकारी को।
अनुसंधान प्रेरणा
- बहु-कार्य शिक्षण की आवश्यकता: एकल-कार्य की तुलना में, बहु-कार्य शिक्षण कई परिणामों का लाभ उठाकर मॉडल प्रशिक्षण के समग्र प्रदर्शन को बढ़ा सकता है, जानकारी और संसाधनों को साझा करके शिक्षण दक्षता में सुधार करता है।
- मौजूदा विधियों की सीमाएं:
- मौजूदा सूचना-सैद्धांतिक सुरक्षित एकत्रीकरण समस्याएं मुख्य रूप से Kc=1 के मामले पर ध्यान केंद्रित करती हैं
- सर्वर के कम्प्यूटेशनल कार्यों की गोपनीयता सुरक्षा पर विचार की कमी
- उपयोगकर्ता ड्रॉपआउट की स्थिति में सुरक्षा और गोपनीयता सुनिश्चित करने की आवश्यकता
- व्यावहारिक अनुप्रयोग की आवश्यकता: वास्तविक संघीय शिक्षण परिदृश्यों में, सर्वर को कई अलग-अलग रैखिक संयोजनों की गणना करने की आवश्यकता हो सकती है, जबकि उपयोगकर्ताओं को सर्वर की विशिष्ट कम्प्यूटेशनल आवश्यकताओं के बारे में नहीं पता होना चाहिए।
मुख्य योगदान
- नई समस्या का औपचारिकीकरण: पहली बार मांग गोपनीयता के साथ बहु-संदेश सुरक्षित एकत्रीकरण समस्या प्रस्तावित की गई है, जो पारंपरिक सुरक्षित एकत्रीकरण अनुसंधान के दायरे को विस्तारित करती है।
- इष्टतम योजना (Kc=1): गुणात्मक एन्क्रिप्शन मांग और योजक एन्क्रिप्शन मॉडल को जोड़ने वाली सुरक्षित एकत्रीकरण योजना प्रस्तावित की गई है, जो इष्टतम संचार दर क्षेत्र प्राप्त करती है, जो गोपनीयता बाधा के बिना सुरक्षित एकत्रीकरण समस्या की क्षमता के बराबर है।
- अनुमानित इष्टतम योजना (2≤Kc<U): सममित निजी गणना योजना का उपयोग करते हुए, पहली योजना को Kc बार दोहराने की आधारभूत विधि में महत्वपूर्ण सुधार किया गया है, पहले दौर की दर इष्टतम है, दूसरे दौर की दर 2 के कारक के भीतर इष्टतम है।
- सैद्धांतिक विश्लेषण: समस्या के सैद्धांतिक आधार को स्थापित करते हुए, पूर्ण प्राप्यता प्रमाण और विपरीत सीमा विश्लेषण प्रदान किया गया है।
विधि विवरण
प्रणाली मॉडल
प्रतिभागी:
- 1 सर्वर और 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}$$ **संचार मॉडल**: - **पहला दौर**: सर्वर उपयोगकर्ता i को क्वेरी Q1,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 (कुंजी पीढ़ी)**: - प्रत्येक उपयोगकर्ता i के लिए Zi उत्पन्न करें, 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] के लिए, F^L_q से यादृच्छिक रूप से Zi चुनें - सभी उपयोगकर्ता साझा कुंजी साझा करते हैं: 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 के शास्त्रीय सूचना-सैद्धांतिक सुरक्षा परिणाम --- **समग्र मूल्यांकन**: यह सुरक्षित एकत्रीकरण और गोपनीयता-संरक्षित गणना के अंतर-विषयक क्षेत्र में एक उच्च-गुणवत्ता वाला सैद्धांतिक पेपर है जो महत्वपूर्ण योगदान करता है। हालांकि व्यावहारिकता के पहलू में सुधार की गुंजाइश है, लेकिन इसका सैद्धांतिक नवाचार और कठोर विश्लेषण बाद के अनुसंधान के लिए एक ठोस आधार प्रदान करता है।