التوقيعات المبنية على مشاكل الفك المقيدة باستخدام MPCitH

المعلومات الأساسية

• معرّف الورقة: 2510.11224
• العنوان: التوقيعات المبنية على مشاكل الفك المقيدة باستخدام MPCitH
• المؤلفون: ميشيل باتاجليولا (جامعة بوليتكنيك مارتشي)، سيباستيان بيتزر، أنطونيا واختر-زيه، فيوليتا فيجر (جامعة ميونخ التقنية)
• التصنيف: 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، مما يحقق أحجام توقيع قابلة للمقارنة مع أصغر المرشحين في فئة MPCitH في مسابقة NIST.

الخلفية البحثية والدافع

خلفية المشكلة

1. الحاجة إلى توحيد التشفير بعد الكم: بعد توحيد CRYSTALS-Dilithium و FALCON و SPHINCS+، أطلقت NIST في سبتمبر 2022 استدعاءً لمخططات توقيع رقمي إضافية، بهدف تنويع مجموعة معايير التوقيع بعد الكم.
2. تطور نموذج MPCitH: منذ اقتراحه من قبل Ishai وآخرين في عام 2007، أعاد نموذج MPCitH تشكيل مشهد التوقيعات الرقمية بعد الكم. يوفر TCitH و VOLEitH كتخصصات حديثة لـ MPCitH تحسينات أداء كبيرة مقارنة بالبنى السابقة.
3. تطبيق نظرية الترميز في التشفير: توفر مشاكل الصعوبة المبنية على نظرية الترميز (مثل مشاكل فك هامينج والفك بمقياس الرتبة) أساساً نظرياً لبناء توقيعات بعد الكم فعالة.

دافع البحث

1. الحاجة إلى تحسين الأداء: على الرغم من أن مخطط التوقيع CROSS الحالي يعتمد على مشاكل الفك المقيدة، إلا أنه يستخدم بروتوكول CVE نسبياً بسيطاً، مما يترك مجالاً للتحسين من حيث حجم التوقيع.
2. توحيد الإطار: دمج مشاكل الفك المقيدة في إطاري TCitH/VOLEitH المتقدمين للاستفادة الكاملة من مزايا الأداء لهذه الأطر.
3. تعزيز القدرة التنافسية: تقليل حجم التوقيع بشكل كبير مع الحفاظ على الأمان، مما يعزز القدرة التنافسية في مسابقة NIST.

المساهمات الأساسية

1. اقتراح طريقة نمذجة متعددة الحدود لـ E-SDP: تصميم علاقة متعددة حدود بسيطة البنية لكن فعالة لدمج مشكلة الفك المقيدة للمتلازمة في إطاري TCitH و VOLEitH.
2. تقليل كبير في حجم التوقيعات من نوع CROSS: بالنسبة لنفس مشكلة الفك، يتم تقليل حجم التوقيع بأكثر من 50% مقارنة بمخطط CROSS المقدم لـ NIST (من 12.4 كيلوبايت إلى 5.5 كيلوبايت).
3. اكتشاف الإمكانات التطبيقية لفك الأوزان الكاملة الثلاثية: إثبات أن فك الأوزان الكاملة الثلاثية المرتبط بـ WAVE هو مشكلة فك مقيدة، وتحقيق حجم توقيع مماثل لأصغر المرشحين في فئة MPCitH (3.1 كيلوبايت).
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) لـ i ∈ k
• f_{k+i}(x) = f_E(s_i - ⟨a_i, x⟩) لـ 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

المقارنة مع مرشحي NIST

النتائج الرئيسية

1. تقليل كبير في الحجم: يقلل CROSS-SDP حجم التوقيع بنسبة 64.5% مقارنة بـ CROSS الأصلي
2. تأثير اختيار الإطار: بالنسبة للمشاكل عالية الدرجة، يكون VOLEitH أكثر فعالية من TCitH
3. القدرة التنافسية: يحقق Ternary-SDP أداءً مماثلاً لأفضل المرشحين في فئة MPCitH

الأعمال ذات الصلة

تطور نموذج MPCitH

1. MPCitH الأصلي 23: مقترح في عام 2007، يجمع بين الحسابات الآمنة متعددة الأطراف وتحويل Fiat-Shamir
2. إطار TCitH 21: تطبيق باستخدام المشاركة السرية بنسبة ℓ-من-n
3. إطار VOLEitH 13: ترجمة البروتوكولات ذات المعرفة الصفرية المبنية على VOLE إلى بروتوكولات قابلة للتحقق العام

تطبيقات نظرية الترميز

1. فك هامينج: أساس مخططات مثل SDitH
2. فك مقياس الرتبة: مخططات RYDE و Mirath وغيرها
3. مشكلة نواة التبديل: افتراض الصعوبة لمخطط PERK

مشاكل الفك المقيدة

1. مخطط CROSS 6: استخدام بروتوكول CVE بسيط للفك المقيد
2. مخطط WAVE 10,19: بناءً على فك الأوزان الكاملة الثلاثية للمتلازمة
3. التحليل النظري 8,9: اكتمال NP وصعوبة E-SDP المحددة

الخلاصة والمناقشة

الاستنتاجات الرئيسية

1. التكامل الناجح للإطار: إثبات أن مشاكل الفك المقيدة يمكن دمجها بفعالية في أطر MPCitH المتقدمة
2. تحسن الأداء الكبير: من خلال استبدال بروتوكول CVE البسيط بـ TCitH/VOLEitH، يتم تقليل حجم التوقيع بشكل كبير
3. الانطباق الواسع: تنطبق هذه الطريقة على أنواع مختلفة من مشاكل الفك المقيدة

القيود

1. زيادة التعقيد: مقارنة ببروتوكول 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، مما يوفر أساساً نظرياً قوياً للبحث.