💻 computer science

Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build PRFs in $\mathsf{NC}^1$ , Generically)

यह शोध पत्र एक सामान्य रूपांतरण (generic transformation) प्रस्तुत करता है जो न्यूनतम डेप्थ ओवरहेड के साथ कमजोर PRFs को मजबूत PRFs में परिवर्तित करता है, जिससे LWE, LPN और CDH सहित मानक धारणाओं से $\mathsf{NC}^1$ -कंप्यूटेबल PRFs के निर्माण को सक्षम बनाया जा सके, और इस प्रकार लो-डेप्थ क्रिप्टोग्राफी की दीर्घकालिक खुली समस्याओं का समाधान किया जा सके।

मूल लेखक: Youlong Ding, Aayush Jain, Ilan Komargodski

प्रकाशित 2026-08-27

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

CC BY 4.0

मूल लेखक: Youlong Ding, Aayush Jain, Ilan Komargodski

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

डिजिटल दुनिया में, सुरक्षा अक्सर एक विशेष प्रकार के गणितीय उपकरण पर निर्भर करती है जिसे छद्म-यादृच्छिक फलन (pseudorandom function) कहा जाता है। एक ऐसी मशीन की कल्पना करें जो एक गुप्त कोड और डेटा के एक टुकड़े को लेती है, और फिर संख्याओं की एक ऐसी स्ट्रिंग निकालती है जो देखने वाले के लिए पूरी तरह से यादृच्छिक (random) लगती है। यदि मशीन सही ढंग से काम कर रही है, तो कोई भी यह नहीं बता पाएगा कि इसका आउटपुट वास्तव में यादृच्छिक अनुक्रम से अलग है, भले ही उन्होंने मशीन को कई बार काम करते हुए देखा हो। ये उपकरण वे अदृश्य ताले और चाबियाँ हैं जो ऑनलाइन बैंकिंग से लेकर निजी संदेशों तक सब कुछ सुरक्षित रखते हैं। दशकों से, शोधकर्ता इन मशीनों को बनाने की कोशिश कर रहे हैं ताकि वे यथासंभव तेज़ चल सकें, विशेष रूप से उन्हें बहुत कम चरणों में काम करने के योग्य बनाकर। कंप्यूटर विज्ञान की भाषा में, इसका अर्थ है उन्हें एक बहुत ही उथले (shallow) सर्किट के साथ बनाना, जिससे गणना आधुनिक प्रोसेसरों पर लगभग तुरंत हो सके। ये उपकरण जितने तेज़ और सरल होंगे, जटिल प्रणालियों जैसे कि सुरक्षित मतदान या निजी डेटा साझाकरण में इनका उपयोग उतना ही कुशलता से किया जा सकेगा।

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

शोधकर्ताओं की एक टीम ने अब इस अंतर को एक नई, सामान्य विधि के माध्यम से पाट दिया है जो एक कमजोर, आसानी से बनने वाले उपकरण को एक मजबूत, सुरक्षित उपकरण में बदल देती है, वह भी उसकी गति को धीमा किए बिना। उनका कार्य, जिसका शीर्षक "Pseudorandom Functions in NC1 from LWE/LPN/CDH" है, यह प्रदर्शित करता है कि यह संभव है कि इन तेज़, उथले मशीनों का निर्माण तीन सबसे मौलिक और व्यापक रूप से भरोसेमंद धारणाओं का उपयोग करके किया जाए। शोधकर्ताओं ने एक पुराने विचार 'GGM कंस्ट्रक्शन' को परिष्कृत करके यह उपलब्धि हासिल की, जो छोटे-छोटे गणनाओं के एक पेड़ (tree) के माध्यम से एक जटिल फलन का निर्माण करता है। इसे करने का पारंपरिक तरीका एक लंबे गलियारे में चलने जैसा था जहाँ हर कदम के लिए समान प्रयास की आवश्यकता होती थी, जिससे पूरी यात्रा लंबी और धीमी हो जाती थी। नई विधि इस गलियारे के आकार को बदल देती है। जैसे-जैसे प्रक्रिया पेड़ में गहराई तक जाती है, प्रत्येक चरण में आवश्यक कार्य की मात्रा ज्यामितीय रूप से घटती जाती है। पहले कुछ कदम भारी होते हैं, लेकिन बाद के चरण इतने हल्के होते जाते हैं कि कुल प्रयास कम ही रहता है। यह "टेपरिंग" (tapering) तकनीक शोधकर्ताओं को पूरी प्रक्रिया को एक उथले, तेज़ सर्किट की सीमाओं के भीतर रखने की अनुमति देती है।

इस नए तरीके के काम करने को सिद्ध करने के लिए, टीम ने इसे तीन विशिष्ट गणितीय समस्याओं पर लागू किया जो हल करने के लिए कठिन मानी जाती हैं। पहला 'लर्निंग विद एरर्स' (Learning With Errors) की समस्या है, जिसमें शोर वाले डेटा के एक छिपे हुए पैटर्न को खोजना शामिल है। इस समस्या से तेज़ मशीनें बनाने के पिछले प्रयासों के लिए बहुत बड़ी संख्याओं वाले एक विशिष्ट, अधिक जटिल गणितीय संस्करण की आवश्यकता थी। नया कार्य दिखाता है कि बहुत छोटी संख्याओं वाला मानक संस्करण ही पर्याप्त है। दूसरी समस्या 'लर्निंग पैरिटी विद नॉइज़' (Learning Parity with Noise) है, जो बिट्स के एक ऐसे प्रवाह में छिपे हुए पैटर्न को खोजने से संबंधित है जिसमें रैंडम तरीके से बदलाव (flip) किया गया है। शोधकर्ताओं ने दिखाया कि उनकी विधि इस समस्या के मानक संस्करण के साथ काम करती है, जिससे पहले आवश्यक विशिष्ट, संरचित संस्करणों की आवश्यकता समाप्त हो गई। तीसरी समस्या 'कंप्यूटेशनल डिफी-हेलमैन' (Computational Diffie-Hellman) धारणा है, जो आधुनिक इंटरनेट सुरक्षा का एक आधार स्तंभ है जिसका उपयोग गुप्त कुंजियों (secret keys) के आदान-प्रदान के लिए किया जाता है। दशकों तक, इस धारणा से तेज़ मशीनें बनाने का एकमात्र ज्ञात तरीका इस समस्या के एक मजबूत, अधिक प्रतिबंधात्मक संस्करण पर निर्भर था। नया निर्माण सिद्ध करता है कि मानक संस्करण ही पर्याप्त है।

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

यह उपलब्धि यह अर्थ देती है कि पहली बार, हम इन आवश्यक सुरक्षा उपकरणों को अपनी गति से समझौता किए बिना, सबसे सामान्य और भरोसेमंद गणितीय आधारों का उपयोग करके बना सकते हैं। यह उन विशिष्ट, जटिल वेरिएंट्स की आवश्यकता को समाप्त करता है जिन्हें पहले दक्षता के लिए आवश्यक माना जाता था। इसका परिणाम भविष्य की डिजिटल सुरक्षा के लिए एक अधिक मजबूत और बहुमुखी आधार है, जो अधिक तेज़ और कुशल एन्क्रिप्शन विधियों को लागू करने की अनुमति देता है जिन्हें तकनीक के एक विस्तृत दायरे में तैनात किया जा सकता है। यह कार्य इस बात का निर्णायक प्रमाण है कि कमजोर, तेज़ उपकरणों और मजबूत, तेज़ उपकरणों के बीच की बाधा टूट गई है, जो कुशल क्रिप्टोग्राफिक डिज़ाइन के एक नए युग के द्वार खोलता है।

तकनीकी सारांश: LWE/LPN/CDH से NC1 में छद्म यादृच्छिक फलन (Pseudorandom Functions)

1. समस्या विवरण

कम समानांतर जटिलता (विशेष रूप से NC1 वर्ग के भीतर, जो बहुपद-आकार, लघु-गहराई वाले सर्किट द्वारा गणनीय है) वाले छद्म यादृच्छिक फलनों (PRFs) का निर्माण क्रिप्टोग्राफी में एक लंबे समय से खुला प्रश्न रहा है। जबकि PRFs को एक छद्म यादृच्छिक जनरेटर (PRG) से GGM रूपांतरण के माध्यम से सामान्य रूप से बनाया जा सकता है, यह विधि स्वाभाविक रूप से क्रमिक (sequential) है। भले ही अंतर्निहित PRG लघु-गहराई (logarithmic depth) में गणनीय हो, परिणामी PRF के लिए गहराई $\omega(\log n)$ आवश्यक होती है, जिससे वह NC1 के बाहर हो जाता है।

इस कार्य से पूर्व, ज्ञात NC1-गणनीय PRFs दुर्लभ थे और अत्यधिक विशिष्ट बीजगणितीय संरचनाओं या मजबूत धारणाओं पर निर्भर थे:

नाओर-रेनॉल्ड्स (1997, 2004): Decisional Diffie-Hellman (DDH) और गुणनखंड (factoring) से $TC_0 \subseteq NC1$ में PRFs का निर्माण किया।
बनर्जी-पेइकर्ट-रोसेन (2012): Ring-LWE से $TC_0$ में PRFs का निर्माण किया, लेकिन इसके लिए सुपर-पॉलीनोमियल मॉड्यूलस-टू-नॉइज़ अनुपात की आवश्यकता थी।
डिंग-जैन-कोमर्गोडोस्की (2025): LPN के संरचित वेरिएंट्स (जैसे SeededLPN या Ring-LPN) से NC1-गणनीय PRFs का निर्माण किया।

मुख्य चुनौती मानक धारणाओं (बहुपद मॉड्यूलस-टू-नॉइज़ अनुपात के साथ LWE, मानक LPN, और Computational Diffie-Hellman) से NC1-गणनीय PRFs प्राप्त करना है, बिना किसी संरचित वेरिएंट या सुपर-पॉलीनोमियल मापदंडों पर निर्भर रहे।

2. कार्यप्रणाली

यह शोध पत्र दो तरफा दृष्टिकोण प्रस्तुत करता है: कमजोर PRFs (WPRFs) से मजबूत PRFs में एक सामान्य गहराई-संरक्षण रूपांतरण (generic depth-preserving transformation), और मानक धारणाओं से नए गहराई-कुशल WPRF (या सिंथेसाइज़र) के निर्माण।

2.1 टेपरिंग-GGM (Tapering-GGM): एक सामान्य रूपांतरण

लेखक GGM ट्री निर्माण का एक नया अनुकूलन प्रस्तावित करते हैं, जिसे टेपरिंग-GGM कहा जाता है, जो एक WPRF को एक मजबूत PRF में अपग्रेड करता है और मूल्यांकन सर्किट की गहराई को संरक्षित रखता है।

टेपरिंग तंत्र (The Tapering Mechanism): एक मानक GGM ट्री में, स्टेट का आकार स्थिर रहता है, और गहराई ट्री के स्तरों की संख्या ( $\ell \cdot d_{WPRF}$ ) के साथ रैखिक रूप से बढ़ती है। टेपरिंग-GGM में, स्टेट का आकार प्रत्येक स्तर पर ज्यामितीय रूप से घटता है। यदि स्तर $i$ पर सुरक्षा पैरामीटर $\lambda^{(i)}$ है, तो लेखक $\lambda^{(i)} = \lambda^{2^{-i+1}}$ को परिभाषित करते हैं। फलस्वरूप, स्तर $i$ पर WPRF कॉल की गहराई, $d(\lambda^{(i)})$ , ज्यामितीय रूप से कम होती जाती है।
गहराई विश्लेषण: यदि आधार WPRF की गहराई $d(\lambda) = \Theta(\log \lambda)$ है, तो टेपरिंग-GGM निर्माण की कुल गहराई होती है:
$d_{total} = O(\log \lambda) + \sum_{i=1}^{\ell} d(\lambda^{(i)}) \approx O(\log \lambda) + \sum_{i=1}^{\ell} \log(\lambda^{2^{-i+1}}) = O(\log \lambda)$
यह ज्यामितीय क्षय सुनिश्चित करता है कि कुल गहराई $O(d(\lambda))$ बनी रहे, जिससे निर्माण (यदि इनपुट WPRF NC1 में है) NC1 के भीतर रहता है।
सुरक्षा चुनौतियाँ और समाधान:
- चुनौती: जैसे-जैसे ट्री गहरा होता जाता है, सुरक्षा पैरामीटर $\lambda^{(i)}$ छोटा (sub-polynomial) होता जाता है, जिससे अंतर्निहित WPRF की कम्प्यूटेशनल सुरक्षा टूट सकती है।
- समाधान 1 (हैशिंग): इनपुट को पहले एक पेयरवाइज इंडिपेंडेंट हैश फंक्शन के माध्यम से हैश किया जाता है। यह सुनिश्चित करता है कि उच्च संभावना के साथ, एडवरसरी के क्वेरीज़ को "बिखर" (shattered) दिया जाता है (अर्थात, शीर्ष $O(\log_\Delta q)$ स्तरों के भीतर अलग-अलग पथों पर मैप किया जाता है), जहाँ सुरक्षा पैरामीटर अभी भी बहुपद (polynomial) है।
- समाधान 2 (की-यूनिफॉर्मिटी): बिखराव बिंदु (shattering point) के नीचे के स्तरों के लिए, निर्माण सूचना-सैद्धांतिक (information-theoretic) सुरक्षा पर निर्भर करता है। लेखक मांग करते हैं कि WPRF की-यूनिफॉर्म (1-wise independent) हो। यदि बिखराव स्तर पर स्टेट छद्म-यादृच्छिक (pseudorandom) है, तो निम्न-स्तर के WPRFs के की-यूनिफॉर्म रूपांतरणों का संयोजन इस स्टेट को पूर्णतः यूनिफॉर्म आउटपुट में मैप करता है, चाहे निम्न-स्तर के WPRFs की कम्प्यूटेशनल कठोरता कुछ भी हो।

2.2 गहराई-कुशल WPRF निर्माण

लेखक मानक धारणाओं से नए WPRF निर्माणों के साथ टेपरिंग-GGM फ्रेमवर्क को लागू करते हैं:

LWE (Learning With Errors) से:
- लेखक बहुपद मॉड्यूलस-टू-नॉइज़ अनुपात ( $\alpha = n^{-\epsilon}$ ) के साथ मानक LWE से पहला NC1 WPRF निर्मित करते हैं।
- मुख्य तकनीकी उपकरण: एक राउंडेड गॉसियन सैंपलर (Rounded Gaussian Sampler) जो $O(\text{poly}(\log \log \lambda))$ गहराई में गणनीय है। वे $\ln$ , $\cos$ , और वर्गमूल के लिए लो-डेप्थ पॉलीनोमियल एप्रोक्सिमेशन का उपयोग करके बॉक्स-मुलर ट्रांसफॉर्म का अनुमान लगाते हैं।
- निर्माण: वे एक चेनिंग प्रतिमान (chaining paradigm) का उपयोग करते हैं (Kim [Kim20] से प्रेरित)। निर्माण स्तर दर स्तर मास्क किए गए LWE इनर प्रोडक्ट्स की गणना करता है। एक परत के आउटपुट के उच्च-क्रम बिट्स अगली परत के लिए एरर डिस्ट्रीब्यूशन को नियत रूप से सैंपल करते हैं। एरर सैंपलर की सीमा स्थिरता सुनिश्चित करती है, जिससे हाइब्रिड्स के माध्यम से सुरक्षा प्रमाण आगे बढ़ पाता है।
LPN (Learning Parity with Noise) से:
- लेखक डिंग, जैन और कोमर्गोडोस्की [DJK25] के एक हालिया परिणाम का लाभ उठाते हैं जो मानक LPN (अनिश्चित इनवर्स पॉलीनोमियल नॉइज़) से NC1 में WPRFs प्रदान करता है।
- इसे टेपरिंग-GGM के साथ जोड़कर, वे मानक LPN से पहले NC1 PRFs प्राप्त करते हैं, जिससे पिछले कार्यों के लिए आवश्यक संरचित वेरिएंट (जैसे Ring-LPN) की आवश्यकता समाप्त हो जाती है।
CDH (Computational Diffie-Hellman) से:
- लेखक देखते हैं कि टेपरिंग-GGM वास्तव में एक WPRF से भी कमजोर प्रिमिटिव की आवश्यकता रखता है: एक सिंथेसाइज़र (जहाँ इनपुट पूल एडवरसरी से छिपा हुआ होता है)।
- वे नैओर-रेनॉल्ड्स सिंथेसाइज़र निर्माण [NR95, NR99] का उपयोग करके इस रूपांतरण को लागू करते हैं, जो CDH धारणा के तहत NC1 में गणनीय है। इससे CDH से पहले NC1 PRFs प्राप्त होते हैं, जो पिछले DDH-आधारित निर्माणों में सुधार करता है।

3. मुख्य योगदान

सामान्य गहराई-संरक्षण रूपांतरण (Generic Depth-Preserving Transformation): एक ब्लैक-बॉक्स रूपांतरण जो किसी भी WPRF (या सिंथेसाइज़र) को, जो $d(\lambda) = \Omega(\log \lambda)$ गहराई में गणनीय है, को $O(d(\lambda))$ गहराई वाले मजबूत PRF में बदल देता है। यह उस सामान्य बाधा को हल करता है जो मानक धारणाओं से NC1 PRFs को रोकने वाली थी।
मानक LWE से NC1 PRFs: बहुपद मॉड्यूलस-टू-नॉइज़ अनुपात $\alpha = n^{-\epsilon}$ के साथ मानक LWE से NC1 में PRFs का पहला निर्माण, जो वैंकटनाथन के लेक्चर नोट्स में स्पष्ट रूप से बताई गई समस्या को हल करता है। यह GapSVP के बहुपद एप्रोक्सिमेशन फैक्टर्स की कठोरता पर निर्भर करता है।
मानक LPN से NC1 PRFs: मानक LPN धारणा से NC1 में PRFs का पहला निर्माण, जिससे Ring-LPN या Sparse LPN जैसे संरचित वेरिएंट की आवश्यकता समाप्त हो जाती है।
CDH से NC1 PRFs: CDH धारणा से NC1 में PRFs का पहला निर्माण, जो 30 साल पुराने नैओर-रेनॉल्ड्स परिणाम में सुधार करता है जो मजबूत Decisional Diffie-Hellman (DDH) पर निर्भर था।
लो-डेप्थ गॉसियन सैंपलर: $O(\text{poly}(\log \log \lambda))$ गहराई में राउंडेड गॉसियन एरर्स को सैंपल करने के लिए एक नवीन नियत सर्किट (deterministic circuit), जो LWE-आधारित WPRF के लिए एक महत्वपूर्ण घटक है।

4. परिणाम

यह शोध पत्र निम्नलिखित ठोस परिणाम स्थापित करता है:

प्रमेय (Theorem): यदि NC1 में WPRFs मौजूद हैं, तो NC1 में PRFs मौजूद हैं।
उपप्रमेय (Corollary - LWE): यदि शोर-टू-मॉड्यूलस अनुपात $\alpha = n^{-\epsilon}$ के लिए LWE धारणा सत्य है, तो NC1 में PRFs मौजूद हैं।
उपप्रमेय (Corollary - LPN): यदि शोर संभाव्यता $\mu = n^{-\epsilon}$ के लिए LPN धारणा सत्य है, तो NC1 में PRFs मौजूद हैं।
उपप्रमेय (Corollary - CDH): यदि CDH धारणा सत्य है, तो NC1 में PRFs मौजूद हैं।
उपप्रमेय (Corollary - GapSVP): यदि GapSVP $\tilde{O}(n^{1+\epsilon})$ कारक के भीतर अनुमानित करने के लिए कठिन है, तो NC1 में PRFs मौजूद हैं।

5. महत्व

यह शोध पत्र क्रिप्टोग्राफिक प्रिमिटिव्स की जटिलता के संबंध में कई लंबे समय से खुले प्रश्नों को हल करने का दावा करता है। PRF मूल्यांकन की गहराई को GGM रूपांतरण की क्रमिक प्रकृति से अलग करके, लेखक यह प्रदर्शित करते हैं कि मजबूत PRFs को बिना समानांतर दक्षता से समझौता किए एक विस्तृत श्रृंखला की मानक धारणाओं से बनाया जा सकता है।

विशेष रूप से, यह कार्य:

NC1 PRFs के लिए Ring-LWE और सुपर-पॉलीनोमियल मापदंडों पर निर्भरता को हटाता है, और मानक LWE की ओर बढ़ता है।
संरचित LPN वेरिएंट की निर्भरता को हटाता है, और मानक LPN की ओर बढ़ता है।
CDH-आधारित PRFs के लिए कठोरता धारणा को DDH से CDH तक कमजोर करता है।
एक सामान्य ढांचा (Tapering-GGM) प्रदान करता है जो किसी भी मौजूदा लॉग-डेप्थ WPRF (जैसे [ABG+14], [AR16] से) को लॉग-डेप्थ PRF में अपग्रेड कर सकता है, बशर्ते अंतर्निहित धारणा सत्य हो।

लेखक इस कार्य को क्रिप्टोग्राफी की समानांतर जटिलता को समझने में एक मौलिक कदम के रूप में देखते हैं, जिसके सुरक्षित कंप्यूटेशन प्रोटोकॉल, लर्निंग थ्योरी (PRF-बनाम-लर्निंग कनेक्शन के माध्यम से), और मेटा-कॉम्प्लेक्सिटी पर निहितार्थ हैं।