💻 computer science

FIPS 204-Compatible Threshold ML-DSA via Shamir Nonce DKG

تقدم هذه الورقة أول مخطط عتبة (threshold) متوافق مع معيار FIPS 204 لخوارزمية ML-DSA، والذي يحقق خصوصية غير مشروطة لحصص الـ nonce وتوافقاً قياسياً للتوقيع من خلال بروتوكول توزيع مفاتيح (DKG) لـ Shamir nonce وأقنعة PRF ذات إلغاء ثنائي، مما يتيح التوقيع الآمن بعتبات عشوائية عبر مختلف ملفات التعريف القائمة على المنسقين والملفات التعريفية الموزعة بالكامل.

المؤلفون الأصليون: Leo Kao

نُشر 2026-03-05

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Leo Kao

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أن لديك خزنة رقمية فائقة الأمان (مثل حساب بنكي أو ختم حكومي) تتطلب مفتاحاً خاصاً لفتحها. في العالم القديم، قد تعطي هذا المفتاح لشخص واحد. ولكن إذا تعرض هذا الشخص للاختراق، أو فقد المفتاح، أو قرر التمرد، فسيصبح النظام بأكهره في خطر.

لحل هذه المشكلة، نستخدم التوقيعات العتبية (Threshold Signatures). بدلاً من مفتاح واحد، نقوم بتقسيم المفتاح إلى $N$ من القطع (الشظايا) ونعطيها لـ $N$ من الأشخاص المختلفين. لفتح الخزنة، لا تحتاج للجميع؛ بل تحتاج فقط إلى عدد محدد منهم (مثلاً 3 من أصل 5) ليجتمعوا معاً ويجمعوا قطعهم لتوقيع معاملة ما.

تخيل أن العالم يتغير. الحواسيب الكمومية قادمة، وهي ستكسر أقفالنا الحالية. لقد أصدرت الحكومة الأمريكية (NIST) للتو قفلاً جديداً مضاداً للكم يسمى ML-DSA (FIPS 204).

المشكلة:
بينما نمتلك طرقاً رائعة لتقسيم مفاتيح الأقفال القديمة (مثل ECDSA)، فإن تقسيم قفل ML-DSA الجديد أمر صعب للغاية.

فخ "الرفض" (The Rejection Trap): يعمل ML-DSA مثل لعبة "خمن الرقم". إذا كان التخمين بعيداً قليلاً، عليك البدء من جديد. في سيناريو الشخص الواحد، يحدث هذا حوالي 20% من الوقت. ولكن إذا حاولت تقسيم العمل بين 5 أشخاص باستخدام الطرق القديمة، فإن الرياضيات تصبح معقدة جداً لدرجة أن فرصة النجاح تنخفض إلى الصفر تقريباً. الأمر يشبه محاولة جعل 5 أشخاص يهمسون بسر لبعضهم البعض، لكن الضجيج عالٍ جداً لدرجة أنهم لا يستطيعون الاتفاق أبداً على الإجابة.
مشكلة الحجم: بعض المحاولات السابقة لإصلاح هذا جعلت "التوقيع الرقمي" (الإيصال) ضخماً جداً — أكبر بـ 5 مرات من الحجم الطبيعي. هذا يكسر التوافق مع الأنظمة الحالية، تماماً مثل محاولة تركيب إطار شاحنة على دراجة هوائية.

الحل: "Shamir Nonce DKG"
تقدم هذه الورقة البحثية طريقة جديدة لتقسيم قفل ML-DSA تحل كلا المشكلتين. يستخدم المؤلف، ليو كاو (Leo Kao)، حيلة ذكية تتضمن توزيع أسرار شامير (Shamir Secret Sharing) (وهي طريقة رياضية لتقسيم الأسرار) خصيصاً لـ "النونس" (الرقم العشوائي المستخدم في اللعبة).

إليك التشبيه:

التشبيه: الأوركسترا والمايسترو

تخيل مجموعة من الموسيقيين (الموقعين) يحاولون عزف مقطوعة (إنشاء توقيع) لمايسترو صارم جداً (المتحقق).

الطريقة القديمة (مشكلة الضجيج):
في المحاولات القديمة، كان على كل موسيقي أن يصرخ بجزئه بصوت عالٍ لكي يسمعه الجميع. ولكن بسبب صراخهم، تشوه الصوت. ولإصلاح هذا التشوه، اضطروا لإضافة الكثير من "الضوضاء الساكنة" (Static Noise) لدرجة أن المقطوعة أصبحت غير قابلة للتمييز (توقيعات ضخمة) أو أنهم ببساطة لم يستطيعوا الاتفاق على اللحن (فشل المحاولات).

الطريقة الجديدة (الأوركسترا الهامسة):
تقدم هذه الورقة طريقة جديدة حيث لا يصرخ الموسيقيون. بدلاً من ذلك، يستخدمون Shamir Nonce DKG (توليد المفاتيح الموزعة).

ورقة الموسيقى السرية: قبل الحفل، يتفق الموسيقيون على ورقة موسيقى سرية (المفتاح السري). يقومون بتقسيم هذه الموسيقى إلى قطع باستخدام خدعة رياضية خاصة (توزيع شامير).
الارتجال (النونس): لكل أغنية، يحتاجون لارتجال لحن عشوائي (النونس). في الماضي، حاولوا تخمين هذا اللحن بشكل فردي، مما تسبب في "فخ الرفض".
- الابتكار: بدلاً من التخمين الفردي، يقومون بتوليد اللحن بشكل مشترك. يكتب كل موسيقي جزءاً صغيراً من "متعدد الحدود" (Polynomial - منحنى رياضي). عندما يجمعون أجزاءهم، نحصل على لحن عشوائي مثالي لا يعرفه أي شخص بمفرده، ولكن الجميع يساهم فيه.
- السحر: لأنهم يستخدمون نوعاً معيناً من المنحنيات (شامير)، حتى لو سرق مخترق نوتات اثنين من أصل ثلاثة من الموسيقيين، فلن يتمكنوا من معرفة اللحن. تعمل النوتات المتبقية مثل "لوحة التشفير لمرة واحدة" (One-time pad)، مما يجعل اللحن مستحيلاً رياضياً للاختراق دون المجموعة الكاملة.

"الأقنعة المتبادلة الإلغائية" (سماعات إلغاء الضجيج)
هناك عقبة أخرى. عندما يرسل الموسيقيون أجزاءهم إلى المايسترو، يحتاجون لإخفاء مساهماتهم الفردية حتى لا يتمكن أحد من سرقة اللحن.

تستخدم الورقة أقنعة متبادلة إلغائية (Pairwise-Canceling Masks). تخيل أن كل زوج من الموسيقيين لديه كود سري لـ "إلغاء الضجيج". عندما يرسلون ملاحظاتهم، يضيف كل منهم ضجيجه الخاص. ولكن لأن الضجيج محسوب بدقة بحيث يلغي ضجيج شريكه، فعندما يجمع المايسترو كل شيء، يختفي الضجيج ولا يتبقى سوى اللحن النقي.
يضمن هذا الخصوصية دون جعل التوقيع ضخماً.

"ملفات النشر الثلاثة" (كيفية إدارة الأوركسترا)

تقدم الورقة ثلاث طرق لتشغيل هذا النظام اعتماداً على مقدار الثقة التي تملكها:

الملف P1 (المايسترو الموثوق): لديك كمبيوتر فائق الأمان وغير قابل للتلاعب (TEE/HSM) يعمل كالمايسترو. يقوم بالعمليات الحسابية الصعبة داخل صندوق مغلق.
- المزايا: الأسرع (5.8 مللي ثانية).
- العيوب: يجب أن تثق في الشركة المصنعة للأجهزة.
الملف P2 (الديمقراطية الخالصة): لا توجد أجهزة موثوقة. يتحدث الجميع مع الجميع باستخدام رياضيات معقدة (MPC) للتحقق من بعضهم البعض.
- المزايا: لا حاجة للثقة في الأجهزة؛ حتى لو كان معظم الأشخاص سيئين، يظل النظام صامداً.
- العيوب: أبطأ (21.5 مللي ثانية) ويتطلب المزيد من التواصل.
الملف P3+ (الفريق شبه غير المتزامن): هذا مخصص للبشر في العالم الحقيقي. يجهز الموسيقيون أجزاءهم "أوفلاين" (أثناء احتساء القهوة). وعندما تأتي إشارة "الانطلاق"، يرسلون أجزاءهم خلال نافذة زمنية محددة.
- المزايا: مرونة عالية جداً؛ ممتاز للبشر الذين لا يمكنهم التواجد عبر الإنترنت في نفس الثانية تماماً.
- العيوب: يتطلب بعض الإعداد المسبق.

لماذا هذا مهم؟

إنه معيار قياسي: التوقيع الناتج له نفس الحجم تماماً (3.3 كيلوبايت) كتوقيع ML-DSA العادي. الأنظمة الموجودة يمكنها التحقق منه دون أي تغييرات.
إنه سريع: يعمل في أجزاء من الثانية، وهو ما يضاهي توقيع شخص واحد.
إنه آمن: لا يعتمد على "الأمل" أو افتراضات معقدة. إنه يستخدم الرياضيات البحتة (الإحصاء) لإثبات أنه حتى لو سرق مخترق بعض القطع، فلن يتعلم شيئاً.
إنه يحل "فجوة القابلية للتوسع": الطرق السابقة كانت تتعطل عند محاولة استخدام أكثر من 6 أشخاص. هذا النظام يعمل مع 3، 16، أو حتى 32 شخصاً.

باختاً:
هذه الورقة البحثية تشبه ابتكار طريقة جديدة لجوقة تغني مقطوعة معقدة ومضادة للكم. بدلاً من أن يصرخ الجميع ويطغوا على بعضهم البعض، يستخدمون تقنية همس منسقة وسرية تضمن أن تكون المقطوعة مثالية، وأن يسمعها الجمهور (المتحققون) بوضوح، وألا يتمكن أحد من أعضاء الجوقة من سرقة اللحن. إنها تجعل المستقبل للتوقيعات الرقمية الموزعة والآمنة أمراً عملياً حقاً.

إليك ملخص تقني مفصل لورقة البحث "FIPS 204-Compatible Threshold ML-DSA via Shamir Nonce DKG" للباحث ليو كاو (Leo Kao).

1. بيان المشكلة

يمثل الوصول الوشيك للحواسيب الكمومية تهديداً لأنظمة التشفير بالمفتاح العام الحالية. واستجابة لذلك، قامت NIST بتوحيد معيار ML-DSA (خوارزمية التوقيع الرقمي القائمة على الشبكة النمطية) كمعيار FIPS 204. وبينما تُعد التواقيع العتبية (حيث تتطلب مجموعة من $N$ من الأطراف وجود مجموعة فرعية مكونة من $T$ للتوقيع) أمراً راسخاً في المخططات الكلاسيكية مثل ECDSA، فإن تكييفها مع ML-DSA القائم على الشبكات يفرض تحديات فريدة:

أخذ عينات الرفض (Rejection Sampling): يستخدم ML-DSA نموذج "Fiat-Shamir مع الإجهاض". يكون التوقيع صالحاً فقط إذا كان متجه الاستجابة $z = y + cs_1$ يستوفي حداً صارماً للمعيار ( $\|z\|_\infty < \gamma_1 - \beta$ ). في الإعدادات العتبية، غالباً ما يؤدي إعادة البناء الساذجة إلى انتهاك هذا الحد بسبب معاملات لاجرانج الكبيرة أو تراكم الضوضاء.
توافق حجم التوقيع: تنتج مخططات الشبكة العتبية الحالية إما تواقيع أكبر بكثير من الحجم القياسي البالغ 3.3 كيلوبايت (مما يكسر توافق FIPS 204) أو تكون محدودة بعتبات صغيرة جداً ( $T \le 6$ ).
خصوصية الـ Nonce (القيم العشوائية): في التوقيع العتبي، يجب توليد الـ nonce الخاص بالتوقيع $y$ بشكل تعاوني. تتطلب النهج السابقة غالباً افتراض "صادقين اثنين" ( $|S| \ge T+1$ ) أو تعتمد على افتراضات حسابية (مثل تدفق الضوضاء) لإخفاء حصص الـ nonce، وهو ما قد يكون غير فعال أو غير آمن ضد الهجمات المستقبلية.
"الفجوة العتبية" (The Threshold Gap): بالنسبة للعتبات العملية ( $T \in [9, 32]$ )، لا يوجد مخطط حالي يحقق في آن واحد العتبات التعسفية، وحجم التوقيع القياسي، وتوافق FIPS 204، وضمانات الخصوصية القوية.

2. المنهجية

يقترح المؤلفون "Threshold ML-DSA via Shamir Nonce DKG"، وهو إطار عمل مبتكر مبني على تقنيتين رئيسيتين:

أ. توليد المفاتيح الموزعة (DKG) لـ Shamir Nonce

بدلاً من توليد الـ nonce $y$ كمجرد مجموع لقيم عشوائية، يقوم الأطراف بتوليد $y$ بشكل مشترك كـ توزيع Shamir من الدرجة $(T-1)$ .

مطابقة الهيكل: المفتاح السري طويل الأمد $s_1$ هو بالفعل مشارك في كثير حدود من الدرجة $(T-1)$ . يتم توليد الـ nonce $y$ ليتطابق مع هذا الهيكل بدقة.
آلية الخصوصية: كل طرف $i$ يمتلك حصة $y_i$ وهي عبارة عن تقييم لكثير حدود من الدرجة $(T-1)$ . الخصم الذي يسيطر على $T-1$ من الأطراف لا يرى سوى $T-1$ من التقييمات لكثير حدود الطرف الصادق.
الإنتروبيا الدنيا المشروطة (Conditional Min-Entropy): نظرًا لأن كثير الحدود يحتوي على $T$ من المعاملات والخصم يعرف $T-1$ من التقييمات، يتبقى بالضبط درجة واحدة من الحرية. تحتفظ حصة الـ nonce للطرف الصادق $y_h$ بـ إنتروبيا دنيا مشروطة تتجاوز 5 أضعاف إنتروبيا المفتاح السري (لـ $|S| \le 17$ ). يوفر هذا خصوصية إحصائية (لا تتطلب افتراضات حسابية) حتى مع وجود طرف صادق واحد في ملفات التعريف القائمة على المنسق (coordinator-based profiles).
إلغاء شرط "الصادقين الاثنين": في ملفات التعريف القائمة على المنسق (P1, P3+)، تسمح هذه التقنية بالتوقيع لمجموعات حجمها $|S| = T$ (الحد الأدنى النظري)، بينما كانت مخططات القناع الثنائي السابقة تتطلب $|S| \ge T+1$ .

ب. أقنعة الإلغاء الثنائية (Pairwise-Canceling Masks)

للتعامل مع تحديات الشبكة الخاصة التي تغيب في ECDSA (ربط الالتزام، وفحص $r_0$ ، وتجميع الاستجابة)، قام المؤلفون بتكييف أقنعة الإلغاء الثنائية:

إخفاء الالتزام: يقوم الأطراف بقناع قيم الالتزام $W_i$ باستخدام بذور PRF ثنائية. هذه الأقنعة مجموعها صفر، مما يخفي المساهمات الفردية مع السماح للمجمع بإعادة بناء الـ $W$ الإجمالي الصحيح.
خصوصية فحص $r_0$ : يتطلب الفحص $\|LowBits(w - cs_2)\|_\infty < \gamma_2 - \beta$ إعادة بناء $cs_2$ . بما أن $c$ قابلة للعكس باحتمالية عالية، فإن تسريب $cs_2$ يكشف المفتاح السري $s_2$ . يستخدم البروتوكول الأقنعة لإخفاء حصص $s_2$ الفردية أثناء إعادة بناء $cs_2$ داخل المجمع أو بروتوكولات MPC/2PC الفرعية.

ج. تحليل توزيع إيروين-هول (Irwin-Hall Distribution)

يتبع الـ nonce المجمع $y$ توزيع إيروين-هول (مجموع $|S|$ من المتغيرات الموحدة) بدلاً من سحب موحد واحد.

فقدان الأمان: قام المؤلفون بإجراء تحليل مباشر لثبات الإزاحة (Corollary 9) لتحديد فقدان الأمان بدقة.
النتيجة: فقدان الأمان ضئيل للغاية: أقل من 0.007 بت لكل جلسة لـ $|S| \le 17$ وأقل من 0.013 بت لـ $|S| \le 33$ . وهذا يحل فجوة القابلية للتوسع الموجودة في العمل السابق حيث تصبح حدود الأمان غير ذات جدوى مع العتبات الأكبر.

3. المساهمات الرئيسية

أول مخطط عتبي متوافق مع FIPS 204 مع عتبة $T$ تعسفية: ينتج المخطط تواقيع قياسية بحجم 3.3 كيلوبايت يمكن التحقق منها بواسطة تطبيقات FIPS 204 غير المعدلة لأي عتبة $T$ .
خصوصية حصة الـ Nonce الإحصائية: يحقق خصوصية الـ nonce بناءً على الإنتروبيا الدنيا المشروطة (الأمان الإحصائي) دون افتراضات حسابية، حتى مع $|S|=T$ في ملفات التعريف القائمة على المنسق.
ثلاثة ملفات تعريف للنشر مع براهين UC:
- الملف P1 (المساعد بـ TEE): يستخدم منسقاً يعتمد على بيئة تنفيذ موثوقة (TEE). يحقق 3 جولات عبر الإنترنت. وهو الأسرع (5.8 مللي ثانية لـ 3-من-5).
  led الملف P2 (الموزع بالكامل): يستخدم الحوسبة متعددة الأطراف (MPC) مع SPDZ و edaBits. يحقق 5 جولات عبر الإنترنت مع أمان الأغلبية غير الصادقة (يتحمل $N-1$ من الفساد). لا يتطلب ثقة في الأجهزة.
- الملف P3+ (الـ 2PC شبه غير المتزامن): مصمم للتفويض الذي يتضمن تدخل البشر. يستخدم 2PC بين طرفي حوسبة. يقوم الموقعون بحساب الـ nonces مسبقاً (offline) والاستجابة ضمن نافذة زمنية. يحقق جولتين منطقيتين (خطوة واحدة للموقع + جولة واحدة للخادم).
حد ثبات الإزاحة المباشر: يستبدل حدود Raccoon الأكثر تحفظاً بتحليل مباشر أكثر دقة، مما يثبت أن المخطط يظل آمناً لآلاف جلسات التوقيع دون حدود فارغة.

4. النتائج والأداء

التنفيذ: تم اختبار تنفيذ بلغة Rust (حوالي 5.5 ألف سطر من المنطق الأساسي) على أجهزة عادية (Intel i7-12700H).
زمن الاستجابة (Latency):
- P1 (TEE): 5.8 مللي ثانية (3-من-5)، وتصل إلى ~60 مللي ثانية لـ 32-من-45.
- P2 (MPC): 21.5 مللي ثانية (3-من-5)، وتصل إلى ~129 مللي ثانية لـ 32-من-45.
- P3+ (Async): 22.1 مللي ثانية (3-من-5)، وتصل إلى ~94 مللي ثانية لـ 32-من-45.
معدل النجاح: معدل النجاح الملحوظ هو 21–45%، وهو مماثل أو أفضل قليلاً من ML-DSA ذي الموقعح الواحد (20–25%). يركز توزيع إيروين-هول الكتلة بالقرب من الصفر، مما يزيد من احتمال اجتياز فحص أخذ عينات الرفض.
القابلية للتوسع: يتوسع المخطط بفعالية حتى $T=32$ وما فوق (حتى $T=128$ مع زمن استجابة أقل من 3 ثوانٍ لـ P3+)، متجاوزاً حد $T \le 6$ الخاص بمخططات LSSS ذات المعاملات القصيرة.

5. الأهمية

يسد هذا العمل فجوة حرجة في التشفير ما بعد الكم:

النشر العملي: يتيح استخدام ML-DSA في البيئات الموزعة عالية الأمان (مثل حفظ العملات الرقمية، PKI الموزع، والتفويض متعدد الأطراف الحكومي) دون التضحية بالأداء أو الامتثال للمعايير.
تقدم نموذج الأمان: من خلال إثبات الأمان ضد الأغلبية غير الصادقة (في P2) وتحقيق خصوصية الـ nonce الإحصائية دون افتراض "الصادقين الاثنين"، فإنه يضع معياراً جديداً للتواقيع العتبية القائمة على الشبكة.
الجاهزية للتوحيد القياسي: يضمن الالتزام الصارم بتنسيقات F 204 التوافق التشغيلي الفوري مع البنية التحتية الحالية، مما يسهًل الانتقال إلى الأمن ما بعد الكم.

باختًا، تقدم هذه الورقة طفرة في التشفير العتبي من خلال الجمع بين هياكل مشاركة سر Shamir وتحسينات الشبكة لتحقيق مخطط توقيع عملي وآمن ومتوافق مع المعايير.