शून्य-ज्ञान प्रमाण प्रणालियों की संरचना पर

शून्य-ज्ञान इंटरैक्टिव प्रमाणों की व्यापक अनुप्रयोगिता इन प्रमाणों का क्रिप्टोग्राफिक प्रोटोकॉल में उपप्रथाओं के रूप में उपयोग करने की संभावना से आती है। इस उपयोग के बारे में एक मूल प्रश्न यह है कि क्या (क्रमिक और/या समानांतर) शून्य-ज्ञान प्रोटोकॉल का संयोजन भी शून्य-ज्ञान है। हम शून्य-ज्ञान प्रोटोकॉल के संयोजन की सीमाओं को प्रदर्शित करते हैं, यह साबित करके कि शून्य-ज्ञान की मूल परिभाषा क्रमिक संयोजन के तहत बंद नहीं है; और यह कि शून्य-ज्ञान के मजबूत प्रारूप (जैसे, ब्लैक-बॉक्स अनुकरण) समानांतर निष्पादन के तहत भी बंद नहीं हैं। हम शून्य-ज्ञान प्रमाणों की राउंड जटिलता के लिए निचले सीमाएँ प्रस्तुत करते हैं, जिनका शून्य-ज्ञान प्रोटोकॉल के समानांतरकरण पर महत्वपूर्ण प्रभाव है। हम साबित करते हैं कि तीन-राउंड इंटरैक्टिव प्रमाण और स्थिर-राउंड आर्थर-मरलीन प्रमाण जो ब्लैक-बॉक्स अनुकरण शून्य-ज्ञान होते हैं, केवल BPP में भाषाओं के लिए मौजूद हैं। विशेष रूप से, यह अनुसरण करता है कि पहले इंटरैक्टिव प्रमाण प्रणालियों के "समानांतर संस्करण", जो द्विघात अवशेषता, ग्राफ समरूपता, और NP में किसी भी भाषा के लिए प्रस्तुत किए गए, ब्लैक-बॉक्स अनुकरण शून्य-ज्ञान नहीं हैं, जब तक कि संबंधित भाषाएँ BPP में न हों। क्या ये समानांतर संस्करण शून्य-ज्ञान प्रमाणों का गठन करते हैं, यह शून्य-ज्ञान पर प्रारंभिक कार्यों से उत्पन्न एक दिलचस्प खुला प्रश्न था। अन्य परिणामों में विभिन्न ज्ञात शून्य-ज्ञान प्रोटोकॉल की राउंड जटिलता के लिए आदर्शता का एक प्रमाण और "समानांतरizable" स्थिर-राउंड शून्य-ज्ञान प्रमाणों की डिजाइन में गुप्त सिक्कों के उपयोग की आवश्यकता है।