💻 computer science

Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768 at the Heuristic Failure Scale

यह शोध पत्र एक नवीन ग्राफ-युग्मित विश्लेषण (graph-coupled analysis) और गहन एंटी-कन्सन्ट्रेशन तकनीकों का उपयोग करते हुए, ML-KEM-768 की ईमानदार-डिकैप्सुलेशन विफलता संभावना के लिए $2^{-164.81}$ का एक प्रमाणित ऊपरी स्तर स्थापित करता है, जो योजना के ह्यूरिस्टिक विफलता पैमाने को कठोरता से न्यायसंगत ठहराने के लिए एक डिपेंडेंसी-अवेयर रैंडम-ऑरेकल और सेंटर्ड-बाइनोमियल एब्स्ट्रैक्शन का उपयोग करता है।

मूल लेखक: Aurélie Duriez (netHsys SARL, Lille, France), Christophe Tommasini (Tommasini Conseil, Lille, France)

प्रकाशित 2026-09-10✓ Author reviewed ⓘ

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

CC BY 4.0

मूल लेखक: Aurélie Duriez (netHsys SARL, Lille, France), Christophe Tommasini (Tommasini Conseil, Lille, France)

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

डिजिटल दुनिया में, सुरक्षा अक्सर उन गणितीय समस्याओं पर निर्भर करती है जिन्हें एक दिशा में उपयोग करना आसान है लेकिन सही गुप्त जानकारी के बिना उन्हें उलटना अत्यंत कठिन है। ML-KEM एक पोस्ट-क्वांटम कुंजी-स्थापना तंत्र (key-establishment mechanism) है जिसे भविष्य के क्वांटम कंप्यूटरों के विरुद्ध भी सुरक्षित रहने के लिए डिज़ाइन किया गया है। अन्य लैटिस-आधारित क्रिप्टोग्राफिक प्रणालियों की तरह, इसमें जिसे 'ऑनेस्ट डिकैप्सुलेशन विफलता' (honest decapsulation failure) कहा जाता है, उसकी एक अत्यंत कम संभावना होती है: भले ही दोनों पक्ष सही ढंग से व्यवहार कर रहे हों, सिद्धांत रूप में दोनों पक्ष अलग-अलग कुंजियाँ प्राप्त कर सकते हैं। यह कितनी दुर्लभता से हो सकता है इसका अनुमान लगाना शुद्धता (correctness) का एक महत्वपूर्ण प्रश्न है। पिछले विश्लेषण काफी हद तक विफलता के पैमाने के अनुमानों (heuristic estimates) पर निर्भर रहे हैं, जबकि विभिन्न त्रुटि पदों (error terms) के बीच प्रासंगिक गणितीय निर्भरता को बनाए रखते हुए एक कठोर सीमा (rigorous bound) प्राप्त करना काफी अधिक कठिन है।

ऑरेलिए ड्यूरिएज़ और क्रिस्टोफ टोमासिनी द्वारा किया गया एक नया अध्ययन एक स्पष्ट आदर्श रैंडम-फंक्शन / सेंटर्ड-बाइनोमियल, या ROM/CBD एब्स्ट्रैक्शन के भीतर ML-KEM-768 का एक कठोर गणितीय विश्लेषण विकसित करके इस समस्या का समाधान करता है। यह कार्य कोई सिमुलेशन नहीं है और यह सटीक विफलता दर की गणना करने का प्रयास नहीं करता है। इसके बजाय, लेखक विभिन्न त्रुटि पदों के बीच महत्वपूर्ण निर्भरताओं को बनाए रखते हुए एक ऑनेस्ट डिकैप्सुलेशन विफलता की संभावना पर एक प्रमाणित ऊपरी सीमा (certified upper bound) प्राप्त करते हैं। विशेष रूप से, यह विश्लेषण केवल उन्हें स्वतंत्र मानने के बजाय सार्वजनिक मैट्रिक्स और दोनों सिफरटेक्स्ट-कंप्रेशन पदों द्वारा प्रेरित निर्भरताओं को ट्रैक रखता है। परिणामी प्रमाणित ऊपरी सीमा 2 की घात 164.81 के एक बटे से भी कम है।

यह खोज महत्वपूर्ण है क्योंकि यह अध्ययन किए गए स्पष्ट मॉडल के भीतर एक अनुमानित विफलता-पैमाने के अनुमान को, निर्भरता-जागरूक प्रमाणित ऊपरी सीमा (dependency-aware certified upper bound) से बदल देती है। यह विश्लेषण केवल यह नहीं मानता कि प्रासंगिक त्रुटियाँ स्वतंत्र हैं; यह उनके बीच उत्पन्न होने वाली गणितीय निर्भरताओं को सुरक्षित रखता है। प्रमाणित सीमा पहले के अनुमानों के समान ही पैमाने तक पहुँचती है, लेकिन इसे यह साबित करने के रूप में नहीं समझा जाना चाहिए कि वे अनुमान सटीक विफलता दर हैं। परिणाम जानबूझकर अधिक सीमित है: पेपर में अध्ययन किए गए स्पष्ट ROM/CBD एब्स्ट्रैक्शन के भीतर, एक ऑनेस्ट डिकैप्सुलेशन विफलता की संभावना को कठोरता से एक अत्यंत छोटे मान से ऊपर सीमित किया गया है। पेपर यह भी स्पष्ट करता है कि यह सटीक डिकैप्सुलेशन-विफलता दर नहीं है और न ही यह FIPS 203 के निश्चित SHAKE इंस्टेंशिएशन के बारे में कोई सूचना-सैद्धांतिक (information-theoretic) कथन है।

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

परिणाम घोषित एब्स्ट्रैक्शन के भीतर एक कठोर और पारदर्शी प्रमाणित शुद्धता सीमा (certified correctness bound) है। शोधकर्ताओं ने अपना कोड, डेटा और सहायक आर्टिफैक्ट्स उपलब्ध कराए हैं ताकि गणनाओं की स्वतंत्र रूप से जाँच की जा सके। पुनरुत्पादकता का यह स्तर क्रिप्टोग्राफी में विशेष रूप से महत्वपूर्ण है, जहाँ गणितीय दावों को स्वतंत्र सत्यापन के लिए खुला होना चाहिए। अध्ययन दिखाता है कि, विचार किए गए स्पष्ट ROM/CBD एब्स्ट्रैक्शन के भीतर, एक ऑनेस्ट डिकैप्सुलेशन विफलता की संभावना एक अत्यंत छोटे स्तर पर सीमित है। हालाँकि, इसे ML-KEM-768 के लिए सुरक्षा के सामान्य प्रमाण, मानकीकृत योजना के सभी सुरक्षा गुणों के प्रमाण, या प्रत्येक हार्डवेयर या सॉफ़्टवेयर कार्यान्वयन को कवर करने वाले कथन के रूप में नहीं समझा जाना चाहिए।

यह परिणाम एक स्पष्ट रूप से परिभाषित एब्स्ट्रैक्शन के भीतर निर्भरता-जागरूक प्रमाणित ऊपरी सीमा प्राप्त करके, एक अनुमानित विफलता-पैमाने के अनुमान से आगे बढ़कर ML-KEM-768 की शुद्धता की कठोर समझ को आगे बढ़ाता है। यह दिखाता है कि एक सीमा (bound) को अनुमानित पैमाने पर तब भी स्थापित किया जा सकता है जब प्रासंगिक त्रुटि पदों के बीच महत्वपूर्ण निर्भरताओं को बनाए रखा जाए। संख्या 164.81 इस ऊपरी सीमा का प्रमाणित घातांक (exponent) है: बताए गए ROM/CBD एब्स्ट्रैक्शन के भीतर, ऑनेस्ट-डिकैप्सुलेशन विफलता की संभावना 2 की घात -164.81 से ऊपर सीमित है। इसलिए इस संख्या को ML-KEM-768 की समग्र सुरक्षा या मजबूती के सामान्य माप के बजाय, पेपर में सिद्ध प्रमाणित सीमा के एक सटीक गुण के रूप में समझा जाना चाहिए।

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

अंत में, यह शोध पत्र एक सटीक लेकिन जानबूझकर सीमित परिणाम प्रदान करता है: बताए गए ROM/CBD एब्स्ट्रैक्शन के भीतर, ऑनेस्ट-डिकैप्सुलेशन विफलता की संभावना कठोरता से 2 की घात -164.81 से ऊपर सीमित है। यह एक अत्यंत छोटा प्रमाणित ऊपरी सीमा है, लेकिन यह सटीक विफलता दर नहीं है और यह कोई व्यापक प्रमाण नहीं है कि पूर्ण रूप से तैनात ML-KEM-768 प्रणाली वास्तविक दुनिया की हर स्थिति में बिना विफलता के काम करती है। इसका योगदान एक स्पष्ट रूप से परिभाषित मॉडल के भीतर एक अनुमानित विफलता-पैमाने के अनुमान को निर्भरता-जागरूक, पुनरुत्पादित और स्वतंत्र रूप से जांचने योग्य सीमा से बदलने में निहित है। इसकी ताकत उस मॉडल से परे निश्चितता का दावा करने में नहीं, बल्कि इस बारे में स्पष्ट होने में है कि क्या सिद्ध किया गया है और क्या परिणाम के दायरे से बाहर है।

तकनीकी सारांश: ML-KEM-768 के लिए डिपेंडेंसी-अवेयर (Dependency-Aware) ROM/CBD शुद्धता सीमाएँ

समस्या विवरण
FIPS 203 में मानकीकृत ML-KEM-768 में एक गैर-शून्य प्रायिकता होती है कि एक ईमानदारी से उत्पन्न किया गया सिफरटेक्स्ट (ciphertext) संदेश से भिन्न संदेश को डिक्रिप्ट करता है (एक डिक्रिप्शन विफलता)। जबकि FIPS 203 लगभग $2^{-164.8}$ का एक ह्यूरिस्टिक (heuristic) विफलता पैमाना रिपोर्ट करता है, यह मान उन सरलीकृत मॉडलों पर निर्भर करता है जो अक्सर कंप्रेशन त्रुटियों (compression errors) और लैटिस नॉइज़ (lattice noise) के बीच स्वतंत्रता (independence) को मान लेते हैं। पिछले औपचारिक विश्लेषणों ने या तो काफी कमजोर (जैसे, लगभग $2^{-80}$ ) प्रमाणित शुद्धता सीमाएँ प्रदान की हैं या ह्यूरिस्टिक पैमाने को एक खुले प्रश्न के रूप में माना है जिसके लिए कठोर औचित्य की आवश्यकता है। विशेष रूप से, मौजूदा कठोर विधियाँ अक्सर घटकों के बीच निर्भरता को संभालने के लिए वास्तविक संयुक्त वितरण (joint distribution) को वर्स्ट-केस (worst-case) नियतात्मक लिफाफों (deterministic envelopes) से बदलकर करती हैं, जिसके परिणामस्वरूप ढीली सीमाएँ (जैसे, $2^{-127}$ ) प्राप्त होती हैं। मुख्य चुनौती एक प्रमाणित ऊपरी सीमा प्रदान करना है जो सार्वजनिक मैट्रिक्स और दोनों कंप्रेशन पदों ( $c_u$ और $c_v$ ) द्वारा प्रेरित बीजगणितीय निर्भरताओं (algebraic dependencies) को सुरक्षित रखते हुए ह्यूरिस्टिक विफलता पैमाने तक पहुँचती है।

कार्यप्रणाली (Methodology)
यह शोध पत्र एक स्पष्ट ROM/CBD एब्स्ट्रैक्शन के भीतर कार्य करता है:

रैंडम ऑरेकल मॉडल (ROM): डोमेन-सेपरेटेड पब्लिक-मैट्रिक्स जनरेशन स्ट्रीम को स्वतंत्र यूनिफॉर्म रिंग एलिमेंट्स के रूप में मॉडल किया गया है।
सेंटर्ड बिनोमियल डिस्ट्रीब्यूशन (CBD): सीक्रेट और नॉइज़ पॉलिनोमिअल्स को CBD2 गुणांकों के साथ स्वतंत्र सैंपल्स के रूप में मॉडल किया गया है।
सटीक पूर्णांक मानचित्र (Exact Integer Maps): कंप्रेशन, डीकंप्रेशन और डिकोडिंग ML-KEM-768 पैरामीटर सेट के सटीक ऑडिटेड इंटीजर मैप्स का उपयोग करते हैं, न कि रियल-नंबर अनुमानों का।

प्रूफ रणनीति त्रुटि पदों (error terms) के बीच स्वतंत्रता को मानने से बचती है। इसके बजाय, यह एक डिपेंडेंसी-प्रिजर्विंग ट्रांसपोर्ट (dependency-preserving transport) दृष्टिकोण अपनाती है:

ग्राफ-कपल्ड रेफरेंस (Graph-Coupled Reference): लेखक साझा मैट्रिक्स-निर्भर मात्रा द्वारा प्रेरित $c_u$ और $c_v$ के संयुक्त अवशेष (joint residual) के लिए एक सटीक द्विविचर प्रिमिटिव (bivariate primitive) व्युत्पन्न करते हैं।
फूरियर विश्लेषण (Fourier Analysis): वे स्पेक्ट्रल बाउंड्स से टोटल वेरिएशन डिस्टेंस (total variation distance) तक के स्टेप को स्पष्ट रूप से प्रबंधित करने के लिए एक पार्शियल-फूरियर लेम्मा का उपयोग करते हैं। यह उन्हें "फुल-आइडियल" संदर्भ वितरण (जहाँ त्रुटियाँ स्वतंत्र हैं) को "प्रॉपर-आइडियल" वास्तविक वितरण (जहाँ निर्भरताएँ मौजूद हैं) में बिना निर्भरता संरचना खोए ट्रांसपोर्ट करने की अनुमति देता है।
स्तरीकृत सुधार (Stratified Correction): प्रूफ इफेमेरल वेक्टर $r$ $r$ द्वारा जनरेट किए गए आइडियल के इनएक्टिव CRT फैक्टर्स के आधार पर स्तरीकरण (stratification) को संभालता है।
- $|T|=1$ और $|T|=2$ (एक या दो इनएक्टिव फैक्टर्स) के लिए, सटीक ड्यूल एन्यूमरेटर्स (dual enumerators) और रैशनल स्पेक्ट्रल सर्टिफिकेट का उपयोग किया जाता है।
- $|T| \ge 3$ के लिए, लेखक दुर्लभ स्ट्रेटा (rare strata) की प्रायिकता को बाउंड करने के लिए एक कंस्ट्रक्शन-A लैटिस और Fincke–Pohst एन्यूमरेशन का उपयोग करके एक व्यापक तीन-फैक्टर एंटी-कंसंट्रेशन विश्लेषण नियोजित करते हैं।
बिट-विशिष्ट सीमाएँ (Bit-Specific Bounds): विश्लेषण FIPS डिकोडिंग मैप के लिए सटीक बिट-विशिष्ट सुरक्षित क्षेत्रों के साथ समाप्त होता है, जिसके बाद 256 मैसेज कोएफिशिएंट्स पर एक यूनियन बाउंड लगाया जाता है। इन कोएफिशिएंट्स के बीच किसी भी स्वतंत्रता को नहीं माना गया है।

प्रमुख योगदान

डिपेंडेंसी-प्रिजर्विंग अपर बाउंड: यह शोध पत्र ML-KEM-768 के लिए एक प्रमाणित ऊपरी सीमा प्रदान करता है जो $c_u$ और $c_v$ के बीच बीजगणितीय निर्भरता को बनाए रखता है, न कि उन्हें स्वतंत्र राउंडिंग नॉइज़ या वर्स्ट-केस लिफाफों से बदलता है।
ग्राफ-कपल्ड बाइवेरिएट ट्रांसपोर्ट: लेखक एफाइन आइडियल मिश्रण के माध्यम से फुल-आइडियल संदर्भ को ट्रांसपोर्ट करने के लिए एक ग्राफ-कपल्ड बाइवेरिएट ग्रुप-अल्जेब्रा ट्रांसपोर्ट पेश करते हैं, जो संयुक्त $c_u/c_v$ निर्भरता को हल करता है।
सर्टिफाइड रेयर-स्ट्रटम कंट्रोल: $|T| \ge 3$ शाखा को एक व्यापक तीन-फैक्टर एंटी-कंसंट्रेशन रीप्ले का उपयोग करके बंद किया गया है, जो उन दुर्लभ मामलों के लिए एक प्रमाणित बाउंड प्रदान करता है जहाँ आइडियल संरचना अत्यधिक डिजेनरेट (degenerate) होती है।
सटीक रैशनल सर्टिफिकेट: अंतिम परिणाम एक कम किया गया रैशनल सर्टिफिकेट है जो सटीक इंटीजर तुलनाओं और रैशनल असमानताओं से व्युत्पन्न है, जो निर्णय तर्क (decision logic) के लिए फ्लोटिंग-पॉइंट अनुमानों से बचता है।

परिणाम
यह शोध पत्र दिए गए ROM/CBD एब्स्ट्रैक्शन के भीतर ईमानदार डिकैप्सुलेशन विफलता ( $K' \neq K$ ) की प्रायिकता के लिए निम्नलिखित ऊपरी सीमा स्थापित करता है:
$\Pr[K' \neq K] \le P^* \le 2^{-164.81}$
सटीक प्रमाणित एक्सपोनेंट है $-\log_2 P^* = 164.810716201343121\dots$ ।

थ्रेशोल्ड $164.81$ सटीक है लेकिन संख्यात्मक रूप से टाइट (tight) है; प्रमाणित एक्सपोनेंट इससे केवल $\approx 0.0007162$ बिट्स अधिक है।
$2^{-164.82}$ का मान इस प्रमाण द्वारा प्रमाणित नहीं है।
यह एक ऊपरी सीमा (upper bound) है, न कि सटीक डिक्रिप्शन फेल्योर रेट (DFR)।

महत्व और दावे
लेखक स्पष्ट रूप से बताते हैं कि परिणाम क्या है और क्या नहीं है:

यह क्या है: एक स्पष्ट ROM/CBD एब्स्ट्रैक्शन के भीतर एक डिपेंडेंसी-प्रिजर्विंग प्रमाणित ऊपरी सीमा। यह प्रमाणित शुद्धता (जो अक्सर कमजोर होती है) और ह्यूरिस्टिक अनुमानों के बीच के अंतर को पाटता है, क्योंकि यह उन बीजगणितीय निर्भरताओं को कठोरता से ध्यान में रखता है जिन्हें ह्यूरिस्टिक मॉडल अक्सर अनदेखा कर देते हैं।
यह क्या नहीं है:
- यह FIPS 203 के फिक्स्ड SHAKE इंस्टेंशिएशन के बारे में कोई सूचना-सैद्धांतिक (information-theoretic) कथन नहीं है।
- यह एक सटीक DFR नहीं है।
- यह एक नया IND-CCA रिडक्शन या एडेप्टिव $\delta$ -करेक्टनेस का प्रमाण नहीं है (जहाँ हमलावर सार्वजनिक डेटा देखने के बाद संदेश चुनता है)।
- यह अंतर्निहित उपकरणों (ideals, CRT stratification, Fourier anti-concentration) के लिए प्राथमिकता का दावा नहीं करता है, जो स्थापित पूर्ववर्ती (prior art) हैं।

इसका महत्व इस बात में निहित है कि यह ML-KEM-768 के ह्यूरिस्टिक विफलता पैमाने के लिए एक अच्छी तरह से परिभाषित एब्स्ट्रैक्शन के भीतर पहला कठोर, डिपेंडेंसी-अवेयर औचित्य प्रदान करता है, यह प्रदर्शित करते हुए कि ह्यूरिस्टिक मान केवल स्वतंत्रता को मानने का परिणाम नहीं है, बल्कि तब भी बना रहता है जब निर्भरताओं को संरक्षित किया जाता है, बशर्ते कि सीमा को $2^{-164.81}$ तक थोड़ा कड़ा किया जाए।

इसी तरह के और पेपर