💻 computer science

Lower Bounds on Black-Box Constructions of Pseudorandom Functions

यह शोध पत्र यह स्थापित करता है कि एक छद्म यादृच्छिक जनरेटर (PRG) से एक छद्म यादृच्छिक फलन (PRF) का कोई भी पूर्णतः ब्लैक-बॉक्स निर्माण, एक-बिट आउटपुट वाले कमजोर PRF के लिए भी, $o(n/\log n)$ गैर-अनुकूली कॉल्स (non-adaptive calls) प्राप्त नहीं कर सकता है, जिससे ऐसे निर्माणों की दक्षता पर कड़े निचले स्तर के प्रमाण (lower bounds) प्राप्त होते हैं और एकल-इनवोकेशन निर्माण की संभावना एक प्रमुख खुले प्रश्न के रूप में शेष रहती है।

मूल लेखक: Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

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

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

CC BY 4.0

मूल लेखक: Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

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

डिजिटल लॉकस्मिथ की दुविधा

कल्पना कीजिए कि आप एक मास्टर लॉकस्मिथ हैं जो एक अटूट तिजोरी का दरवाजा बनाने की कोशिश कर रहे हैं। डिजिटल सुरक्षा की दुनिया में, यह "तिजोरी" एक स्यूडोरेन्डम फंक्शन (PRF) है। एक PRF को एक जादुई मशीन के रूप में सोचें: आप इसमें एक गुप्त कुंजी (secret key) और एक विशिष्ट इनपुट (जैसे कि कमरा नंबर) डालते हैं, और यह एक ऐसा नंबर स्ट्रिंग बाहर निकालता है जो देखने वाले के लिए पूरी तरह से रैंडम (यादृच्छिक) लगता है। हालांकि, यदि आप उसी गुप्त कुंजी का उपयोग फिर से करते हैं, तो यह हमेशा बिल्कुल वही "रैंडम" स्ट्रिंग उत्पन्न करता है। यही निरंतरता इसे आपके ईमेल को सुरक्षित करने, आपके बैंक लेनदेन को सुरक्षित करने और आपके पासवर्ड को सुरक्षित रखने के लिए उपयोगी बनाती है।

इस जादुई मशीन को बनाने के लिए, क्रिप्टोग्राफर अक्सर एक सरल चीज़ से शुरुआत करते हैं जिसे स्यूडोरेन्डम जेनरेटर (PRG) कहा जाता है। एक PRG एक छोटे, कुशल बीज (seed) की तरह है जो एक विशाल, रैंडम दिखने वाले जंगल में विकसित होता है। यह एक छोटी, गुप्त स्ट्रिंग लेता है और उसे एक बहुत लंबी स्ट्रिंग में फैला देता है जो किसी भी कंप्यूटर प्रोग्राम के लिए रैंडम दिखती है। बड़ा सवाल क्रिप्टोग्राफी में यह रहा है: हमें इस "बीज-फैलाव" (seed-stretching) वाली मशीन का उपयोग करके अपना "तिजोरी का दरवाजा" बनाने के लिए कितनी बार इसकी आवश्यकता होगी?

दशकों से, मानक रेसिपी (जिसे GGM कंस्ट्रक्शन के रूप में जाना जाता है) यह रही है कि बीज-फैलाव वाली मशीन का बार-बार, एक पेड़ जैसी संरचना में, लगभग $\omega(\log n)$ बार उपयोग किया जाए (जहाँ $n$ बीज का आकार है)। यह बहुत अच्छा काम करता है, लेकिन यह थोड़ा बोझिल लगता है। क्या कोई शॉर्टकट है? क्या हम बीज-फैलाव वाली मशीन का केवल एक बार उपयोग करके एक आदर्श तिजोरी का दरवाजा बना सकते हैं? या शायद केवल कुछ ही बार? यह पेपर इसी प्रश्न की गहराई में जाता है, जो एक जासूस की तरह यह सिद्ध करने की कोशिश कर रहा है कि चाहे आप कितने भी चतुर क्यों न हों, आप बहुत कम बार बीज को फैलाकर एक सुरक्षित तिजोरी का दरवाजा नहीं बना सकते।

पेपर की बड़ी खोज: "बहुत कम" की समस्या

यह पेपर, जिसे बार अलोन, इताई डिनर और मुथुरमाक्रमकृष्णन वेंकिटसुब्रमण्यम द्वारा लिखा गया है, इस मौलिक प्रश्न को हल करता है: एक स्यूडोरेन्डम फंक्शन (PRF) बनाने के लिए हमें एक स्यूडोरेन्डम जेनरेटर (PRG) को न्यूनतम कितनी बार कॉल करना चाहिए?

लेखक सिद्ध करते हैं कि एक विशिष्ट और बहुत ही तर्कसंगत प्रकार के निर्माण के लिए, उत्तर है "आपकी उम्मीद से बहुत अधिक।" विशेष रूप से, वे दिखाते हैं कि आप एक "पूरी तरह से ब्लैक-बॉक्स" विधि का उपयोग करके एक सुरक्षित PRF नहीं बना सकते यदि आप PRG को बहुत कम बार कॉल करते हैं—विशेष रूप से, लगभग $n / \log n$ बार से कम (जहाँ $n$ PRG के इनपुट की लंबाई है)।

उनके प्रमाण को समझने के लिए, "नकली पहचानें" (Spot the Fake) के खेल की कल्पना करें।

सेटअप: एक "रिडक्शन" (निर्माता) एक PRG का उपयोग करके एक PRF बनाने की कोशिश करता है। उनके पास एक "एडवर्सरी" (हैकर) भी है जो यह बताने की कोशिश कर रहा है कि क्या PRF असली है या केवल एक रैंडम फंक्शन है।
ट्रिक: लेखक एक ऐसी स्थिति की कल्पना करते हैं जहाँ निर्माता "क्वेरी-बाउंडेड" (query-bounded) है। इसका मतलब है कि निर्माता हैकर से मदद मांग सकता है, लेकिन वह जितनी बार सवाल पूछता है, उसकी संख्या बहुत अधिक नहीं बढ़ सकती।
काउंटर-अटैक: लेखक एक "रियल एडवर्सरी" (वास्तविक विरोधी) और एक "आइडियल एडवर्सरी" (आदर्श विरोधी) का निर्माण करते हैं।
- आइडियल एडवर्सरी: यह एक सुपर-पावरफुल, धीमा कंप्यूटर है जो डेटा को देखने के लिए हर संभावित गुप्त कुंजी की जांच कर सकता है। यह आसानी से बता सकता है कि कोई फंक्शन PRF है या रैंडम।
- रियल एडवर्सरी: यह वह है जिसे निर्माता वास्तव में उपयोग करता है। इसके पास सुपरपावर नहीं है; यह केवल निर्माता द्वारा पूछे गए सीमित प्रश्नों को देखता है।
खुलासा: लेखक सिद्ध करते हैं कि यदि निर्माता बहुत कम बार PRG को कॉल करता है, तो "रियल एडवर्सरी" बिना वास्तव में PRG की सुरक्षा को तोड़े, "आइडियल एडवर्सरी" की पूरी तरह से नकल कर सकता है। यह एक विरोधाभास पैदा करता है: यदि निर्माता इतने कम कॉल्स के साथ एक सुरक्षित PRF बना सकता था, तो वह PRG की सुरक्षा को भी एक ऐसे तरीके से तोड़ पाता जो व्यावहारिक रूप से बहुत धीमा होता, जो इस धारणा का खंडन करता है कि PRG सुरक्षित है।

मुख्य परिणाम:
पेपर सिद्ध करता है कि नॉन-एडैप्टिव (non-adaptive) निर्माणओं के लिए (जहाँ निर्माता सभी PRG प्रश्न पहले ही तय कर लेता है), $o(n / \log n)$ कॉल्स से कम में एक PRF बनाना असंभव है। यह तब भी सच है जब PRF केवल एक सिंगल बिट (0 या 1) आउटपुट करता है और यहाँ तक कि यदि हैकर सरल, रैंडम प्रश्न पूछने तक सीमित है।

"लॉन्ग आउटपुट" (Long Output) परिणाम:
लेखकों ने उन PRFs का भी अध्ययन किया जो लंबे डेटा स्ट्रिंग्स (केवल एक बिट नहीं) उत्पन्न करते हैं। उन्होंने सिद्ध किया कि भले ही निर्माता "एडैप्टिव" (एक-एक करके प्रश्न पूछना और अगले प्रश्न का निर्णय लेने के लिए उत्तरों का उपयोग करना) होने की अनुमति दे, फिर भी एक कठिन सीमा है। यदि PRG इनपुट को थोड़ा फैलाता है, तो आपको कम से कम लगभग $out / \log n$ कॉल्स की आवश्यकता होती है। यदि PRG इसे बहुत अधिक फैलाता है, तो आपको कम से कम $out / r$ कॉल्स की आवश्यकता होती है।

"एक कॉल" के सपने का क्या हुआ

लंबे समय से, क्रिप्टोग्राफर्स सोचते थे कि क्या "सिंगल-कॉल" निर्माण संभव है—बीज को केवल एक बार फैलाकर एक आदर्श PRF बनाना।

नॉन-एडैप्टिव तरीकों के लिए: यह पेपर प्रभावी रूप से इसे खारिज करता है। आप एक स्थिर संख्या में कॉल्स (जैसे 1, 2, या 10) के साथ एक सुरक्षित PRF नहीं बना सकते यदि इनपुट का आकार बढ़ता है। गणित इसकी अनुमति नहीं देता।
एडैप्टिव तरीकों के लिए: यह पेपर सभी एडैप्टिव परिदृश्यों के लिए सिंगल-कॉल निर्माण को खारिज नहीं करता है। इसके बजाय, यह दिखाता है कि लंबे आउटपुट वाले PRFs के लिए, कॉल्स की संख्या आउटपुट के आकार के साथ स्केल होनी चाहिए। आप एक विशाल तिजोरी के लिए बहुत कम, निश्चित संख्या में कॉल्स के साथ काम नहीं चला सकते यदि आउटपुट बड़ा है। यह प्रश्न कि क्या छोटे आउटपुट वाले PRFs के लिए सिंगल-कॉल एडैप्टिव निर्माण मौजूद है, अभी भी खुला है।

"क्वेरी-बाउंडेड" की चेतावनी

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

निष्कर्ष

यह पेपर केवल एक सीमा का सुझाव नहीं देता है; यह एक गणितीय प्रमाण प्रदान करता है कि PRFs बनाने का "शॉर्टकट" एक बंद रास्ता है। यदि आप एक सुरक्षित, ब्लैक-बॉक्स PRF चाहते हैं, तो आप चरणों को छोड़ नहीं सकते। आपको PRG को पर्याप्त बार कॉल करने की लागत चुकानी होगी ताकि यह सुनिश्चित हो सके कि "एन्ट्रॉपी" (अनिश्चितता और अप्रत्याशितता) इतनी अधिक है कि वह किसी भी हैकर को मूर्ख बना सके। प्रसिद्ध GGM कंस्ट्रक्शन, जो लगभग $\omega(\log n)$ कॉल्स का उपयोग करता है, लगभग अनुकूल (optimal) साबित होता है। एक ही ईंट से एक किला बनाने का सपना इस संदर्भ में गणितीय रूप से असंभव है।

तकनीकी सारांश: ब्लैक-बॉक्स निर्माणों पर लोअर बाउंड्स (Lower Bounds)

समस्या विवरण (Problem Statement)

यह शोध पत्र क्रिप्टोग्राफी के एक मौलिक खुले प्रश्न को संबोधित करता है: एक पूर्ण ब्लैक-बॉक्स निर्माण के माध्यम से एक छद्म-यादृच्छिक फलन (Pseudorandom Function - PRF) का निर्माण करने के लिए एक छद्म-यादृच्छिक जनरेटर (Pseudorandom Generator - PRG) के आह्वान (invocations) की न्यूनतम संख्या क्या होनी चाहिए?

गोल्डरेक, गोल्डवासर और गिमिली (GGM) के मौलिक कार्य ने स्थापित किया कि एक ट्री-आधारित दृष्टिकोण का उपयोग करके PRG से एक PRF का निर्माण किया जा सकता है। लेविन की डोमेन एक्सटेंशन तकनीक के साथ संयोजन करने पर, इस निर्माण के लिए PRG के $\omega(\log n)$ कॉल्स की आवश्यकता होती है, जहाँ $n$ PRG का इनपुट लेंथ है। हालांकि हाल ही के काम द्वारा बीमैल, माल्किन और मेज़र ने एक विशिष्ट वर्ग के "ट्री कंस्ट्रक्शन" के लिए GGM की इष्टतमता (optimality) को सिद्ध किया है, लेकिन सामान्य मामला अभी भी अनसुलझा है। विशेष रूप से, यह अज्ञात है कि क्या एक सामान्य ब्लैक-बॉक्स तकनीकों का उपयोग करके $\omega(\log n)$ से कम कॉल्स के साथ या यहाँ तक कि एक एकल कॉल के साथ एक PRF बनाया जा सकता है।

यह कार्य पूर्णतः ब्लैक-बॉक्स निर्माणों (fully black-box constructions) के ढांचे के भीतर इस प्रश्न की जांच करता है, जहाँ निर्माण और सुरक्षा न्यूनीकरण (security reduction) दोनों ही ब्लैक-बॉक्स हैं। लेखक विशेष रूप से क्वेरी-बाउंडेड रिडक्शन (query-bounded reductions) नामक रिडक्शन के वर्ग पर ध्यान केंद्रित करते हैं, जहाँ रिडक्शन और एडवरसरी (adversary) के बीच बातचीत की संख्या, एडवरसरी की क्वेरी जटिलता से स्वतंत्र एक बहुपद (polynomial) द्वारा ऊपरी रूप से सीमित होती है (बशर्ते कि एडवरसरी पर्याप्त रूप से सफल हो)।

कार्यप्रणाली (Methodology)

लेखक अपने लोअर बाउंड्स को स्थापित करने के लिए मेटा-रिडक्शन प्रतिमान (meta-reduction paradigm) का उपयोग करते हैं। इस तकनीक में एक अक्षम "वास्तविक" एडवरसरी का निर्माण शामिल है जो एक "आदर्श" एडवरसरी (जो PRF को तोड़ सकती है) का अनुकरण कर सकती है, बिना सीधे PRG तक पहुँच प्राप्त किए, जिससे कम कॉल्स का उपयोग करके PRG की सुरक्षा को भंग किया जा सके।

मुख्य तकनीकी घटक:

क्वेरी-बाउंडेड रिडक्शन (Query-Bounded Reductions): लेखक एक रिडक्शन को तब क्वेरी-बाउंडेड कहते हैं जब एडवरसरी के अपने ऑरेकल (oracle) को की जाने वाली क्वेरी की संख्या की परवाह किए बिना, डिस्टिंग्विशिंग एडवरसरी के साथ बातचीत की संख्या एक बहुपद $d(n)$ द्वारा सीमित हो। यह वर्ग साहित्य में मौजूद अधिकांश ज्ञात रिडक्शन को समाहित करता है, जिसमें GGM और गोल्डरेक-लेविन निर्माण शामिल हैं।
आदर्श बनाम वास्तविक एडवरसरी (Ideal vs. Real Adversaries):
- आदर्श एडवरसरी ( $A_{ideal}$ ): एक अक्षम एडवरसरी जिसके पास PRG ऑरेकल तक घातीय (exponential) पहुँच है। यह एक बड़े इनपुट-आउटपुट युग्मों के अंश के अनुरूप की (key) खोजने का प्रयास करके PRF को तोड़ने का प्रयास करती है।
- वास्तविक एडवरसरी ( $A_{real}$ ): एक अक्षम एडवरसरी जिसके पास PRG तक पहुँच नहीं होती है। इसके बजाय, इसे रिडक्शन के PRG के साथ इंटरैक्शन द्वारा उत्पन्न क्वेरी-उत्तर युग्म प्राप्त होते हैं। यह देखे गए आउटपुट्स के साथ एक की (key) के सुसंगत होने की संभावना का अनुमान लगाकर $A_{ideal}$ का अनुकरण करने का प्रयास करती है।
स्कोर फंक्शन्स और स्वतंत्रता (Score Functions and Independence):
- मुख्य चुनौती यह है कि अलग-अलग इनपुट्स पर PRF के आउटपुट्स आश्रित हो सकते हैं यदि वे समान PRG सीड्स (seeds) साझा करते हैं।
- लेखक "फ्रीक्वेंट सीड्स" (ऐसे सीड्स जो कई इनपुट्स द्वारा उपयोग किए जाते हैं) की पहचान करने और उनके आउटपुट्स को निश्चित मानों से बदलने की एक प्रक्रिया पेश करते हैं। यह सक्रिय PRG कॉल्स की संख्या को कम करता है।
- शेष इनपुट्स के लिए, वे एक कॉम्बिनेटरियल दावे (Claim 3/6) का उपयोग करके यह दिखाते हैं कि या तो इनपुट्स का एक बड़ा सेट परस्पर विलग (disjoint) PRG सीड्स का उपयोग करता है (जो होफडिंग असमानता (Hoeffding's inequality) के माध्यम से स्वतंत्रता तर्क की अनुमति देता है) या ऐसे की (keys) की संख्या नगण्य है।
- आदर्श और वास्तविक एडवरसरी के बीच सांख्यिकीय दूरी (statistical distance) को संभालने के लिए, लेखक एक निश्चित थ्रेशोल्ड के बजाय एक रैंडमाइज्ड थ्रेशोल्ड (जो $[0.8, 1]$ से समान रूप से सैंपल किया गया है) का उपयोग करते हैं। यह निर्णय सीमा (decision boundary) को सुचारू बनाता है, यह सुनिश्चित करता है कि वास्तविक एडवरसरी का आउटपुट वितरण सांख्यिकीय रूप से आदर्श एडवरसरी के करीब हो, बशर्ते कि इनपुट्स $m$ की संख्या रिडक्शन क्वेरीज $d$ के सापेक्ष पर्याप्त रूप से बड़ी हो।
लॉन्ग आउटपुट्स के लिए एंट्रॉपी तर्क (Entropy Arguments for Long Outputs): दूसरे परिणाम (Theorem 2) के लिए, लेखक एक एंट्रॉपी-आधारित तर्क का उपयोग करते हैं। वे एक विशिष्ट PRG का निर्माण करते है जो केवल सीड के एक छोटे प्रीफिक्स पर रैंडमनेस लागू करता है। यह PRF की आउटपुट एंट्रॉपी को वास्तव में यादृच्छिक फलन की तुलना में काफी कम कर देता है, जिससे एक डिस्टिंग्विशर (distinguisher) निर्माण को तोड़ सकता है यदि कॉल्स की संख्या बहुत कम है।

मुख्य योगदान और परिणाम (Key Contributions and Results)

1. नॉन-एडैप्टिव कॉल्स के लिए लोअर बाउंड (Theorem 1)

यह शोध पत्र सिद्ध करता है कि कोई भी पूर्णतः ब्लैक-बॉक्स निर्माण नॉन-एडैप्टिव कॉल्स और क्वेरी-बाउंडेड रिडक्शन का उपयोग करके PRF बनाने के लिए अस्तित्व में नहीं है, यदि कॉल्स की संख्या $c$ इस प्रकार है:
$c = o\left(\frac{n}{\log n}\right) \quad \text{और} \quad c = o\left(\frac{in}{\log in}\right)$
जहाँ $n$ PRG इनपुट लेंथ है और $in$ PRF इनपुट लेंथ है।

दायरा (Scope): यह परिणाम तब भी मान्य है जब कमजोर PRFs (जहाँ एडवरसरी i.i.d. यूनिफॉर्म क्वेरीज तक सीमित है) और एक-बिट आउटपुट वाले PRFs के लिए भी लागू होता है।
निहितार्थ (Implication): यह उन PRFs के लिए एक स्थिर संख्या में नॉन-एडैप्टिव कॉल्स (जैसे, एक एकल कॉल) के साथ PRF बनाने की संभावना को खारिज करता है जिनका इनपुट लेंथ $in = \omega(\log n)$ है, जो क्वेरी-बाउंडेड रिडक्शन के लिए खुले प्रश्न के एक विशिष्ट मामले को हल करता है।

2. लॉन्ग आउटपुट्स के लिए लोअर बाउंड (Theorem 2)

यह शोध पत्र लॉन्ग आउटपुट्स ($out$) वाले PRFs के लिए एक लोअर बाउंड स्थापित करता है जो एडैप्टिव निर्माणों के लिए भी मान्य है और इसके लिए रिडक्शन का क्वेरी-बाउंडेड होना आवश्यक नहीं है।

परिणाम: $r$ स्ट्रेच वाले PRG से $out$ लंबाई वाले PRF का कोई भी पूर्णतः ब्लैक-बॉक्स निर्माण $\frac{out}{\max(r, \omega(\log n))}$ से कम कॉल्स का उपयोग करके संभव नहीं है।
GGM से तुलना: GGM निर्माण (लेविन के ट्रिक के साथ) $n$ -बिट आउटपुट उत्पन्न करने के लिए $n$ -बिट स्ट्रेच वाले PRG के $\omega(\log n)$ कॉल्स का उपयोग करता है। इसे 1-बिट स्ट्रेच PRG के साथ संयोजित करने पर (जिसके लिए $O(n/\log n)$ कॉल्स की आवश्यकता होती है), 1-बिट स्ट्रेच PRG के कुल कॉल्स $\omega(n)$ होते हैं। Theorem 2 $\Omega(n / \omega(\log n))$ का लोअर बाउंड दर्शाता है, जो यह दिखाता है कि GGM $\omega(\log n)$ के कारक तक इष्टतम (optimal) है।

महत्व और दावे (Significance and Claims)

यह शोध पत्र PRG से PRF निर्माण की दीर्घकालिक प्रश्न की इष्टतमता पर महत्वपूर्ण प्रगति करने का दावा करता है।

GGM की इष्टतमता: जबकि पिछले परिणाम "ट्री कंस्ट्रक्शन" तक सीमित थे, यह कार्य विशिष्ट लेकिन स्वाभाविक धारणाओं (क्वेरी-बाउंडेड रिडक्शन) के तहत सामान्य ब्लैक-बॉक्स निर्माणों के लिए लोअर बाउंड प्रदान करता है।
सिंगल-कॉल केस का समाधान: लेखक स्पष्ट रूप से कहते हैं कि उनका परिणाम क्वेरी-बाउंडेड रिडक्शन के वर्ग के लिए $in = \omega(\log n)$ इनपुट लेंथ वाले PRFs के लिए PRF बनाने के प्रश्न को हल करता है कि क्या PRF को PRG के एक एकल कॉल के साथ बनाया जा सकता है। वे प्रदर्शित करते हैं कि ऐसा निर्माण असंभव है।
मजबूती (Robustness): असंभवता के परिणाम कमजोर PRFs के लिए भी मान्य हैं और लंबे आउटपुट्स के मामले में, एडैप्टिव निर्माणों के लिए भी लागू होते हैं।
सीमाएँ (Limitations): लेखक विनम्रतापूर्वक स्वीकार करते हैं कि उनका मुख्य परिणाम (Theorem 1) "क्वेरी-बाउंडेड" धारणा पर निर्भर है। वे नोट करते कि यह अभी भी एक खुला प्रश्न है कि क्या इन लोअर बाउंड्स को सभी ब्लैक-बॉक्स रिडक्शन तक विस्तारित किया जा सकता है, क्योंकि उनका प्रमाण इस बात पर निर्भर करता है कि रिडक्शन की बातचीत की संख्या एडवरसरी की क्वेरी जटिलता से स्वतंत्र है।

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