CSIDH: Commutative Supersingular Isogenies

CSIDH (क्रमविनिमेय सुपरसिंगुलर आइसोजेनी डिफी-हेलमैन, Castryck आदि, 2018) एक आइसोजेनी-आधारित कुंजी विनिमय है, जो मूलतः अलग बीजीय संरचना का उपयोग करके SIDH के टॉर्शन-बिंदु सूचना-रिसाव से पूरी तरह बचता है। CSIDH, SIDH की तरह Fp2 के बजाय Fp पर सुपरसिंगुलर वक्रों के साथ काम करता है। इसकी कठिनता धारणा वर्ग समूह क्रिया की क्रमविनिमेयता है: दोनों पक्ष एक साझा प्रारंभिक वक्र पर अलग-अलग गुप्त वर्ग समूह अवयव लागू करते हैं और क्रमविनिमेयता यह सुनिश्चित करती है कि दोनों एक ही साझा वक्र तक पहुँचें। कोई सहायक टॉर्शन-बिंदु सूचना प्रकाशित नहीं की जाती—सार्वजनिक कुंजी केवल एक j-अपरिवर्ती होती है। यह अभिकल्पना SIDH पर हुए Castryck-Decru आक्रमण से सुरक्षित रही।

Fp पर, जहाँ p = 3 mod 4 है, सुपरसिंगुलर वक्र E में एक विशिष्ट एंडोमोर्फिज़्म pi (फ्रॉबेनियस) होता है और उसके एंडोमोर्फिज़्म बीजगणित में काल्पनिक द्विघाती क्रम Z[pi] शामिल होता है। आदर्श वर्ग समूह Cl(Z[pi]) Fp पर मौजूद सुपरसिंगुलर वक्रों के समुच्चय पर (समरूपता तक) मुक्त और संक्रमणात्मक रूप से क्रिया करता है। Cl(Z[pi]) में कोई आदर्श a किसी वक्र E पर क्रिया करके एक नया वक्र a * E उत्पन्न करता है, जिसकी गणना E/E[a] के रूप में की जाती है, जहाँ E[a] आदर्श a के अनुरूप टॉर्शन उपसमूह है। यह क्रिया क्रमविनिमेय है: a * (b * E) = b * (a * E) = [ab] * E। यही CSIDH समूह क्रिया है, जो डिफी-हेलमैन का एक क्रमविनिमेय अनुरूप प्रदान करती है।

CSIDH कुंजी विनिमय इस प्रकार होता है। सार्वजनिक पैरामीटर: Fp पर एक सुपरसिंगुलर वक्र E0 और छोटी विषम अभाज्य संख्याएँ l_1, ..., l_n। गुप्त कुंजियाँ: Alice a = (a_1, ..., a_n) चुनती हैं, जहाँ प्रत्येक a_i {-m, ..., m} में एक यादृच्छिक छोटी पूर्णांक है। Bob b = (b_1, ..., b_n) चुनते हैं। Alice की सार्वजनिक कुंजी: E_A = [l_1^a_1 * ... * l_n^a_n] * E0। Bob की सार्वजनिक कुंजी: E_B = [l_1^b_1 * ... * l_n^b_n] * E0। साझा गुप्त मान: Alice E_B पर अपनी गुप्त घातांक लागू करती हैं; Bob E_A पर अपने घातांक लागू करते हैं। क्रमविनिमेयता यह सुनिश्चित करती है कि दोनों E_AB = [product(l_i^(a_i + b_i))] * E0 प्राप्त करें। साझा गुप्त मान j(E_AB) है। कोई सहायक बिंदु प्रकाशित नहीं किए जाते।

संदर्भ CSIDH कार्यान्वयन में p = 4 * l_1 * l_2 * ... * l_74 - 1 का उपयोग होता है, जहाँ l_1 से l_74 तक पहली 74 विषम अभाज्य संख्याएँ हैं (3, 5, 7, ..., 373)। इससे p लगभग 512 बिट का प्राप्त होता है। प्रत्येक गुप्त कुंजी घटक a_i {-5, ..., 5} में होता है (प्रत्येक घटक के लिए 11 विकल्प, कुल 74 घटक)। वर्ग समूह का क्रम लगभग sqrt(p) होता है और कुंजी-स्थान का आकार 11^74 होता है। प्रत्येक आइसोजेनी चरण की गणना के लिए, प्रत्येक अभाज्य l_i का l_i-टॉर्शन उपसमूह खोजा जाता है और Velu के सूत्रों का उपयोग करके l_i-आइसोजेनी की गणना की जाती है। sqrt-Velu के साथ, प्रत्येक बड़ी अभाज्य आइसोजेनी के चरण में O(sqrt(l_i)) संक्रियाएँ लगती हैं। आधुनिक हार्डवेयर पर CSIDH-512 का कुल कुंजी विनिमय लगभग 1-5 ms में पूरा होता है।

मूल CSIDH स्थिर-समय नहीं है: Velu चरणों की संख्या गुप्त कुंजी के मानों पर निर्भर करती है, जिससे समय-आधारित पार्श्व-चैनलों के माध्यम से सूचना का रिसाव होता है। CTIDH (स्थिर-समय ISOGENY डिफी-हेलमैन, Bernstein आदि, 2021) निश्चित-भार कुंजी प्रारूप और सावधानीपूर्वक अभिकल्पित स्थिर-समय आइसोजेनी गणना का उपयोग करके इस समस्या को ठीक करता है। CTIDH की गुप्त कुंजियाँ उन सदिशों तक सीमित होती हैं जिनमें निरपेक्ष मानों का योग निश्चित होता है (उदाहरण के लिए, sum |a_i| = 130)। गुप्त कुंजी के मानों की परवाह किए बिना आइसोजेनी गणना निश्चित संख्या में चरणों में आगे बढ़ती है; इसमें उन चरणों को भरने के लिए नकली आइसोजेनी गणनाएँ की जाती हैं जहाँ गुप्त घातांक शून्य होता है। CTIDH, CTIDH-512 के समान सुरक्षा प्राप्त करता है और कठोर स्थिर-समय गारंटी देता है, जो एम्बेडेड परिनियोजनों के लिए उपयुक्त हैं।

CSIDH की क्वांटम सुरक्षा जालिका-आधारित योजनाओं की तुलना में अधिक सूक्ष्म है। सर्वोत्तम क्वांटम आक्रमण छिपी हुई शिफ्ट समस्या के लिए Kuperberg के एल्गोरिद्म (2005) का उपयोग करता है, जो वर्ग समूह क्रिया की संरचना को उपघातीय समय L(1/2) = exp(O(sqrt(log p))) में तोड़ देता है। यह sqrt(p) वाले सर्वोत्तम शास्त्रीय आक्रमण से काफी बेहतर है, अर्थात क्वांटम कंप्यूटर शास्त्रीय आक्रमणकारियों की तुलना में CSIDH को काफी कमजोर कर देते हैं। 128-बिट पोस्ट-क्वांटम सुरक्षा के लिए (L(1/2) आक्रमण के विरुद्ध), CSIDH को लगभग 5000-बिट के अभाज्य p की आवश्यकता होती है (CSIDH-5000) — जबकि 128-बिट शास्त्रीय सुरक्षा के लिए 512 बिट पर्याप्त हैं। CSIDH-512 में क्वांटम सुरक्षा केवल अनुमानतः 62–72 बिट है, जो NIST स्तर 1 की आवश्यकताओं से काफी कम है।

CSIDH की सुरक्षा Group Action Inverse Problem (GAIP) पर निर्भर करती है: E_A = a * E0 और E0 दिए जाने पर a ज्ञात कीजिए। ज्ञात सर्वोत्तम एल्गोरिद्म Pohlig-Hellman-जैसे अपचयन को बेबी-स्टेप-जायंट-स्टेप के साथ मिलाता है और शास्त्रीय रूप से O(sqrt(|Cl|)) ~ O(p^{1/4}) समय में चलता है। क्वांटम कठिनता (Kuperberg) CSIDH को LWE-आधारित योजनाओं की तुलना में कम क्वांटम-सुरक्षित बनाती है। LWE का सर्वोत्तम क्वांटम आक्रमण (जालिका सिविंग) अधिक सतर्क सुरक्षा-सीमाएँ प्रदान करता है। CSIDH का लाभ इसका कम आकार है: CSIDH-512 की सार्वजनिक कुंजियाँ 64-बाइट की होती हैं (केवल j-अपरिवर्तक), जबकि ML-KEM-512 की कुंजी 800 बाइट की होती है। सबसे छोटी संभव कुंजियों की आवश्यकता वाले और कम क्वांटम सुरक्षा-सीमाएँ स्वीकार करने वाले अनुप्रयोगों के लिए CSIDH अब भी रुचिकर है।

कई CSIDH रूपांतर इसकी क्वांटम सुरक्षा की सीमाओं को दूर करने का प्रयास करते हैं। BSIDH (B का अर्थ “बेहतर”) बड़े-डिग्री वाले आधार वक्रों और दीर्घवृत्तीय वक्रों के गुणनफलों का उपयोग करता है, ताकि गणना को तेज़ रखते हुए वर्ग समूह का आकार बढ़ाया जा सके। Csurf (सतह पर CSIDH) अतिसुपरसिंगुलर वक्रों के एक अलग समुच्चय के साथ काम करता है, जिससे समूह क्रिया की गणना तेज़ हो जाती है। उच्च-जीनस वाले CSIDH प्रस्ताव Fp पर जीनस-2 वक्रों के जेकोबियन का उपयोग करते हैं, जिससे संभावित रूप से बेहतर क्वांटम सुरक्षा-सीमाओं वाला बड़ा समूह क्रिया-स्थान मिलता है। इनमें से किसी भी रूपांतर को व्यापक रूप से अपनाया नहीं गया है और न ही NIST ने इन पर विचार किया है। इसका एक कारण यह है कि CSIDH रूपांतरों का क्वांटम सुरक्षा विश्लेषण अभी विकसित हो रहा है और जालिका-आधारित योजनाओं की तुलना में कम परिपक्व है।

CSIDH और SIDH में मूलभूत अंतर हैं। क्रमविनिमेयता: CSIDH क्रमविनिमेय समूह क्रिया (वर्ग समूह) का उपयोग करता है; SIDH सहायक टॉर्शन बिंदुओं वाली गैर-संवादात्मक कुंजी विनिमय योजना है, जो क्रमविनिमेय न होने वाली आइसोजेनियों पर आधारित है। आधार क्षेत्र: CSIDH, Fp पर काम करता है; SIDH, Fp2 पर (द्विघाती विस्तार)। सार्वजनिक कुंजी का आकार: CSIDH की कुंजी 64 बाइट की होती है (Fp पर एकल j-अपरिवर्तक); SIDH की कुंजी 324 से अधिक बाइट की होती है (एक वक्र और दो Fp2 बिंदु)। सुरक्षा: CSIDH Castryck-Decru आक्रमण से बच गया; SIDH को तोड़ दिया गया। क्वांटम सुरक्षा: 128-बिट क्वांटम सुरक्षा के लिए CSIDH को 5000-बिट अभाज्यों की आवश्यकता होती है; शास्त्रीय रूप से तोड़े जाने से पहले SIDH में तुलनीय क्वांटम प्रतिरोध था। प्रदर्शन: CSIDH-512 में लगभग 1–5 ms लगते हैं; SIDH भी लगभग इतना ही तेज़ था, लेकिन CSIDH-5000 बहुत धीमा होगा।

CSIDH की क्रमविनिमेयता गैर-संवादात्मक कुंजी विनिमय (NIKE) संभव बनाती है: Alice, E_A = a * E0 प्रकाशित करती है; Bob, E_B = b * E0 प्रकाशित करता है। बाद में, किसी भी अतिरिक्त संचार के बिना, कोई भी व्यक्ति किसी भी सार्वजनिक कुंजी से साझा गुप्त मान की गणना कर सकता है: Alice, a * E_B = a * (b * E0) = ab * E0 की गणना करती है; Bob, b * E_A = b * (a * E0) = ab * E0 की गणना करता है। यह NIKE गुण उन अनुप्रयोगों के लिए उपयोगी है जहाँ संवादात्मक कुंजी विनिमय व्यावहारिक नहीं होता — उदाहरण के लिए, ईमेल कूटलेखन, जहाँ प्रेषक और प्राप्तकर्ता एक ही समय पर ऑनलाइन नहीं होते। CSIDH से प्राप्त NIKE, Diffie-Hellman NIKE के समान है, लेकिन पोस्ट-क्वांटम है। LWE पर आधारित ML-KEM अतिरिक्त प्रोटोकॉल अभिकल्पना के बिना स्वाभाविक रूप से NIKE का समर्थन नहीं करता।

CSIDH का मानकीकरण नहीं हुआ है और इसे अभी तक उत्पादन प्रणालियों में तैनात नहीं किया गया है। यह सक्रिय अनुसंधान का विषय है और इसके कार्यान्वयन उपलब्ध हैं: CTIDH (नियत-समय), csidh-reference (शिक्षण के लिए Python), और supersingular-isogeny-toolbox (अनुकूलित C)। परिनियोजन की मुख्य बाधा क्वांटम सुरक्षा है: CSIDH-512 की अनुमानित 62–72 बिट क्वांटम सुरक्षा NIST स्तर 1 (128 बिट) से कम है, इसलिए यह NIST अनुपालन की आवश्यकता वाले पोस्ट-क्वांटम अनुप्रयोगों के लिए उपयुक्त नहीं है। CSIDH-5000 सुरक्षा मानक पूरा करेगा, लेकिन बहुत अधिक धीमा होगा। क्वांटम सुरक्षा विश्लेषण में सुधार और इस अंतर को पाटने वाले रूपांतरों पर अनुसंधान जारी है, लेकिन 2024 तक CSIDH परिनियोजन के लिए तैयार क्रिप्टोग्राफ़िक आदिम के बजाय एक अनुसंधान प्रोटोटाइप बना हुआ है।

CSIDH, Fp पर अतिसुपरसिंगुलर वक्रों पर Cl(Z[pi]) की क्रमविनिमेय वर्ग समूह क्रिया का उपयोग करता है, जहाँ pi फ्रॉबेनियस एंडोमोर्फ़िज़्म है। सार्वजनिक कुंजियाँ एकल j-अपरिवर्तक होती हैं (64 बाइट)। कोई सहायक टॉर्शन बिंदु प्रकाशित नहीं किए जाते, जिससे SIDH की भेद्यता से बचा जाता है। वर्ग समूह क्रिया क्रमविनिमेय है, इसलिए NIKE संभव होता है। सर्वोत्तम शास्त्रीय आक्रमण O(p^{1/4}) का है; सर्वोत्तम क्वांटम आक्रमण (Kuperberg) उपघातीय L(1/2) समय में चलता है, इसलिए 128-बिट क्वांटम सुरक्षा के लिए 5000-बिट अभाज्यों की आवश्यकता होती है। CTIDH नियत-समय कार्यान्वयन प्रदान करता है। CSIDH-512 में केवल लगभग 65 बिट क्वांटम सुरक्षा है। CSIDH का मानकीकरण नहीं हुआ है; अनुसंधान का केंद्र सघन कुंजियों को बनाए रखते हुए क्वांटम प्रतिरोध में सुधार करने वाले रूपांतर हैं।