توقيعات CRYSTALS-Dilithium وFalcon

تكسر خوارزمية Shor توقيعات RSA وECDSA. ويجب أن تحل التوقيعات ما بعد الكمّية محلها في شهادات TLS، وتوقيع الشفرة، وتوقيع البريد الإلكتروني (S/MIME وPGP)، ومصادقة تحديثات البرامج. وقد وحّدت NIST مخططين قائمين على الشبكات: ML-DSA وFN-DSA.

تعتمد Dilithium على صعوبة Module-LWE وModule-SIS (حل الأعداد الصحيحة القصيرة). ويستند إثبات الأمان إلى QROM (نموذج العشوائية الكمّية). ولها ثلاثة أنواع: Dilithium2 (نحو 128 بتًا)، وDilithium3 (نحو 192 بتًا)، وDilithium5 (نحو 256 بتًا). كما أن مسار التوقيع فيها بسيط ولا يحتاج إلى أخذ عينات الرفض.

المفتاح الخاص: المصفوفتان السريتان s1 وs2. المفتاح العام: t = As1 + s2. وقّع كما يلي: خذ عينة عشوائية y؛ واحسب w = Ay؛ واحسب التحدي c = H(mu || w1) حيث w1 = HighBits(w)؛ ثم احسب z = y + cs1؛ وإذا كان ||z|| أو ||r0|| كبيرًا جدًا، فارفض العملية وأعد المحاولة. أخرج (z, c, hint).

للتحقق من (z, c, hint): تحقّق من أن ||z|| صغير؛ واحسب w' = Az - ct؛ واستخدم hint لاستعادة w1؛ ثم تحقّق من أن c == H(mu || w1). إن hint هو عدد صغير من البتات تنتجه MakeHint(). ويضمن الرفض ألا تسرّب z معلومات عن s1، وتُعرف حجة الأمان باسم حجة "aborts-then-uniform".

ML-DSA-65 (Dilithium3، أمان بمستوى 192 بتًا): المفتاح العام 1952 بايت، والمفتاح الخاص 4000 بايت، والتوقيع 3293 بايت. وبالمقارنة، يملك ECDSA-P256 مفتاحًا عامًا بحجم 64 بايت وتوقيعًا بحجم 64 بايت. وتكون توقيعات Dilithium أكبر بنحو 40 إلى 50 مرة، لكنها آمنة في عصر الحوسبة الكمّية.

تعتمد Falcon على شبكات NTRU وتستخدم أداة أخذ عينات غاوسية فوق شبكة NTRU. وتكون توقيعاتها أصغر بكثير من توقيعات Dilithium، لكن التوقيع يتطلب أداة أخذ عينات غاوسية بأعداد فاصلة عائمة، مما يجعل تنفيذها بزمن ثابت أصعب وكتابة شفرتها بصورة آمنة أكثر تعقيدًا.

Falcon-512 (أمان بمستوى 128 بتًا): المفتاح العام 897 بايت، والتوقيع 666 بايت، أي أصغر بكثير من Dilithium. والمقابل هو أن تنفيذ Falcon بأمان أصعب، إذ إن أخذ العينات الغاوسية عرضة لهجمات التوقيت. وهي مناسبة للبيئات ذات النطاق الترددي المحدود، لكنها تتطلب تنفيذًا دقيقًا.

إن SPHINCS+ مخطط توقيعات قائم على التجزئة، وهو خيار محافظ لا يفترض بنى جبرية محددة. ويعتمد أمانه فقط على أمان دالة التجزئة. ويتراوح حجم التوقيع بين نحو 8 و50 كيلوبايت، وهو حجم كبير، كما أن التوقيع بطيء. ويُستخدم عندما تكون الثقة طويلة الأجل بالغة الأهمية ويأتي الأداء في مرتبة ثانوية.

ML-DSA (Dilithium): استخدام عام، وتنفيذ بسيط، ومناسب لشهادات TLS وتوقيع الشفرة. FN-DSA (Falcon): بيئات ذات نطاق ترددي محدود (IoT وLPWAN). SLH-DSA (SPHINCS+): خيار شديد التحفظ للجذور طويلة الأجل (مفاتيح CA غير المتصلة وجذر الثقة للبرامج).

Dilithium: قد يكشف أخذ عينات الرفض توقيت الفروع، لذا استخدموا مقارنة بزمن ثابت. Falcon: تستخدم أداة أخذ العينات الغاوسية أعدادًا فاصلة عائمة، لذا احرصوا على حتمية حسابات الفاصلة العائمة. في كليهما: تجنبوا القنوات الجانبية في الحسابات متعددة الحدود. استخدموا التطبيقات المرجعية من حزم طلب NIST.

NIST FIPS 204: ‏ML-DSA (Dilithium). NIST FIPS 205: ‏SLH-DSA (SPHINCS+). NIST FIPS 206: ‏FN-DSA (Falcon). نُشرت جميعها في أغسطس 2024. وتنفّذ مكتبات OpenSSL 3.x وBoringSSL وliboqs (مشروع Open Quantum Safe) المخططات الثلاثة كلها.

ما الميزة الرئيسية لـ Falcon مقارنةً بـ Dilithium؟

ML-DSA (Dilithium): قائم على الشبكات، وبسيط، وتوقيعاته نحو 3 كيلوبايت. FN-DSA (Falcon): قائم على NTRU، وتوقيعاته نحو 700 بايت، لكن تنفيذه معقد. SLH-DSA (SPHINCS+): قائم على التجزئة، ومحافظ، وحجمه كبير. وقد وُحّدت جميعها في FIPS 204/205/206. التالي: الترحيل إلى التشفير ما بعد الكم باستخدام أساليب هجينة.