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-ভিত্তিক স্বাক্ষর

মৌলিক তথ্য

পেপার আইডি: 2510.11224
শিরোনাম: MPCitH-based Signatures from Restricted Decoding Problems
লেখক: Michele Battagliola (University Polytechnic of Marche), Sebastian Bitzer, Antonia Wachter-Zeh, Violetta Weger (Technical University of Munich)
শ্রেণীবিভাগ: cs.CR (ক্রিপ্টোগ্রাফি এবং নিরাপত্তা), cs.IT (তথ্য তত্ত্ব), math.IT (তথ্য তত্ত্ব)
প্রকাশনার সময়: ২০২৫ সালের ১৩ অক্টোবর (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 প্রার্থী স্কিমগুলির সাথে তুলনীয়।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার পটভূমি

পোস্ট-কোয়ান্টাম ক্রিপ্টোগ্রাফি স্ট্যান্ডার্ডাইজেশনের প্রয়োজন: CRYSTALS-Dilithium, FALCON এবং SPHINCS+ স্ট্যান্ডার্ডাইজ করার পর, NIST ২০২২ সালের সেপ্টেম্বরে অতিরিক্ত ডিজিটাল স্বাক্ষর স্কিমের জন্য একটি আহ্বান চালু করেছিল, যার লক্ষ্য পোস্ট-কোয়ান্টাম স্বাক্ষর মান সমন্বয়কে বৈচিত্র্যময় করা।
MPCitH প্যারাডাইমের বিকাশ: ২০০৭ সালে Ishai এবং অন্যদের দ্বারা প্রস্তাবিত হওয়ার পর থেকে, MPCitH প্রযুক্তি পোস্ট-কোয়ান্টাম ডিজিটাল স্বাক্ষরের ল্যান্ডস্কেপ পুনর্নির্ধারণ করেছে। TCitH এবং VOLEitH, MPCitH-এর সর্বশেষ বিশেষায়ন, পূর্ববর্তী নির্মাণের তুলনায় উল্লেখযোগ্য কর্মক্ষমতা উন্নতি প্রদান করে।
ক্রিপ্টোগ্রাফিতে কোডিং তত্ত্বের প্রয়োগ: কোডিং তত্ত্বের উপর ভিত্তি করে কঠিন সমস্যা (যেমন হ্যামিং মেট্রিক এবং র্যাঙ্ক মেট্রিক ডিকোডিং সমস্যা) দক্ষ পোস্ট-কোয়ান্টাম স্বাক্ষর নির্মাণের জন্য তাত্ত্বিক ভিত্তি প্রদান করে।

গবেষণা প্রেরণা

কর্মক্ষমতা অপ্টিমাইজেশনের প্রয়োজন: বিদ্যমান CROSS স্বাক্ষর স্কিম যদিও সীমাবদ্ধ ডিকোডিং সমস্যার উপর ভিত্তি করে, তবে তুলনামূলকভাবে সহজ CVE প্রোটোকল ব্যবহার করে, স্বাক্ষর আকারের ক্ষেত্রে অপ্টিমাইজেশনের জায়গা রয়েছে।
কাঠামো একীকরণ: সীমাবদ্ধ ডিকোডিং সমস্যাগুলিকে উন্নত TCitH/VOLEitH কাঠামোতে একীভূত করা, এই কাঠামোগুলির কর্মক্ষমতা সুবিধাগুলি সম্পূর্ণভাবে কাজে লাগানোর জন্য।
প্রতিযোগিতামূলকতা বৃদ্ধি: নিরাপত্তা বজায় রেখে স্বাক্ষর আকার উল্লেখযোগ্যভাবে হ্রাস করা, NIST প্রতিযোগিতায় প্রতিযোগিতামূলকতা বৃদ্ধি করা।

মূল অবদান

E-SDP-এর বহুপদী মডেলিং পদ্ধতি প্রস্তাব: একটি কাঠামোগতভাবে সহজ কিন্তু কার্যকর বহুপদী সম্পর্ক ডিজাইন করা হয়েছে যা সীমাবদ্ধ সিন্ড্রোম ডিকোডিং সমস্যাকে TCitH এবং VOLEitH কাঠামোতে এম্বেড করে।
CROSS-প্রকার স্বাক্ষরের আকার উল্লেখযোগ্যভাবে হ্রাস: একই ডিকোডিং সমস্যার জন্য, NIST-এ জমা দেওয়া CROSS স্কিমের তুলনায় স্বাক্ষর আকার ৫০% এর বেশি হ্রাস পায় (১২.৪kB থেকে ৫.৫kB পর্যন্ত)।
ত্রিমুখী সম্পূর্ণ-ওজন ডিকোডিংয়ের প্রয়োগ সম্ভাবনা আবিষ্কার: প্রমাণ করা হয়েছে যে WAVE-এর সাথে সম্পর্কিত ত্রিমুখী সম্পূর্ণ-ওজন ডিকোডিং একটি সীমাবদ্ধ ডিকোডিং সমস্যা, এবং ক্ষুদ্রতম MPCitH প্রার্থী স্কিমের সাথে তুলনীয় স্বাক্ষর আকার (৩.১kB) অর্জন করা হয়েছে।
সম্পূর্ণ প্যারামিটারাইজেশন স্কিম প্রদান: NIST নিরাপত্তা বিভাগ ১, ৩, ৫-এর জন্য নির্দিষ্ট প্যারামিটার পছন্দ এবং কর্মক্ষমতা বিশ্লেষণ প্রদান করা হয়েছে।

পদ্ধতির বিস্তারিত বর্ণনা

কাজের সংজ্ঞা

গবেষণার লক্ষ্য হল সীমাবদ্ধ সিন্ড্রোম ডিকোডিং সমস্যা (E-SDP) কে বহুপদী সম্পর্ক হিসাবে প্রকাশ করা, যাতে এটি TCitH এবং VOLEitH কাঠামোতে ডিজিটাল স্বাক্ষর স্কিম নির্মাণ করতে পারে।

E-SDP সংজ্ঞা: সীমাবদ্ধ সেট E ⊂ F, পরীক্ষা ম্যাট্রিক্স H ∈ F^(r×n) এবং সিন্ড্রোম s ∈ F^r দেওয়া, e ∈ E^n খুঁজে বের করুন যাতে eH^T = s।

মূল মডেলিং পদ্ধতি

১. বহুপদী সীমাবদ্ধতা নির্মাণ

সিস্টেম ফর্মের পরীক্ষা ম্যাট্রিক্স 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

২. ডিগ্রি বিশ্লেষণ

প্রস্তাব ১: এই বহুপদী সম্পর্ক 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}) অপারেশন (বহুপদী ফ্যাক্টরের মধ্যে)

পরীক্ষামূলক সেটআপ

প্যারামিটার নির্বাচন কৌশল

নিরাপত্তার প্রয়োজনীয়তা এবং কর্মক্ষমতা অপ্টিমাইজেশনের লক্ষ্য অনুযায়ী, নিম্নলিখিত মূল প্যারামিটারগুলি নির্বাচন করা হয়েছে:

TCitH কাঠামো প্যারামিটার:
- τ: সমান্তরাল পুনরাবৃত্তির সংখ্যা
- N: মূল্যায়ন ডোমেইনের আকার
- μ: সম্প্রসারণ ক্ষেত্রের ডিগ্রি K : F
- η: ব্যাচ প্রসেসিং প্যারামিটার
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 1	CROSS-SDP	4,372	~21%
NIST 1	Ternary-SDP	2,974	~4%
NIST 3	CROSS-SDP	9,361	~24%
NIST 3	Ternary-SDP	6,463	~6%

NIST প্রার্থী স্কিমের সাথে তুলনা

স্কিম	কঠিনতার অনুমান	ডিজাইন নীতি	স্বাক্ষর আকার(kB)
এই কাজ (CROSS-SDP)	সীমাবদ্ধ ডিকোডিং	VOLEitH	4.4
এই কাজ (Ternary-SDP)	সীমাবদ্ধ ডিকোডিং	TCitH	3.1
CROSS	CROSS-E-SDP	CVE	12.4
SDitH	সিন্ড্রোম ডিকোডিং	VOLEitH	3.7
MQOM	বহুপদী দ্বিঘাত	TCitH	2.8
PERK	পারমুটেশন কার্নেল সমস্যা	VOLEitH	3.5

মূল আবিষ্কার

উল্লেখযোগ্য আকার হ্রাস: CROSS-SDP মূল CROSS-এর তুলনায় ৬৪.৫% স্বাক্ষর আকার হ্রাস করে
কাঠামো নির্বাচনের প্রভাব: উচ্চ ডিগ্রির সমস্যার জন্য, VOLEitH TCitH-এর চেয়ে বেশি সুবিধাজনক
প্রতিযোগিতামূলকতা: Ternary-SDP সর্বোত্তম MPCitH প্রার্থী স্কিমের সাথে তুলনীয় কর্মক্ষমতা অর্জন করে

উপসংহার এবং আলোচনা

প্রধান উপসংহার

সফল কাঠামো একীকরণ: প্রমাণ করা হয়েছে যে সীমাবদ্ধ ডিকোডিং সমস্যা উন্নত MPCitH কাঠামোতে কার্যকরভাবে একীভূত করা যায়
উল্লেখযোগ্য কর্মক্ষমতা উন্নতি: সহজ CVE প্রোটোকলকে TCitH/VOLEitH দিয়ে প্রতিস্থাপন করে, স্বাক্ষর আকার উল্লেখযোগ্যভাবে হ্রাস পায়
বিস্তৃত প্রযোজ্যতা: এই পদ্ধতি বিভিন্ন ধরনের সীমাবদ্ধ ডিকোডিং সমস্যার জন্য প্রযোজ্য

সীমাবদ্ধতা

জটিলতা বৃদ্ধি: মূল CROSS-এর সহজ CVE প্রোটোকলের তুলনায়, TCitH/VOLEitH নির্মাণ উল্লেখযোগ্যভাবে আরও জটিল
গণনা ওভারহেড: যদিও স্বাক্ষর আকার হ্রাস পায়, তবে স্বাক্ষর প্রজন্ম এবং যাচাইকরণের গণনা জটিলতা বৃদ্ধি পেতে পারে
প্যারামিটার নির্ভরতা: কর্মক্ষমতা নির্দিষ্ট প্যারামিটার পছন্দ এবং অপ্টিমাইজেশন কৌশলের উপর অত্যন্ত নির্ভরশীল

ভবিষ্যত দিকনির্দেশনা

আরও অপ্টিমাইজেশন: আরও দক্ষ বহুপদী মডেলিং পদ্ধতি অন্বেষণ করা
অন্যান্য সীমাবদ্ধ সমস্যা: এই পদ্ধতিকে অন্যান্য ধরনের সীমাবদ্ধ ডিকোডিং সমস্যায় প্রসারিত করা
বাস্তবায়ন অপ্টিমাইজেশন: গণনা ওভারহেড হ্রাস করতে দক্ষ বাস্তবায়ন বিকাশ করা

গভীর মূল্যায়ন

শক্তি

প্রযুক্তিগত উদ্ভাবন: সীমাবদ্ধ ডিকোডিং সমস্যার সংক্ষিপ্ত এবং কার্যকর বহুপদী মডেলিং পদ্ধতি প্রস্তাব করা
উল্লেখযোগ্য উন্নতি: একই নিরাপত্তা বজায় রেখে স্বাক্ষর আকার উল্লেখযোগ্যভাবে হ্রাস করা
তাত্ত্বিক অবদান: সীমাবদ্ধ ডিকোডিং সমস্যা এবং উন্নত MPCitH কাঠামোর মধ্যে সেতু স্থাপন করা
ব্যবহারিক মূল্য: পোস্ট-কোয়ান্টাম স্বাক্ষর স্কিমের জন্য নতুন ডিজাইন চিন্তাভাবনা প্রদান করা

অপূর্ণতা

জটিলতা ট্রেড-অফ: নির্মাণ জটিলতার বিনিময়ে স্বাক্ষর আকার হ্রাস
সীমিত নতুনত্ব: প্রধানত বিদ্যমান প্রযুক্তির চতুর সমন্বয়, তাত্ত্বিক উদ্ভাবন তুলনামূলকভাবে সীমিত
বাস্তবায়ন বিবরণ অনুপস্থিত: বিস্তারিত কর্মক্ষমতা বিশ্লেষণ এবং প্রকৃত বাস্তবায়নের তুলনা অনুপস্থিত

প্রভাব

একাডেমিক মূল্য: MPCitH কাঠামোর প্রয়োগের জন্য নতুন কেস স্টাডি প্রদান করা
ব্যবহারিক তাৎপর্য: ভবিষ্যত NIST স্ট্যান্ডার্ডাইজেশন প্রক্রিয়ায় স্কিম নির্বাচনকে প্রভাবিত করতে পারে
পদ্ধতিগত অবদান: অন্যান্য কঠিন সমস্যার অনুরূপ মডেলিংয়ের জন্য রেফারেন্স প্রদান করা

প্রযোজ্য পরিস্থিতি

সম্পদ-সীমিত পরিবেশ: স্বাক্ষর আকার সংবেদনশীল অ্যাপ্লিকেশন পরিস্থিতি
পোস্ট-কোয়ান্টাম ক্রিপ্টোগ্রাফি স্থাপনা: বৈচিত্র্যময় নিরাপত্তা অনুমানের প্রয়োজনীয় সিস্টেম
গবেষণা প্রোটোটাইপ: আরও অপ্টিমাইজেশন এবং উন্নতির ভিত্তি হিসাবে

তথ্যসূত্র

পেপারটি ২৪টি গুরুত্বপূর্ণ তথ্যসূত্র উদ্ধৃত করে, যা MPCitH কাঠামোর বিকাশ, কোডিং তত্ত্বের প্রয়োগ এবং সম্পর্কিত NIST প্রার্থী স্কিমগুলি অন্তর্ভুক্ত করে, গবেষণার জন্য একটি দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করে।