2025-11-16T14:22:13.039505

MPCitH-based Signatures from Restricted Decoding Problems

Battagliola, Bitzer, Wachter-Zeh et al.
Threshold-Computation-in-the-Head (TCitH) and VOLE-in-the-Head (VOLEitH), two recent developments of the MPC-in-the-Head (MPCitH) paradigm, have significantly improved the performance of digital signature schemes in this framework. In this note, we embed the restricted decoding problem within these frameworks. We propose a structurally simple modeling that achieves competitive signature sizes. Specifically, by instantiating the restricted decoding problem with the same hardness assumption underlying CROSS, we reduce sizes by more than a factor of two compared to the NIST submission. Moreover, we observe that ternary full-weight decoding, closely related to the hardness assumption underlying WAVE, is a restricted decoding problem. Using ternary full-weight decoding, we obtain signature sizes comparable to the smallest MPCitH-based candidates in the NIST competition.
academic

प्रतिबंधित डिकोडिंग समस्याओं से MPCitH-आधारित हस्ताक्षर

मूल जानकारी

  • पेपर ID: 2510.11224
  • शीर्षक: प्रतिबंधित डिकोडिंग समस्याओं से MPCitH-आधारित हस्ताक्षर
  • लेखक: Michele Battagliola (University Polytechnic of Marche), Sebastian Bitzer, Antonia Wachter-Zeh, Violetta Weger (Technical University of Munich)
  • वर्गीकरण: cs.CR (क्रिप्टोग्राफी और सुरक्षा), cs.IT (सूचना सिद्धांत), math.IT (सूचना सिद्धांत)
  • प्रकाशन तिथि: 13 अक्टूबर 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2510.11224

सारांश

यह पेपर प्रतिबंधित डिकोडिंग समस्या (E-SDP) को Threshold-Computation-in-the-Head (TCitH) और VOLE-in-the-Head (VOLEitH) ढांचे में एम्बेड करता है, जो MPC-in-the-Head (MPCitH) प्रतिमान के नवीनतम विकास हैं, जो डिजिटल हस्ताक्षर योजनाओं के प्रदर्शन में महत्वपूर्ण सुधार लाते हैं। लेखकों ने एक संरचनात्मक रूप से सरल मॉडलिंग विधि प्रस्तावित की है, जो प्रतिस्पर्धी हस्ताक्षर आकार को प्राप्त करती है। CROSS के समान कठिनाई धारणा उदाहरण का उपयोग करके प्रतिबंधित डिकोडिंग समस्या को तत्काल करने से, हस्ताक्षर आकार NIST प्रस्तुति संस्करण की तुलना में दो गुना से अधिक कम हो जाता है। इसके अलावा, लेखकों ने पाया कि त्रिमान पूर्ण-वजन डिकोडिंग WAVE अंतर्निहित कठिनाई धारणा से घनिष्ठ रूप से संबंधित है, इस विधि का उपयोग करके प्राप्त हस्ताक्षर आकार NIST प्रतियोगिता में सबसे छोटे MPCitH उम्मीदवार योजनाओं के साथ तुलनीय है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

  1. पोस्ट-क्वांटम क्रिप्टोग्राफी मानकीकरण की आवश्यकता: CRYSTALS-Dilithium, FALCON और SPHINCS+ को मानकीकृत करने के बाद, NIST ने सितंबर 2022 में अतिरिक्त डिजिटल हस्ताक्षर योजनाओं के संग्रह की शुरुआत की, जिसका उद्देश्य पोस्ट-क्वांटम हस्ताक्षर मानक संयोजन में विविधता लाना है।
  2. MPCitH प्रतिमान का विकास: 2007 में Ishai और अन्य द्वारा प्रस्तावित होने के बाद से, MPCitH तकनीक ने पोस्ट-क्वांटम डिजिटल हस्ताक्षर के परिदृश्य को पुनर्निर्मित किया है। TCitH और VOLEitH, MPCitH के नवीनतम विशेषज्ञता के रूप में, पिछली संरचनाओं की तुलना में महत्वपूर्ण प्रदर्शन सुधार प्रदान करते हैं।
  3. क्रिप्टोग्राफी में कोडिंग सिद्धांत का अनुप्रयोग: कोडिंग सिद्धांत पर आधारित कठिनाई समस्याएं (जैसे हैमिंग मेट्रिक और रैंक मेट्रिक डिकोडिंग समस्याएं) उच्च-दक्ष पोस्ट-क्वांटम हस्ताक्षर बनाने के लिए सैद्धांतिक आधार प्रदान करती हैं।

अनुसंधान प्रेरणा

  1. प्रदर्शन अनुकूलन की आवश्यकता: मौजूदा CROSS हस्ताक्षर योजना, हालांकि प्रतिबंधित डिकोडिंग समस्या पर आधारित है, अपेक्षाकृत सरल CVE प्रोटोकॉल का उपयोग करती है, हस्ताक्षर आकार के संदर्भ में अनुकूलन की गुंजाइश है।
  2. ढांचा एकीकरण: प्रतिबंधित डिकोडिंग समस्या को उन्नत TCitH/VOLEitH ढांचे में एकीकृत करना, इन ढांचों के प्रदर्शन लाभों का पूरी तरह से उपयोग करने के लिए।
  3. प्रतिस्पर्धिता में वृद्धि: सुरक्षा को बनाए रखते हुए, हस्ताक्षर आकार में महत्वपूर्ण कमी, NIST प्रतियोगिता में प्रतिस्पर्धिता में सुधार।

मुख्य योगदान

  1. E-SDP की बहुपद मॉडलिंग विधि प्रस्तावित की: एक संरचनात्मक रूप से सरल लेकिन प्रभावी बहुपद संबंध डिजाइन किया, जो प्रतिबंधित सिंड्रोम डिकोडिंग समस्या को TCitH और VOLEitH ढांचे में एम्बेड करता है।
  2. CROSS-प्रकार हस्ताक्षर के आकार में महत्वपूर्ण कमी: समान डिकोडिंग समस्या के लिए, NIST प्रस्तुत CROSS योजना की तुलना में, हस्ताक्षर आकार 50% से अधिक कम (12.4kB से 5.5kB तक)।
  3. त्रिमान पूर्ण-वजन डिकोडिंग के अनुप्रयोग संभावना की खोज: साबित किया कि WAVE से संबंधित त्रिमान पूर्ण-वजन डिकोडिंग एक प्रतिबंधित डिकोडिंग समस्या है, और सबसे छोटी MPCitH उम्मीदवार योजनाओं के बराबर हस्ताक्षर आकार (3.1kB) प्राप्त किया।
  4. संपूर्ण पैरामीटरीकरण योजना प्रदान की: NIST सुरक्षा श्रेणी 1, 3, 5 के लिए विशिष्ट पैरामीटर विकल्प और प्रदर्शन विश्लेषण दिया।

विधि विवरण

कार्य परिभाषा

अनुसंधान लक्ष्य प्रतिबंधित सिंड्रोम डिकोडिंग समस्या (E-SDP) को बहुपद संबंध के रूप में प्रस्तुत करना है, ताकि यह TCitH और VOLEitH ढांचे में डिजिटल हस्ताक्षर योजना बना सके।

E-SDP परिभाषा: प्रतिबंधित सेट E ⊂ F, जांच मैट्रिक्स H ∈ F^(r×n) और सिंड्रोम s ∈ F^r दिए गए, e ∈ E^n खोजें जैसे कि eH^T = s।

मुख्य मॉडलिंग विधि

1. बहुपद बाधा निर्माण

प्रणालीगत रूप के जांच मैट्रिक्स H = (A, I_r) के लिए, जहां A ∈ F^(r×k), I_r इकाई मैट्रिक्स है:

  • साक्षी वेक्टर: w ∈ F^k (आंशिक त्रुटि वेक्टर)
  • विस्तारित त्रुटि वेक्टर: e = (w, s - wA^T)
  • प्रतिबंधित बहुपद: f_E(x) = ∏_{e∈E}(x - e)

बहुपद संबंध प्रणाली:

F(x) = (f_1, ..., f_n) ∈ F[x_1, ..., x_k]^n

जहां:

  • f_i(x) = f_E(x_i) for i ∈ k
  • f_{k+i}(x) = f_E(s_i - ⟨a_i, x⟩) for i ∈ r

2. डिग्री विश्लेषण

प्रस्ताव 1: यह बहुपद संबंध E-SDP की डिग्री z = |E| की मॉडलिंग प्रदान करता है, यदि w ∈ F^k F(w) = 0 को संतुष्ट करता है, तो त्रुटि वेक्टर e = (w, s - wA^T) E-SDP उदाहरण (H, s) को हल करता है।

विशिष्ट तत्काल

CROSS-SDP

  • प्रतिबंधित सेट: E = {2^i | i ∈ 7} ⊆ F_{127}
  • पैरामीटर: |E| = 7, p = 127
  • सुरक्षा: 7,15 के विस्तृत विश्लेषण पर आधारित

Ternary-SDP

  • प्रतिबंधित सेट: E = {1, 2} ⊆ F_3
  • पैरामीटर: |E| = 2, p = 3
  • जटिलता: O(2^{0.247·n}) संचालन (बहुपद कारक के भीतर)

प्रायोगिक सेटअप

पैरामीटर चयन रणनीति

सुरक्षा आवश्यकताओं और प्रदर्शन अनुकूलन उद्देश्यों के अनुसार, निम्नलिखित मुख्य पैरामीटर चुनें:

  1. TCitH ढांचा पैरामीटर:
    • τ: समानांतर पुनरावृत्ति संख्या
    • N: मूल्यांकन डोमेन आकार
    • μ: विस्तार क्षेत्र डिग्री K : F
    • η: बैच प्रसंस्करण पैरामीटर
  2. VOLEitH ढांचा पैरामीटर:
    • ρ: विस्तार क्षेत्र पैरामीटर
    • B: सामंजस्य जांच पैरामीटर
    • T_open: VC योजना पैरामीटर

सुरक्षा बाधाएं

निम्नलिखित सुरक्षा आवश्यकताओं को संतुष्ट करें:

  • TCitH: N ≤ p^μ, p^{μ·η} ≥ 2^λ, (N/d)^τ ≥ 2^{λ-w}
  • VOLEitH: N^τ/d ≥ 2^{λ-w}, p^ρ ≥ 2^λ

मूल्यांकन संकेतक

मुख्य रूप से हस्ताक्षर आकार का मूल्यांकन करें, जिसमें तीन घटक शामिल हैं:

  • |σ_sym|: VC योजना संबंधित
  • |σ_w|: साक्षी संबंधित
  • |σ_F|: OWF संबंधित

प्रायोगिक परिणाम

मुख्य परिणाम

TCitH ढांचा प्रदर्शन

| सुरक्षा स्तर | E-SDP प्रकार | |F| | |E| | n | k | τ | N | μ | η | हस्ताक्षर आकार(B) | |---------|-----------|-----|-----|---|---|---|---|---|---|-----------| | NIST 1 | CROSS-SDP | 127 | 7 |127| 76| 15|2048| 2| 10| 5,533 | | NIST 1 | Ternary-SDP| 3 | 2 |579|213| 12|2048| 7| 12| 3,095 | | NIST 3 | CROSS-SDP | 127 | 7 |187|111| 23|2048| 2| 14| 12,354 | | NIST 3 | Ternary-SDP| 3 | 2 |839|309| 18|2048| 7| 18| 6,860 |

VOLEitH ढांचा प्रदर्शन

सुरक्षा स्तरE-SDP प्रकारहस्ताक्षर आकार(B)TCitH की तुलना में सुधार
NIST 1CROSS-SDP4,372~21%
NIST 1Ternary-SDP2,974~4%
NIST 3CROSS-SDP9,361~24%
NIST 3Ternary-SDP6,463~6%

NIST उम्मीदवार योजनाओं के साथ तुलना

योजनाकठिनाई धारणाडिजाइन सिद्धांतहस्ताक्षर आकार(kB)
यह कार्य(CROSS-SDP)प्रतिबंधित डिकोडिंगVOLEitH4.4
यह कार्य(Ternary-SDP)प्रतिबंधित डिकोडिंगTCitH3.1
CROSSCROSS-E-SDPCVE12.4
SDitHसिंड्रोम डिकोडिंगVOLEitH3.7
MQOMबहुचर द्विघातTCitH2.8
PERKक्रमचय कर्नल समस्याVOLEitH3.5

मुख्य निष्कर्ष

  1. आकार में महत्वपूर्ण कमी: CROSS-SDP मूल CROSS की तुलना में हस्ताक्षर आकार में 64.5% की कमी
  2. ढांचा चयन का प्रभाव: उच्च डिग्री समस्याओं के लिए, VOLEitH TCitH से अधिक लाभप्रद है
  3. प्रतिस्पर्धिता: Ternary-SDP सर्वश्रेष्ठ MPCitH उम्मीदवार योजनाओं के बराबर प्रदर्शन प्राप्त करता है

संबंधित कार्य

MPCitH प्रतिमान विकास

  1. मूल MPCitH 23: 2007 में प्रस्तावित, सुरक्षित बहु-पक्षीय संगणना और Fiat-Shamir रूपांतरण को जोड़ता है
  2. TCitH ढांचा 21: ℓ-out-of-n थ्रेसहोल्ड गुप्त साझाकरण का उपयोग करके तत्काल
  3. VOLEitH ढांचा 13: VOLE-आधारित शून्य-ज्ञान प्रोटोकॉल को सार्वजनिक रूप से सत्यापन योग्य प्रोटोकॉल में संकलित करता है

कोडिंग सिद्धांत अनुप्रयोग

  1. हैमिंग मेट्रिक डिकोडिंग: SDitH आदि योजनाओं का आधार
  2. रैंक मेट्रिक डिकोडिंग: RYDE, Mirath आदि योजनाएं
  3. क्रमचय कर्नल समस्या: PERK योजना की कठिनाई धारणा

प्रतिबंधित डिकोडिंग समस्या

  1. CROSS योजना 6: सरल CVE प्रोटोकॉल का उपयोग करके प्रतिबंधित डिकोडिंग
  2. WAVE योजना 10,19: त्रिमान उच्च-वजन सिंड्रोम डिकोडिंग पर आधारित
  3. सैद्धांतिक विश्लेषण 8,9: E-SDP की NP-पूर्णता और ठोस कठिनाई

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. सफल ढांचा एकीकरण: साबित किया कि प्रतिबंधित डिकोडिंग समस्या को उन्नत MPCitH ढांचे में प्रभावी ढंग से एकीकृत किया जा सकता है
  2. महत्वपूर्ण प्रदर्शन सुधार: सरल CVE प्रोटोकॉल को TCitH/VOलेitH से प्रतिस्थापित करके, हस्ताक्षर आकार में बड़ी कमी
  3. व्यापक प्रयोज्यता: यह विधि विभिन्न प्रकार की प्रतिबंधित डिकोडिंग समस्याओं पर लागू होती है

सीमाएं

  1. जटिलता में वृद्धि: मूल CROSS की सरल CVE प्रोटोकॉल की तुलना में, TCitH/VOLEitH निर्माण काफी अधिक जटिल है
  2. कम्प्यूटेशनल ओवरहेड: हालांकि हस्ताक्षर आकार कम हो जाता है, लेकिन हस्ताक्षर पीढ़ी और सत्यापन की कम्प्यूटेशनल जटिलता बढ़ सकती है
  3. पैरामीटर निर्भरता: प्रदर्शन विशिष्ट पैरामीटर चयन और अनुकूलन रणनीति पर अत्यधिक निर्भर है

भविष्य की दिशाएं

  1. आगे अनुकूलन: अधिक कुशल बहुपद मॉडलिंग विधियों की खोज
  2. अन्य प्रतिबंधित समस्याएं: इस विधि को अन्य प्रकार की प्रतिबंधित डिकोडिंग समस्याओं तक विस्तारित करना
  3. कार्यान्वयन अनुकूलन: कम्प्यूटेशनल ओवरहेड को कम करने के लिए कुशल कार्यान्वयन विकसित करना

गहन मूल्यांकन

लाभ

  1. तकनीकी नवाचार: प्रतिबंधित डिकोडिंग समस्या की सरल और प्रभावी बहुपद मॉडलिंग विधि प्रस्तावित की
  2. महत्वपूर्ण सुधार: समान सुरक्षा बनाए रखते हुए, हस्ताक्षर आकार में बड़ी कमी
  3. सैद्धांतिक योगदान: प्रतिबंधित डिकोडिंग समस्या और उन्नत MPCitH ढांचे के बीच पुल स्थापित किया
  4. व्यावहारिक मूल्य: पोस्ट-क्वांटम हस्ताक्षर योजनाओं के लिए नए डिजाइन विचार प्रदान करता है

कमियां

  1. जटिलता व्यापार: हस्ताक्षर आकार में कमी के बदले निर्माण जटिलता में वृद्धि
  2. सीमित नवीनता: मुख्य रूप से मौजूदा तकनीकों का चतुर संयोजन, सैद्धांतिक नवाचार अपेक्षाकृत सीमित
  3. कार्यान्वयन विवरण की कमी: विस्तृत प्रदर्शन विश्लेषण और वास्तविक कार्यान्वयन की तुलना की कमी

प्रभाव

  1. शैक्षणिक मूल्य: MPCitH ढांचे के अनुप्रयोग के लिए नया केस स्टडी प्रदान करता है
  2. व्यावहारिक महत्व: भविष्य की NIST मानकीकरण प्रक्रिया में योजना चयन को प्रभावित कर सकता है
  3. पद्धति योगदान: अन्य कठिनाई समस्याओं के समान मॉडलिंग के लिए संदर्भ प्रदान करता है

प्रयोज्य परिदृश्य

  1. संसाधन-सीमित वातावरण: हस्ताक्षर आकार-संवेदनशील अनुप्रयोग परिदृश्य
  2. पोस्ट-क्वांटम क्रिप्टोग्राफी परिनियोजन: विविध सुरक्षा धारणाओं की आवश्यकता वाली प्रणालियां
  3. अनुसंधान प्रोटोटाइप: आगे अनुकूलन और सुधार के लिए आधार के रूप में

संदर्भ

पेपर 24 महत्वपूर्ण संदर्भों का हवाला देता है, जिसमें MPCitH ढांचा विकास, कोडिंग सिद्धांत अनुप्रयोग, और संबंधित NIST उम्मीदवार योजनाएं शामिल हैं, जो अनुसंधान के लिए एक मजबूत सैद्धांतिक आधार प्रदान करते हैं।