एक cryptographic proof अपने रहस्य को इस तरह छिपा सकता है कि “गायब simulator” की अनुपस्थिति साबित करना कठिन हो जाए

चाल यह सिद्ध करना नहीं है कि रहस्य छिपा हुआ है

शून्य-ज्ञान के सबसे सरल रूप से शुरू करें।

Alice Bob को यह विश्वास दिलाना चाहती है कि सुडोकू puzzle का समाधान है। यदि वह समाधान भेज दे, तो Bob मान जाएगा, लेकिन puzzle खत्म हो जाएगा। उसे कुछ अजीब चाहिए: यह प्रमाण कि समाधान मौजूद है, समाधान बताए बिना।

यही शून्य-ज्ञान प्रमाण का वादा है। प्रूवर (Alice) वेरिफ़ायर (Bob) को विश्वास दिलाता है कि कथन सत्य है, लेकिन कथन के सत्य होने के अलावा कुछ reveal नहीं करता।

समस्या यह है कि इस वादे की कीमत है। सामान्य गणितीय प्रमाण में दो सुविधाजनक विशेषताएँ होती हैं। पहला, वह एक संदेश हो सकता है: आप प्रमाण लिखते हैं, देते हैं और बात खत्म। दूसरा, उसमें पूर्ण soundness हो सकती है: असत्य कथन का कोई वैध प्रमाण होता ही नहीं। शास्त्रीय impossibility परिणाम बताते हैं कि शून्य-ज्ञान में इन दोनों सुविधाओं को इस रूप में बनाए रखना संभव नहीं — न दोनों को एक साथ, और कुछ परिस्थितियों में न हर एक को अलग से।

पहला, शून्य-ज्ञान प्रमाण को बातचीत चाहिए। यदि Alice एक ही संदेश भेजती है, और पहले से कोई trusted सेटअप arranged नहीं है, तो शून्य-ज्ञान गारंटी collapse हो जाती है—चाहे बदले में आप साउंडनेस जितनी भी कम करने को तैयार हों।

दूसरा, शून्य-ज्ञान प्रमाण को त्रुटि के लिए थोड़ी tolerance चाहिए। पूर्ण साउंडनेस माँगना इंटरैक्शन को भी चुपचाप खत्म कर देता है: ऐसा वेरिफ़ायर जिसे उसके यादृच्छिक विकल्प कुछ भी हों कभी fool नहीं किया जा सकता, वे विकल्प पहले से सुधार ही कर सकता है—और वेरिफ़ायर predictable होते ही Alice सारे उत्तर एक संदेश में दे सकती है, वही मामला जो पहले ही टूट चुका था।

Rahul Ilango का शोधपत्र इस double दीवार के आसपास रास्ता खोजता है। दीवार को नकारकर नहीं, और असंभव परिस्थिति में शास्त्रीय शून्य-ज्ञान पैदा करने का दिखावा करके नहीं। कदम अधिक subtle है: “reveals nothing” का अर्थ कमजोर करना, लेकिन इस तरह कि cryptographers जिन सुरक्षा गुण को वास्तव में परीक्षण कर सकते हैं वे बची रहें।

परिणाम का नाम है व्यावहारिक रूप से शून्य-ज्ञान।

पुराना परीक्षण: सिम्युलेटर मौजूद है

शून्य-ज्ञान को formalize करने का शास्त्रीय तरीका एक fictional helper इस्तेमाल करता है जिसे सिम्युलेटर कहते हैं।

विचार यह है: Jane की कल्पना करें, जिसे Alice का रहस्य नहीं पता। यदि Jane पूरी तरह अपने दम पर ऐसे प्रमाण उत्पन्न कर सकती है जो Bob को Alice से मिलने वाले प्रमाण जैसे ही दिखें, तो Alice के प्रमाण ने Bob को कुछ नया नहीं सिखाया। Jane Alice के रहस्य के बिना ही वही experience fake कर सकती थी।

इसलिए शास्त्रीय शून्य-ज्ञान actual सिम्युलेटर माँगता है। एक कुशल एल्गोरिदम सच में मौजूद होना चाहिए जो रहस्य—jargon में विटनेस—जाने बिना fake-looking प्रमाण बना सके। सुडोकू में विटनेस बस solved ग्रिड है।

यह definition शक्तिशाली है, लेकिन old impossibility ठीक यहीं काटती है। Intuition यह है: सचमुच non-interactive प्रमाण सिर्फ एक string है। Bob के पास string आने के बाद वह उसे किसी और को दिखा सकता है; उसे कथन दूसरों को सिद्ध करने की ability मिल गई, जो पहले ही “nothing” से अधिक लगती है। शास्त्रीय theorems इसी intuition को ऊपर की impossibilities में sharpen करती हैं।

फर्क को MegaSudoku से महसूस करें

यह फर्क समझने का जानबूझकर simplified तरीका है।

उपमा के गंभीर हिस्से में सामान्य 9-by-9 सुडोकू न लें। वह बहुत छोटा और finite है: computer उसे हल कर सकता है या सिद्ध कर सकता है कि समाधान नहीं है। इसके बजाय MegaSudoku(n) puzzles की परिवार सोचें। Usual नियम को पैमाना करें: रोकना आकार n चुनें, N = n^2 रखें, फिर N by N ग्रिड बनाएँ जिसे n by n blocks में बाँटा गया हो और जिसमें N चिह्न हों। सामान्य सुडोकू सिर्फ tiny n = 3, N = 9 मामला है: 9-by-9 ग्रिड, 3-by-3 blocks और नौ चिह्न। Proof-जटिलता कहानी तभी शुरू होती है जब n बढ़ सकता है, और ग्रिड अतिरिक्त गैजेटs ले सकता है जो उसे सुडोकू के वेश में SAT सूत्र जैसा व्यवहार कराएँ। SAT सूत्र बस yes/no बाधाएँ की list है: क्या variables को सत्य/असत्य assign किया जा सकता है ताकि हर बाधा satisfied हो?

विटनेस अभी भी easy to तस्वीर है। Alice को mega-Sudoku का पूर्ण वैध filling पता है। Bob को विश्वास करना है कि filling मौजूद है, लेकिन Alice उसे reveal नहीं करना चाहती। Whole filling भेजने पर Bob convinced होगा, रहस्य खत्म।

शास्त्रीय शून्य-ज्ञान संस्करण में Alice और Bob आपस में संवाद करते हैं। पुराने ढंग का एक सरल मानसिक मॉडल ढकी हुई टाइलों का इस्तेमाल करता है। Alice हल किए हुए ग्रिड को छिपाती है, हर दौर से पहले प्रतीकों के नाम गुप्त रूप से बदलती है और Bob को किसी यादृच्छिक स्थानीय बाधा—पंक्ति, स्तंभ, खंड या किसी छोटे गैजेट—की जाँच करने देती है। खोली गई कोशिकाओं में सभी प्रतीक अलग-अलग हों तो Bob का विश्वास बढ़ता है। फिर सब कुछ दोबारा ढक दिया जाता है और अगले दौर के लिए प्रतीकों के नाम फिर बदल दिए जाते हैं। (एक पेच यह है कि पहले से छपे संकेतों के लिए अतिरिक्त तरकीब चाहिए, क्योंकि नाम बदलने से वे भी छिप जाते हैं। नीचे टिप्पणी में शास्त्रीय प्रोटोकॉल का वास्तविक समाधान दिया गया है; आगे की चर्चा के लिए यह सरल तस्वीर पर्याप्त है।)

यह शोधपत्र का actual प्रोटोकॉल नहीं है। यह शास्त्रीय शून्य-ज्ञान का मानसिक मॉडल है:

• Alice और Bob back-और-forth करते हैं।
• Bob यादृच्छिक जाँच चुनता है।
• Alice केवल स्थानीय consistency reveal करती है, whole समाधान नहीं।
• गोपनीयता का प्रमाण दिखाता है कि Bob का view Alice के रहस्य समाधान के बिना उत्पन्न किया जा सकता था।

इसलिए शास्त्रीय शून्य-ज्ञान positive fact पर built है:

सिम्युलेटर वास्तव में मौजूद है।

अब comfortable हिस्से हटा दें। Alice एक प्रमाण string भेजती है और चली जाती है। Trusted सेटअप नहीं, पहले से shared यादृच्छिक string नहीं, और Bob को असत्य puzzle कभी accept नहीं करना। यही परिस्थिति शास्त्रीय शून्य-ज्ञान survive नहीं कर सकता।

तरकीब से पहले एक और character चाहिए। एक नियम-पुस्तिका सुधार करें: logician के अर्थ में औपचारिक प्रमाण-प्रणाली—स्थिर axioms और written गणितीय प्रमाण जाँच करने के यांत्रिक नियम। ZFC, mathematics के मानक axioms, canonical उदाहरण है। आगे सब कुछ पहले से चुने नियम-पुस्तिका के सापेक्ष है, और विकल्प flexible है: निर्माण आपके सुधार किए किसी भी नियम-पुस्तिका के लिए काम करती है, ZFC सहित।

(शोधपत्र से borrowed शब्दों की टिप्पणी: यहाँ “प्रमाण-प्रणाली” हमेशा इसी नियम-पुस्तिका—गणितीय प्रमाण जाँच करने वाले औपचारिक प्रणाली—का अर्थ है, Alice के भेजे messages का नहीं। Alice और Bob की मशीनरी को “प्रूवर और वेरिफ़ायर” कहा जाता है।)

Gödel-style संस्करण mega-Sudoku कहानी रखता है लेकिन प्रमाण बदलता है।

Displayed आकार का दूसरा बाधा प्रणाली चुनें, उसे D कहें। कहानी में S और D समान format के दो MegaSudoku(n) puzzles हैं। Behind scenes D अलग आकार की कठिन तार्किक सूत्र से आया हो सकता है; जरूरत हो तो harmless dummy बाधाएँ से pad करके समान ग्रिड में फिट किया जा सकता है। D ऐसी तार्किक सूत्र से बनाया जाता है जो वास्तव में unsatisfiable है: मान की कोई निर्धारण सभी बाधाएँ सत्य नहीं कर सकती, जैसे broken puzzle का legal completed ग्रिड नहीं। Toy उदाहरण ऐसी सूत्र होगी जो एक साथ “X सत्य है” और “X असत्य है” माँगे। इसलिए D का वैध filling नहीं है।

लेकिन D ऐसा broken puzzle नहीं होना चाहिए जिसे उजागर करना आसान हो। Toy उदाहरण विफल होता है: कोई भी नियम-पुस्तिका “X और नहीं-X” को एक रेखा में खंडन कर देगा। D को ऐसी तरह असत्य होना है कि चुना नियम-पुस्तिका छोटा तर्क से certify न कर सके। यदि नियम-पुस्तिका D को छोटा प्रमाण से खंडन कर सके, नीचे की कहानी collapse होगी: वैकल्पिक मार्ग जो Alice के रहस्य बिना प्रमाण पैदा कर सकता था formally नियम out हो जाएगा, और गोपनीयता गारंटी उसके साथ। इसलिए D ऐसी परिवार से चुना जाता है जिसे स्थिर नियम-पुस्तिका कुशलतापूर्वक खंडन करना नहीं कर सकता: नियम-पुस्तिका के भीतर कोई छोटा प्रमाण नहीं कि D का समाधान नहीं है।

Alice का एक-संदेश प्रमाण फिर either/or कथन के बारे में है:

या वास्तविक mega-Sudoku S का समाधान है, या decoy D का समाधान है।

यही तार्किक कड़ी है। D किसी जादुई तरीके से S को सत्य नहीं बनाता। प्रमाण का तर्क यह नहीं है कि “D का समाधान नहीं, इसलिए S का है।” वह disjunction S or D को सिद्ध करता है। पूर्ण soundness कहती है कि असत्य disjunction का कोई वैध प्रमाण नहीं हो सकता। चूँकि D वास्तव में असत्य है — उसका कोई समाधान नहीं — disjunction के सत्य होने का एकमात्र रास्ता S का सत्य होना है। इसलिए प्रमाण स्वीकार होता है तो S का समाधान मौजूद होना चाहिए। Decoy, असत्य S को सत्य नहीं बना सकता।

लेकिन शून्य-ज्ञान वाले हिस्से के लिए कल्पना करें कि यदि D का समाधान होता तो क्या होता। वह decoy समाधान वैकल्पिक witness बन सकता था। उससे simulator, Alice के वास्तविक mega-Sudoku समाधान को जाने बिना प्रमाण जैसी transcript बना सकता था। वास्तविकता में D का समाधान नहीं है, इसलिए यह रास्ता सचमुच उपलब्ध नहीं। महत्वपूर्ण बात यह है कि चुनी हुई नियम-पुस्तिका कुशलतापूर्वक यह सिद्ध नहीं कर सकती कि वह रास्ता बंद है।

इसलिए D के दो नौकरियाँ हैं। साउंडनेस के लिए D असत्य है, इसलिए “S or D” का वैध प्रमाण S को force करता है। Effective शून्य-ज्ञान के लिए D कठिन to खंडन करना है, इसलिए नियम-पुस्तिका उस decoy मार्ग को जल्दी नियम out नहीं कर सकता जो सिमुलेशन संभव बनाता।

इसलिए सुरक्षा परीक्षण अब यह नहीं है:

क्या हम सिद्ध कर सकते हैं कि सिम्युलेटर सच में मौजूद है?

वह बनता है:

क्या आपका नियम-पुस्तिका कुशलतापूर्वक सिद्ध कर सकता है कि सिम्युलेटर असंभव है?

यदि उत्तर no है, तो surprisingly मजबूत चीज अनुसरण करती है: हर सुरक्षा गारंटी जो (a) परीक्षण चला कर observe की जा सकती है, और (b) नियम-पुस्तिका के भीतर सिम्युलेटर के existence से provably अनुसरण करती है, वास्तव में hold करती है। उनमें से किसी पर successful हमला खुद वही अनुपस्थित छोटा खंडन बन जाएगा, और वह अनुपस्थित छोटा खंडन मौजूद नहीं है। यही व्यावहारिक रूप से शून्य-ज्ञान का “effective” हिस्सा है।

इसलिए classroom contrast:

शास्त्रीय शून्य-ज्ञान: प्रमाण सुरक्षित हैं क्योंकि सिम्युलेटर exists।

Gödel-style effective शून्य-ज्ञान: observable सुरक्षा परीक्षण के लिए प्रमाण सुरक्षित मानना किए जाते हैं क्योंकि नियम-पुस्तिका कुशलतापूर्वक सिद्ध करना नहीं कर सकता कि सिम्युलेटर असंभव है।

दूसरा दावा और कमज़ोर है। यही वजह है कि शोधपत्र शास्त्रीय संस्करण में टूटने वाली तीन विशेषताएँ रख सकता है: एक संदेश, no सेटअप और पूर्ण साउंडनेस।

नया परीक्षण: आप सिम्युलेटर की अनुपस्थिति सिद्ध करना नहीं कर सकते

Ilango की relaxation सवाल बदलती है।

शास्त्रीय शून्य-ज्ञान पूछता है:

क्या सिम्युलेटर मौजूद है?

व्यावहारिक रूप से शून्य-ज्ञान कुछ और कमज़ोर पूछता है:

क्या आपका चुना नियम-पुस्तिका कुशलतापूर्वक सिद्ध कर सकता है कि कोई सिम्युलेटर मौजूद नहीं है?

यह तकनीकी चाल जैसा लग सकता है, लेकिन मुख्य विचार यही है। निर्माण एक अजीब अवस्था में रहती है: सिम्युलेटर वास्तव में मौजूद नहीं है—शोधपत्र इस पर स्पष्ट है—लेकिन आपने जो नियम-पुस्तिका सुधार किया वह कुशलतापूर्वक सिद्ध करना नहीं कर सकता कि वह मौजूद नहीं। यदि हर खराब परिणाम जिसकी आपको परवाह है ऐसी खंडन माँगे, तो उन नतीजों के लिए प्रणाली शून्य-ज्ञान जैसा व्यवहार करता है।

यहीं Gödel आता है। Decoration के रूप में नहीं, और “Gödel crypto को सुरक्षित बनाता है” के रूप में नहीं। Connection proof-theoretic है। नियम-पुस्तिका सर्वोत्तम कहलाता है यदि सटीक अर्थ में वह सर्वोत्तम संभव हो: जब भी कोई नियम-पुस्तिका प्रासंगिक kind की सूत्र को छोटा प्रमाण से खंडन कर सकता है, सर्वोत्तम नियम-पुस्तिका भी कर सकता है, अधिकतम polynomially longer प्रमाण के साथ। Krajíček और Pudlák ने 1989 में conjecture किया कि कोई सर्वोत्तम प्रमाण-प्रणाली नहीं है: आप जो नियम-पुस्तिका सुधार करें, कोई दूसरा नियम-पुस्तिका सत्य कथन की किसी परिवार को बहुत अधिक succinctly सिद्ध करेगा। यह प्रमाण जटिलता की केंद्रीय खुला conjectures में से है और Gödel incompleteness प्रमेय का finite, जटिलता-theoretic cousin है: कुछ सत्य कथन आपके स्थिर नियम-पुस्तिका में छोटा प्रमाण नहीं रखते—इसलिए नहीं कि वे सिद्धांत में unprovable हैं, बल्कि इसलिए कि हर स्थिर नियम-पुस्तिका कुछ छोटा truths को छोटा प्रमाण के बिना छोड़ देता है।

शोधपत्र इस conjecture को mildly अधिक मज़बूत “infinitely often” form में assume करता है, जो क्रिप्टोग्राफ़िक उपयोग में मानक है। Krajíček और Pudlák के प्रमेय से payoff concrete है: हर नियम-पुस्तिका के लिए formulas की क्रम है जो वास्तव में unsatisfiable हैं, जिनकी छोटा खंडनs नियम-पुस्तिका नहीं दे सकता—और crucially, जिन्हें कुशल एल्गोरिदम उत्पन्न करना कर सकता है। यही last गुण, uniformity, विचार को existence दावा से actual एल्गोरिदम बनाती है जिसे Alice चला सकती है: decoys D assembly रेखा से आते हैं, पतला वायु से नहीं।

क्रिप्टोग्राफ़िक कदम इसी shortage of प्रमाण शक्ति को काम में लगाना है।

निर्माण क्या कर रही है

शोधपत्र की निर्माण को उसकी आकार तक पट्टी करें।

एक नियम-पुस्तिका सुधार करें—मान लें ZFC। Proof-जटिलता मान्यता के तहत कुशलतापूर्वक generatable formulas की क्रम है जो वास्तव में unsatisfiable हैं, लेकिन नियम-पुस्तिका के पास उनकी unsatisfiability का छोटा प्रमाण नहीं।

अब इस form का एक-संदेश प्रमाण बनाएं:

या वास्तविक कथन satisfiable है, या यह विशेष कठिन सूत्र satisfiable है।

विशेष कठिन सूत्र satisfiable नहीं है। इसलिए यदि मूल प्रमाण मशीनरी perfectly ध्वनि है, संदेश स्वीकार होने का अर्थ अभी भी वास्तविक कथन सत्य होना है। इससे पूर्ण साउंडनेस मिलता है।

लेकिन शून्य-ज्ञान-like सुरक्षा के लिए imagine करें कि विशेष कठिन सूत्र satisfiable होती। तब उसका विटनेस वास्तविक विटनेस जाने बिना प्रमाण simulate करने में इस्तेमाल हो सकता था। Reality में सूत्र satisfiable नहीं—लेकिन नियम-पुस्तिका कुशलतापूर्वक सिद्ध करना नहीं कर सकता कि ऐसा है। इसलिए वह कुशलतापूर्वक सिद्ध करना नहीं कर सकता कि सिम्युलेटर असंभव है।

यही hinge है। प्रणाली शास्त्रीय सिम्युलेटर उत्पन्न करके रहस्य hide नहीं करता। Observable सुरक्षा परीक्षण की बड़ी class के लिए रहस्य को नियम-पुस्तिका की इस inability के पीछे रखता है कि वह सिम्युलेटर की absence certify नहीं कर सकता।

शोधपत्र क्या दावा करता है

मुख्य प्रमेय layers में आता है। मुख्य परिणाम यह है:

एक मानक क्रिप्टोग्राफ़िक मान्यता—non-interactive विटनेस indistinguishable प्रमाण का existence, अच्छी तरह studied वस्तुएँ जो कई established मान्यता packages से अनुसरण करते हैं—और proof-जटिलता conjecture कि कोई (infinitely often) सर्वोत्तम प्रमाण-प्रणाली मौजूद नहीं के तहत, शोधपत्र हर chosen नियम-पुस्तिका के लिए NP/SAT का एक-संदेश प्रूवर और वेरिफ़ायर construct करता है जिसमें पूर्ण साउंडनेस, no सेटअप और उस नियम-पुस्तिका के सापेक्ष व्यावहारिक रूप से शून्य-ज्ञान है। (NP/SAT puzzle-like समस्याएँ का मानक “hardest सामान्य denominator” है; mega-Sudoku उसका एक costume है।)

परीक्षण-योग्य सुरक्षा गुण बचाए रखना करने के व्यापक दावा के लिए शोधपत्र एक और मानक मान्यता जोड़ता है, derandomization मान्यता P = BPP—लगभग, randomness एल्गोरिदम को essential अतिरिक्त शक्ति नहीं देती।

प्रमेय भाषा के बाहर:

• प्रमाण एक संदेश है।
• Trusted सेटअप नहीं है।
• असत्य कथन सिद्ध करना नहीं किए जा सकते।
• प्रूवर शास्त्रीय शून्य-ज्ञान नहीं है—उसका सिम्युलेटर नहीं है।
• लेकिन शास्त्रीय शून्य-ज्ञान के हर परीक्षण-योग्य, game-based सुरक्षा परिणाम को इस परिस्थिति में achieve किया जा सकता है।

“परीक्षण-योग्य” महत्वपूर्ण है। इसका अर्थ सुरक्षा failure adversary को खेल में run करके परीक्षण की जा सकती है। कई क्रिप्टोग्राफ़िक सुरक्षा definitions इसी form की हैं: क्या adversary दो encryptions अलग पहचान सकता है, कार्य invert कर सकता है, विटनेस recover कर सकता है या specified प्रयोग जीत सकता है? प्रमेय हर परीक्षण-योग्य गुण के लिए एक प्रूवर देता है, एक at a समय। एक एकल प्रूवर जिसमें हर परीक्षण-योग्य गुण एक साथ हो शायद असंभव है—old reusability हमला (“Bob प्रमाण दूसरों को दिखा सकता है”) खुद परीक्षण-योग्य गुण है, और यहाँ सच में विफल होती है। शोधपत्र का proposal है कि एकल प्रूवर संभवतः सभी प्राकृतिक परीक्षण-योग्य गुण शामिल कर सकता है—जो क्रिप्टोग्राफ़िक practice में वास्तव में आती हैं—लेकिन यह हिस्सा informal “प्राकृतिक” notion और स्पष्ट conjecture पर टिका conditional प्रमेय है। गारंटी observable failures को लक्ष्य करती है, secrecy के हर philosophical या सिमुलेशन-based अर्थ को नहीं।

एक concrete corollary नाम लेने लायक है: निर्माण uniform प्रूवर के साथ पहले non-interactive विटनेस hiding प्रमाण देती है—“puzzle का प्रमाण आपको उसका समाधान खोजने में मदद नहीं करता,” no इंटरैक्शन और no सेटअप के साथ—सुनने में मध्यम वस्तु जिसने दशकों तक निर्माण resist की।

यह क्या नहीं कहता

यही section piece को ईमानदार रखता है।

यह नहीं कहता कि old impossibility theorems गलत थे। निर्माण definition बदलकर उनसे बचती है।

यह no इंटरैक्शन, no सेटअप और पूर्ण साउंडनेस के साथ सामान्य शास्त्रीय शून्य-ज्ञान नहीं देती। शोधपत्र स्पष्ट है कि constructed प्रूवर का सिम्युलेटर नहीं है।

इसका अर्थ प्रमाण reuse नहीं हो सकता नहीं है। एक-संदेश प्रमाण किसी और को दिखाया जा सकता है; शोधपत्र deniability-style गुण बचाए रखना नहीं करता। (Trusted सेटअप वाले non-interactive शून्य-ज्ञान में भी यही सीमा है।)

इसका अर्थ यह व्यावहारिक प्रोटोकॉल तैनाती-तैयार नहीं है। यह जटिलता सिद्धांत और क्रिप्टोग्राफ़िक foundations है। परिणाम प्रमाण जटिलता और क्रिप्टोग्राफी की मुख्य मान्यताएँ पर निर्भर है और निर्माण सिद्धांत में क्या संभव है, उस बारे में है।

यह “Gödel” को magic सुरक्षा primitive नहीं बनाता। Gödel connection प्रमाण-प्रणालीs, सर्वोत्तम प्रमाण-प्रणालीs और incompleteness के finite analogues से है। उपयोगी intuition “incompleteness आपका password सुरक्षा देती है” नहीं। वह है: यदि नियम-पुस्तिका कुशलतापूर्वक सिद्ध करना नहीं कर सकता कि सिम्युलेटर असंभव है, तो ऐसी प्रमाण की जरूरत वाले हमले सुरक्षा definitions के level पर रोकना किए जा सकते हैं।

फिर भी यह दिलचस्प क्यों है

क्रिप्टोग्राफी अक्सर hardness को सुरक्षा में बदलती है। Factoring कठिन है, इसलिए RSA-style मान्यताएँ उपयोगी बनते हैं। Lattice समस्याएँ कठिन हैं, इसलिए lattice क्रिप्टोग्राफी उपयोगी है। यहाँ hardness अजीब है: “रहस्य compute करना कठिन” नहीं, बल्कि “यह सिद्ध करना कठिन कि कोई खास प्रमाण वस्तु exist नहीं कर सकता।”

इसीलिए शोधपत्र unusual लगता है। वह axioms और नियम-पुस्तिकाएँ को लगभग क्रिप्टोग्राफ़िक resources की तरह मानना करता है। Usual impossibility साउंडनेस और सिमुलेशन के बीच tension कहती है। Ilango का कदम इस tension को proof-theoretic curtain के पीछे रखता है: सिम्युलेटर absent है, लेकिन औपचारिक प्रणाली कुशलतापूर्वक उसकी absence उजागर करना नहीं कर सकता।

पाठक के लिए surprise यह नहीं कि यह आज के शून्य-ज्ञान प्रणालियाँ replace करेगा। शायद सीधे नहीं करेगा। Surprise यह है कि गणितीय logic की सीमा constructively इस्तेमाल की जा सकती है: दीवार की तरह ही नहीं, शामिल की तरह भी।

साक्ष्य कितना मजबूत है?

यह प्रमेय शोधपत्र है, इसलिए “साक्ष्य” जीवविज्ञान या astronomy शोधपत्र से अलग अर्थ रखता है। सवाल प्रयोग प्रतिकृति बनी या नहीं नहीं। सवाल है definitions, मान्यताएँ और प्रमाण श्रृंखला दावा समर्थन करते हैं या नहीं।

प्रमाण औपचारिक है और शोधपत्र मान्यताएँ साफ बताता है। मान्यताएँ casual नहीं। Non-interactive विटनेस indistinguishable प्रमाण क्रिप्टोग्राफी के मानक वस्तुएँ हैं और कई established मान्यता packages से अनुसरण करते हैं। No-सर्वोत्तम-proof-system conjecture प्रमाण जटिलता की केंद्रीय conjecture है। P = BPP मानक derandomization मान्यता है, केवल व्यापक परीक्षण-योग्य-property प्रमेय के लिए।

शोधपत्र यह भी तर्क देता है कि मान्यताएँ सही कीमत हैं, मनमाना ढाँचा नहीं: विपरीत दिशा का कथन सिद्ध करता है कि वे मूलतः आवश्यक हैं—यदि ऐसी निर्माण मौजूद हैं, तो non-interactive विटनेस indistinguishable प्रमाण exist करने ही चाहिए, और मानक एक-way कार्य मानकर कोई सर्वोत्तम प्रमाण-प्रणाली exist नहीं कर सकता। मान्यताएँ “दोनों ओर लाभ वाली” भी हैं: इनमें से किसी को खंडन करना अपने आप प्रमाण जटिलता, क्रिप्टोग्राफी या जटिलता सिद्धांत की महत्त्वपूर्ण खोज होगा।

लेकिन परिणाम conditional है, इसलिए विश्वास भी conditional। यदि मान्यताएँ विफल होना हों, प्रमेय की व्याख्या बदलती है। और मान्यताएँ hold करने पर भी गारंटी पूरा शास्त्रीय शून्य-ज्ञान नहीं; शोधपत्र का relaxed, proof-theoretic संस्करण है।

इसलिए सही विश्वास: उच्च कि शोधपत्र सुसंगत conditional possibility परिणाम establish करता है; मध्यम कि मान्यताएँ उस क्रिप्टोग्राफ़िक दुनिया को describe करती हैं जिसमें हम वास्तव में रहते हैं; immediate व्यावहारिक परिणाम पर कम।

यह क्यों मायने रखता है

शोधपत्र ऐसा रास्ता खोलता है जिसे बंद माना जाता था।

शास्त्रीय सिद्धांत कहती है: पूरा शून्य-ज्ञान सेटअप बिना एक संदेश नहीं हो सकता और perfectly ध्वनि नहीं हो सकता। Ilango का शोधपत्र कहता है: यदि हम शून्य-ज्ञान के उन नतीजों की माँग करें जिन्हें सुरक्षा games में परीक्षण किया जा सकता है, और सुरक्षा definition को नियम-पुस्तिका क्या कुशलतापूर्वक खंडन कर सकता या नहीं कर सकता इस पर निर्भर होना करने दें, तो उपयोगी व्यवहार का बड़ा हिस्सा वापस पाया जा सकता है—एक संदेश, no सेटअप और पूर्ण साउंडनेस के साथ।

यह छोटा definitional tweak नहीं। क्रिप्टोग्राफ़िक guarantees सोचने का अलग तरीका है। केवल यह मत पूछें कि क्या exists करता है; पूछें नियम-पुस्तिका क्या नियम out कर सकता है। Unprovability को philosophical nuisance की बजाय संरचना की तरह इस्तेमाल करें।

व्यावहारिक दुनिया कल नहीं बदलेगी। Conceptual मानचित्र बदलती है। अब औपचारिक अर्थ है जिसमें “कोई कुशलतापूर्वक सिद्ध करना नहीं कर सकता कि रहस्य रिसाव हुआ” इतना मजबूत हो सकता है कि “रहस्य रिसाव नहीं हुआ” से चाही गई कई game-based protections वापस मिलें।

इसीलिए title में Gödel है।

साफ सारांश

शून्य-ज्ञान प्रमाण प्रूवर को विटनेस reveal किए बिना वेरिफ़ायर को कथन सत्य होने का प्रमाण देने देते हैं। शास्त्रीय impossibility परिणाम कहते हैं कि शून्य-ज्ञान को सेटअप बिना एक संदेश में squeeze नहीं किया जा सकता और पूर्ण साउंडनेस नहीं रख सकता। Rahul Ilango का शोधपत्र इन impossibilities को खंडन नहीं करता। वह और कमज़ोर notion परिभाषित करता है, व्यावहारिक रूप से शून्य-ज्ञान: सिम्युलेटर सच में मौजूद होना जरूरी नहीं; requirement यह है कि chosen प्रमाण-प्रणाली—ZFC जैसा औपचारिक नियम-पुस्तिका—कुशलतापूर्वक सिद्ध न कर सके कि सिम्युलेटर मौजूद नहीं। क्रिप्टोग्राफी की मुख्य मान्यताएँ (non-interactive विटनेस indistinguishable प्रमाण) और प्रमाण जटिलता (no सर्वोत्तम प्रमाण-प्रणाली exists) के तहत शोधपत्र NP/SAT के एक-संदेश provers construct करता है, no सेटअप और पूर्ण साउंडनेस के साथ, जो शून्य-ज्ञान के परीक्षण-योग्य, game-based नतीजों गुण by गुण achieve करते हैं। सभी “प्राकृतिक” गुण शामिल करने वाला एकल प्रूवर आगे का partly conjectural extension है—और literally हर परीक्षण-योग्य गुण शामिल करना शायद असंभव है क्योंकि प्रमाण reusable रहते हैं। परिणाम सैद्धांतिक और conditional है, तैनात primitive नहीं, लेकिन proof-theoretic unprovability को क्रिप्टोग्राफ़िक resource की तरह इस्तेमाल करने का नया तरीका दिखाता है।

बिना बढ़ा-चढ़ाकर जाँच

पेपर क्या दिखाता है: Stated मान्यताएँ के तहत NP/SAT के एक-संदेश, no-व्यवस्था, perfectly ध्वनि provers बनाए जा सकते हैं जो किसी भी chosen प्रमाण-प्रणाली के सापेक्ष व्यावहारिक रूप से शून्य-ज्ञान हैं और शास्त्रीय शून्य-ज्ञान के प्रत्येक परीक्षण-योग्य game-based परिणाम को achieve करते हैं।

क्या संभावित लेकिन unconditionally सिद्ध नहीं: कि जरूरी proof-जटिलता और क्रिप्टोग्राफ़िक मान्यताएँ सही हैं। वे गंभीर, well-studied मान्यताएँ हैं—और शोधपत्र दिखाता है कि वे मूलतः आवश्यक भी हैं और sufficient भी—लेकिन फिर भी मान्यताएँ हैं।

यह क्या नहीं दिखाता: No इंटरैक्शन, no सेटअप और पूर्ण साउंडनेस के साथ शास्त्रीय शून्य-ज्ञान; तैनाती-तैयार व्यावहारिक प्रणाली; प्रमाण की deniability या non-reusability; या Gödel incompleteness प्रमेय अपने आप क्रिप्टोग्राफी सुरक्षित करता है।

मुख्य सीमाएँ: गारंटी शून्य-ज्ञान की relaxation है; broadest संस्करण multiple मान्यताएँ पर निर्भर करती है; single-universal-prover दावे partly conjectural हैं; और परिणाम मुख्यतः foundational है।

सामान्य पाठक को कितना भरोसा रखना चाहिए? Definitions स्वीकार करने पर यह महत्वपूर्ण conditional सिद्धांत परिणाम है—इस पर उच्च विश्वास। मान्यताएँ वास्तव में capture करती हैं—मध्यम। Immediate व्यावहारिक तैनाती—कम। सुरक्षित takeaway: शोधपत्र शून्य-ज्ञान impossibilities को तोड़ता नहीं; वह उन हिस्सों के आसपास नया proof-theoretic रास्ता खोजता है जो कई सुरक्षा games में मायने रखते हैं।