💻 computer science

Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts

यह शोध पत्र बिट-रिवर्स्ड होमोमॉर्फिक एन्क्रिप्शन लेआउट्स के लिए एक रोटेशन-ऑप्टिमल प्रिफिक्स स्कैन एल्गोरिदम प्रस्तुत करता है जो एक रेप्लिकेटेड-अग्रेगेट इनवेरिएंट का लाभ उठाकर रोटेशन जटिलता को $O(m^2)$ से घटाकर $O(m)$ कर देता है, जिससे कंप्यूटेशनल लेटेंसी, मेमोरी उपयोग और इवैल्यूएशन-की स्टोरेज में उल्लेखनीय कमी आती है और गहरे डाउनस्ट्रीम पाइपलाइन्स को सक्षम बनाया जाता है।

मूल लेखक: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

प्रकाशित 2026-07-07

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आपके पास एक विशाल, एन्क्रिप्टेड स्प्रेडशीट है जहाँ प्रत्येक सेल में एक गुप्त संख्या है। आप इन सभी संख्याओं पर एक साथ एक विशिष्ट गणितीय ट्रिक करना चाहते हैं: प्रत्येक सेल के लिए, आपको उन सभी संख्याओं का "रनिंग टोटल" (running total) जानना है जो उससे पहले आई थीं। होमोमॉर्फिक एन्क्रिप्शन (Homomorphic Encryption) की दुनिया में—जहाँ डेटा को बिना डिक्रिप्ट किए उस पर गणना की जाती है—इसे "प्रिफिक्स स्कैन" (prefix scan) कहा जाता है।

समस्या यह है कि डेटा एक सीधी पंक्ति में 1, 2, 3, 4 की तरह संग्रहीत नहीं है। क्योंकि इस तरह से काम करने वाला एन्क्रिप्शन काम करता है, डेटा एक विशिष्ट पैटर्न में बिखरा हुआ है जिसे "बिट-रिवर्सड ऑर्डर" (bit-reversed order) कहा जाता है। यह एक ऐसी किताब की तरह है जिसके पन्ने इधर-उधर बिखरे हुए हैं: पन्ना 1 के बाद पन्ना 8 आता है, फिर पन्ना 4, फिर पन्ना 12, और इसी तरह।

पुराना तरीका: "सटीक पड़ोसी" की समस्या

रनिंग टोटल की गणना करने के लिए, आपको आमतौर पर अपने पड़ोसी से उनकी संख्या पूछनी पड़ती है। एक सामान्य पंक्ति में, आपका पड़ोसी बस एक कदम दूर होता है। लेकिन इस बिखरे हुए "बिट-रिवर्सड" बुक में, आपका तार्किक पड़ोसी कमरे के दूसरी ओर भी बैठा हो सकता है।

पुराने तरीके ने एक संदेशवाहक (एक "रोटेशन") भेजकर उस सटीक पड़ोसी को लाने की कोशिश की जिसकी आपको आवश्यकता थी।

उपमा: कल्पना कीजिए कि आप 8 शेल्फ वाली एक लाइब्रेरी में हैं। आपको अपने बाईं ओर वाले शेल्फ पर बैठे व्यक्ति से बात करनी है। लेकिन क्योंकि शेल्फ बिखरे हुए हैं, "बाएं" का अर्थ अलग-अलग लोगों के लिए अलग-अलग भौतिक दूरी हो सकती है।
लागत: सबको उनका सही पड़ोसी दिलाने के लिए, लाइब्रेरियन को बहुत से अलग-अलग रास्तों पर संदेशवाहक भेजने पड़े। 8 पन्नों की एक छोटी किताब के लिए, इसे 6 संदेशवाहकों की आवश्यकता थी। बड़ी किताब के लिए, यह संख्या विस्फोट की तरह बढ़ गई (यह एक त्रिकोण की तरह बढ़ी: 1+2+3+4...)। यह धीमा, महंगा था और उन सभी अलग-अलग जगहों पर संदेश भेजने के लिए बहुत सारे "कीज़" (अनुमति पर्चियों) की आवश्यकता थी।

नया तरीका: "कॉपीकैट" रणनीति

इस शोध पत्र के लेखकों को एहसास हुआ कि वे बहुत ज्यादा बारीकियाँ देख रहे थे। उन्हें सटीक पड़ोसी की आवश्यकता नहीं थी; उन्हें बस अपने पड़ोसी के समूह में से किसी भी व्यक्ति की आवश्यकता थी जिसके पास वही जानकारी हो।

उपमा: अपने बाईं ओर वाले विशिष्ट व्यक्ति को पूछने के बजाय, कल्पना करें कि एक "ग्रुप" (शेल्फों का एक ब्लॉक) में हर व्यक्ति उस ग्रुप के कुल स्कोर की एक समान प्रति (copy) पकड़े हुए है।
जादुई चाल: लेखकों ने पाया कि वे गणना के प्रत्येक स्तर (level) के लिए पूरी लाइब्रेरी को केवल एक बार रोटेट कर सकते हैं। यह एकल रोटेशन सभी को ऐसी जगह ले जाता है जहाँ वे बगल वाले समूह के किसी व्यक्ति के पास खड़े होते हैं। चूंकि उस समूह में हर कोई उसी "ग्रुप टोटल" की प्रति पकड़े हुए है, इसलिए इससे कोई फर्क नहीं पड़ता कि आपको कौन सा विशिष्ट व्यक्ति मिलता है; गणित पूरी तरह से काम करता है।
परिणाम: 8 पन्नों के लिए 6 संदेशवाहकों के बजाय, आपको केवल प्रति स्तर 1 संदेशवाहक की आवश्यकता होती है। पूरी किताब के लिए, आप संदेशवाहकों की त्रिकोणीय संख्या (जैसे 28) से घटकर केवल स्तरों की संख्या (जैसे 7) तक पहुँच जाते हैं।

उन्होंने वास्तव में क्या सिद्ध किया

यह पेपर केवल यह नहीं कहता कि "यह तेज़ है।" उन्होंने तीन कठिन गणितीय तथ्य सिद्ध किए:

आप इससे बेहतर नहीं कर सकते: उन्होंने सिद्ध किया कि आप कितने भी चतुर क्यों न हों, आपको गणना के स्तरों के बराबर कम से कम रोटेशन का उपयोग करना ही होगा। आप संदेशवाहकों को पूरी तरह से छोड़ नहीं सकते।
"परफेक्ट" मार्ग: उन्होंने दिखाया कि यदि आप न्यूनतम संदेशवाहकों का उपयोग करते हैं, तो उन्हें एक बहुत ही विशिष्ट, कठोर पैटर्न (2 की घातों से संबंधित) का पालन करना चाहिए। इसमें कोई गुंजाइश नहीं है; गणित इस विशिष्ट पथ को अनिवार्य बनाता है।
समझौता (Trade-off): संदेशवाहकों को बचाने के लिए, आपको स्थानीय रूप से थोड़ा अधिक गणितीय कार्य करना होगा (एक के बजाय दो सेट संख्याएं रखना)। लेकिन उनके परीक्षणों में, संदेशवाहकों को बचाने का लाभ काफी अधिक था।

वास्तविक दुनिया का परीक्षण (द "कैरी" समस्या)

उन्होंने इसका परीक्षण एक बहुत ही सामान्य गणितीय समस्या पर किया: संख्याओं को आगे ले जाना (Carrying numbers) (जैसे जब आप 9 + 3 करते हैं और 12 प्राप्त करते हैं, तो आपको 1 को अगले कॉलम में ले जाना होता है)।

सेटअप: उन्होंने अंकों की एक सूची को एन्क्रिप्ट किया और क्रम को अनस्क्रैम्बल किए बिना "कैरी" को ठीक करने की कोशिश की।
परिणाम:
- गति: मध्यम आकार की समस्याओं के लिए उनका नया तरीका पुराने "सटीक पड़ोसी" वाले तरीके की तुलना में लगभग 20% तेज़ था।
- मेमोरी: इसने 64% कम मेमोरी का उपयोग किया क्योंकि उन्हें उतनी अधिक अनुमति कुंजियों (permission keys) को स्टोर करने की आवश्यकता नहीं थी।
- बड़ी जीत: एक लंबी गणना श्रृंखला में, उनके तरीके ने इतनी "एन्क्रिप्शन शक्ति" बचा ली कि एक बहुत ही धीमी प्रक्रिया (जिसे "बूटस्ट्रैपिंग" कहा जाता है) को टाल दिया गया। इसने पूरी प्रक्रिया को अंत-से-अंत तक 4.3 गुना तेज़ बना दिया।

सारांश

इसे एक रिले रेस की तरह समझें।

पुराना तरीका: प्रत्येक धावक को अपने विशिष्ट साथी को खोजने के लिए एक अद्वितीय, लंबे और घुमावदार रास्ते पर दौड़ना पड़ता था। इसमें बहुत ऊर्जा और समय लगता था।
नया तरीका: टीम ने महसूस किया कि यदि वे केवल एक छोटा, मानकीकृत लूप दौड़ते हैं, तो हर कोई एक साथी के पास पहुँच जाएगा जिसके पास वही बैटन (baton) है। इसमें कम कदम लगे, कम ऊर्जा लगी, और काम जल्दी हो गया, भले ही धावकों को रास्ते में कुछ अतिरिक्त बैटन पकड़ने पड़े।

यह पेपर सिद्ध करता है कि इस प्रकार के बिखरे हुए, एन्क्रिप्टेड डेटा पर इस विशिष्ट प्रकार की गणित करने का यह सबसे तेज़ संभव तरीका है।

तकनीकी सारांश: बिट-रिवर्स्ड होमोमोर्फिक लेआउट में रोटेशन-ऑप्टिमल नॉनकम्यूटेटिव प्रीफिक्स स्कैन्स

समस्या विवरण

पैक्ड होमोमोर्फिक एन्क्रिप्शन (HE), विशेष रूप से CKKS स्कीम में, SIMD ऑपरेशन्स $n = 2^m$ तत्वों के एक एसोसिएटिव (associative), संभवतः नॉनकम्यूटेटिव (noncommutative) मोनोइड पर क्रमबद्ध प्रीफिक्स गणनाओं (scans) को करने की अनुमति देते हैं। हालाँकि, संचार के लिए साइक्लिक रोटेशन्स (गालुआ ऑटोमोर्फिज्म) की आवश्यकता होती है, जो की-स्विचिंग के कारण अत्यधिक लागत वाले कार्य हैं। रोटेशन की लागत डेटा के भौतिक लेआउट पर निर्भर करती है।

यह शोध पत्र एक बिट-रिवर्स्ड ऑर्डर (bit-reversed order) में संग्रहीत डेटा पर क्रमबद्ध प्रीफिक्स गणनाओं (scans) की समस्या को संबोधित करता है। यह लेआउट फास्ट ट्रांसफॉर्म्स और पैकिंग कन्वर्जन्स में सामान्य है।

मुख्य चुनौती यह है कि एक मानक "ट्रांसपोर्टेड-प्रीसेडेसर" (transported-predecessor) स्कैन, जो लॉजिकल प्रीसेडेसर्स से दूरी को पुनरावर्ती रूप से दोगुना करता है, बिट-रिवर्स्ड लेआउट में उच्च रूटिंग लागत उत्पन्न करता है। क्योंकि बिट रिवर्सल लॉजिकल इंडेक्स को बदल देता है, एक एकल लॉजिकल शिफ्ट $2^t$ कई विशिष्ट साइक्लिक विस्थापन वर्गों (cyclic displacement classes) में विभाजित हो जाता है। इसके परिणामस्वरूप, एक प्रत्यक्ष कार्यान्वयन के लिए $R_{direct} = \sum_{t=0}^{m-1} (m-t) = \frac{m(m+1)}{2}$ रोटेशन्स की आवश्यकता होती है। लेखक यह जांचते हैं कि क्या यह त्रिकोणीय लागत बिट-रिवर्स्ड लेआउट में प्रीफिक्स कंप्यूटेशन का एक अंतर्निहित गुण है या विशिष्ट रूटिंग टोपोलॉजी का एक आर्टिफैक्ट है।

कार्यप्रणाली और निर्माण

कागज एक रेप्लिकेटेड-एग्रीगेट इनवेरिएंट (replicated-aggregate invariant) पेश करता है ताकि रोटेशन की संख्या को क्वाड्रेटिक से लीनियर में कम किया जा सके।

सिमेंटिक रेप्लिकेशन (Semantic Replication): प्रत्येक स्लॉट को उसके सटीक लॉजिकल प्रीसेडेसर तक रूट करने के बजाय, यह निर्माण एक ऐसी स्थिति बनाए रखता है जहाँ एक अलाइन किए गए लॉजिकल ब्लॉक के भीतर प्रत्येक स्लॉट उस ब्लॉक का पूर्ण एग्रीगेट (complete aggregate) संग्रहीत करता है।
सिबलिंग-ब्लॉक एक्सचेंज (Sibling-Block Exchange): स्कैन के प्रत्येक स्तर $d$ $d$ पर (ब्लॉक के आकार $2^d$ $2^{d}$ को संयोजित करते हुए), एल्गोरिदम एक विशिष्ट ऑफसेट $s_d = 2^{m-d-1}$ $s_{d} = 2^{m - d - 1}$ द्वारा एग्रीगेट स्टेट को रोटेट करता है।
- बिट रिवर्सल के तहत, एक पैरेंट ब्लॉक के दो बच्चे (children) ठीक $s_d$ द्वारा अलग किए गए भौतिक कोसेट्स (cosets) में स्थित होते हैं।
- एक रोटेशन $s_d$ एक स्लॉट को सिबलिंग ब्लॉक की किसी स्थिति में मैप करता है। चूंकि सिबलिंग का एग्रीगेट उसके सभी स्लॉट्स में रेप्लिकेटेड होता है, इसलिए सिबलिंग ब्लॉक का कोई भी स्थान सही सिमेंटिक मान प्रदान करता है।
- यह नॉनकम्यूटेटिव मोनोइड्स के लिए शुद्धता बनाए रखने हेतु पब्लिक मास्क का उपयोग करके, एक एकल निर्देशित साइक्लिक रोटेशन को दोनों चाइल्ड ओरिएंटेशन के लिए वैध एग्रीगेट्स की आपूर्ति करने की अनुमति देता है।
एक्सक्लूसिव स्कैन फॉर्मुलेशन (Exclusive Scan Formulation): यह एक एक्सक्लूसिव स्कैन (वर्तमान तत्व से पहले का प्रीफिक्स आउटपुट करना) लागू करता है। यह डिजिट करेक्शन के लिए इनकमिंग कैरी प्राप्त करने हेतु अंतिम लॉजिकल-प्रीसेडेसर शिफ्ट की आवश्यकता को समाप्त करता है, जो अन्यथा लेआउट-सेंसिटिव रूटिंग को पुनः पेश कर सकता था।
लोअर बाउंड प्रूफ (Lower Bound Proofs): यह पेपर स्थापित करता है कि इस मॉडल में $2^m$ इनपुट्स पर निर्भर आउटपुट कंप्यूट करने वाले किसी भी सर्किट के लिए $m$ रोटेशन्स एक ग्लोबल लोअर बाउंड है। यह प्रमाण एक सबसेट-सम तर्क पर आधारित है: यदि $R$ रोटेशन्स का उपयोग किया जाता है, तो अधिकतम $2^R$ विशिष्ट इनपुट विस्थापनों (displacements) तक एक निश्चित आउटपुट पहुँच सकता है। सभी $2^m$ इनपुट्स को कवर करने के लिए, $R \ge m$ आवश्यक है। इसके अलावा, यह पेपर सिद्ध करता है कि इस बाउंड को प्राप्त करने के लिए रोटेशन ऑफसेट्स को एक पूर्ण 2-एडिक बेसिस (2-adic basis) (प्रत्येक वैल्यूएशन $0, \dots, m-1$ के लिए एक ऑफसेट) बनाना चाहिए।

मुख्य योगदान

ऑप्टिमल स्कैन कंस्ट्रक्शन: एक समावेशी (inclusive) और एक्सक्लूसिव स्कैन एल्गोरिथ्म जो बिट-रिवर्स्ड लेआउट के लिए $R = m$ रोटेशन्स और $D = m$ मोनोइड डेप्थ प्राप्त करता है। यह रोटेशन काउंट को डायरेक्ट टोपोलॉजी के $O(m^2)$ से घटाकर $O(m)$ कर देता है।
ऑप्टिमलिटी की रिजिडिटी (Rigidity of Optimality): सभी ऑप्टिमल सर्किट्स का एक लक्षण वर्णन। यदि एक सर्किट ठीक $m$ रोटेशन्स का उपयोग करता है, तो ऑफसेट्स को एक पूर्ण 2-एडिक बेसिस बनाना चाहिए। यह सिद्ध करता है कि रोटेशन प्रोफाइल रिजिड है, भले ही सर्किट टोपोलॉजी भिन्न हो।
रोटेशन-की फ्रंटियर (Rotation-Key Frontier): सीधे कीकृत ऑफसेट्स ( $K$ $K$ ) की संख्या और ऑनलाइन रोटेशन कॉल्स ( $R$ $R$ ) की संख्या के बीच ट्रेड-ऑफ का विश्लेषण।
- यह एक उत्पाद लोअर बाउंड व्युत्पन्न करता है: $\prod (c_j + 1) \ge 2^m$ , जहाँ $c_j$ वह संख्या है जितनी बार की $j$ का उपयोग किया जाता है।
- जब $K, m$ को विभाजित करता है, तो सटीक फ्रंटियर $R^* = K \cdot (2^{m/K} - 1)$ सिद्ध होता है।
रेडिक्स-CKKS इंस्टेंशिएशन: रेडिक्स-आधारित CKKS में सटीक कैरी और बरो (borrow) प्रोपेगेशन के लिए एक्सक्लूसिव स्कैन का अनुप्रयोग। यह नेचुरल ऑर्डर को बहाल किए बिना या अंतिम शिफ्ट किए बिना पूर्णांक तुलना और मॉड्यूलर अंकगणित की अनुमति देता है।
बैचिंग एफिशिएंसी: यह प्रदर्शन करता है कि रेप्लिकेटेड स्कैन के लाभ पूर्ण रूप से भरे हुए डिजिट-मेजर इंटरलीविंग्स के लिए भी बने रहते हैं, जहाँ $g$ स्वतंत्र पूर्णांकों को रोटेशन काउंट को बढ़ाए बिना एक ही साइफरटेक्स्ट में पैक किया जाता है।

परिणाम और मूल्यांकन

लेखकों ने अपने एल्गोरिथ्म को Lattigo (Go) में लागू किया और इसकी तुलना दो बेसलाइन्स से की:

डायरेक्ट बिट-रिवर्स्ड प्रीसेडेसर: एक नेटिव $O(m^2)$ रोटेशन दृष्टिकोण।
नॉर्मलाइज-स्कैन-रिस्टोर (Normalize–Scan–Restore): एक बेसलाइन जो डेटा को नेचुरल ऑर्डर में बदलती है, स्कैन करती है, और फिर वापस बदलती है।

$m=7$ (128 स्लॉट्स) पर मुख्य निष्कर्ष:

रोटेशन्स: 28 (डायरेक्ट) से घटकर 7 (रेप्लिकेटेड) रह गए।
इवैल्यूएशन कीज़: स्टोरेज 70.0% कम हो गया (908.6 MB $\to$ 272.6 MB)।
मेमोरी: पीक हीप यूसेज 63.9% कम हो गया (2.30 GB $\to$ 830.5 MB)।
लेटेंसी: रेप्लिकेटेड स्कैन ने आइसोलेटेड स्कैन लेटेंसी में डायरेक्ट प्रीसेडेसर विधि की तुलना में 19.9% का सुधार किया।
एंड-टू-एंड पाइपलाइन: डेप्थ-5 डाउनस्ट्रीम पाइपलाइन में, रेप्लिकेटेड स्कैन ने 'नॉर्मलाइज-रिस्टोर' बेसलाइन द्वारा आवश्यक पूर्ण बूटस्ट्रैपिंग ऑपरेशन से बचा। इससे 4.31 $\times$ का औसत पेयर्ड स्पीडअप (95% CI [3.69, 4.92]) प्राप्त हुआ।

पेपर नोट करता है कि हालांकि छोटे $m$ के लिए "नॉर्मलाइज-स्कैन-रिस्टोर" में कम मोनोइड कंपोजिशन के कारण कम आइसोलेटेड लेटेंसी हो सकती है, लेकिन रेप्लिकेटेड स्कैन $m \ge 5$ पर अधिक तेज़ हो जाता है और बेहतर संसाधन दक्षता (कीज़, मेमोरी, मोडुलस लेवल्स) प्रदान करता है।

महत्व और दावे

यह पेपर दावा करता है कि बिट-रिवर्स्ड SIMD प्रतिनिधित्व को बनाए रखना क्रमबद्ध प्रीफिक्स गणना के लिए अनिवार्य रोटेशन ओवरहेड नहीं है। इसका महत्व निम्नलिखित में निहित है:

क्वाड्रेटिक बैरियर को तोड़ना: यह सिद्ध करना कि बिट-रिवर्स्ड लेआउट में डायरेक्ट रूटिंग का $O(m^2)$ लागत अंतर्निहित नहीं है, बल्कि इसे सिमेंटिक रेप्लिकेशन के माध्यम से सैद्धांतिक लोअर बाउंड $O(m)$ तक कम किया जा सकता है।
संसाधन ट्रेड-ऑफ: यह स्थापित करना कि रोटेशन लागत (रोटेशन्स) और की स्टोरेज में कमी, अधिक पैक किए गए मोनोइड वर्क ( $2m-1$ कंपोजिशन बनाम $m$ ) और एक दूसरे लाइव स्टेट वेक्टर की कीमत पर आती है। पेपर का तर्क है कि यह ट्रेड-ऑफ उन गहरे पाइपलाइनों के लिए अनुकूल है जहाँ मोडुलस लेवल्स और बूटस्ट्रैपिंग बाधाएं (bottlenecks) हैं।
सटीकता: रोटेशन-की प्रबंधन के लिए सटीक लोअर बाउंड और फ्रंटियर लक्षण वर्णन प्रदान करना, जो विशिष्ट डिपेंडेंसी पैटर्न के लिए ह्यूरिस्टिक ऑप्टिमाइज़ेशन से आगे बढ़कर प्रमाणित सीमाओं तक जाता है।

यह कार्य एक विशिष्ट बिट-रिवर्स्ड लेआउट बाधा के लिए एक अनुकूलन के रूप में प्रस्तुत किया गया है, जो सामान्य प्रीफिक्स नेटवर्क थ्योरी से अलग है, और इसे एक मानक CKKS कार्यान्वयन के माध्यम से कठोर कॉम्बिनेटरियल प्रमाणों और अनुभवजन्य मूल्यांकन के माध्यम से मान्य किया गया है।