💻 computer science

Machine-Checked Cardinality Bounds for Masked Barrett Reduction: A 1-Bit Side-Channel Leakage Barrier in Post-Quantum Cryptographic Hardware

تقدم هذه الورقة برهاناً تم التحقق منه آلياً باستخدام لغة Lean 4، يثبت وجود "حاجز بت واحد" (1-Bit Barrier) عالمي لعملية اختزال باريت المقنعة (masked Barrett reduction) في التشفير ما بعد الكمي، مما يثبت أن خرائط الأسلاك الداخلية الخاصة بها لها عدد صور عكسية لا يتجاوز اثنين، وبالتالي يضمن فقدان إنتروبيا دنيا لا يتعدى بتًا واحدًا، مما يتيح بناء تركيبات PINI في الحقول الأولية (Prime-Field PINI compositions) آمنة لبروتوكولات ML-KEM وML-DSA.

المؤلفون الأصليون: Ray Iskander, Khaled Kirah

نُشر 2026-04-28

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Ray Iskander, Khaled Kirah

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

الصورة الكبيرة: حماية الأسرار الرقمية

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

فكر في "التغطية" كأنك تضع رقمك السري داخل صندوق، ثم تضيف إليه رقماً عشوائياً متغيراً قبل أن تظهره للعالم. إذا فعلت ذلك بشكل مثالي، فلن يرى المتلصص سوى ضوضاء عشوائية ولن يتعلم شيئاً عن سرك.

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

المشكلة: فخ "البابين"

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

ومع ذلك، فإن اختزال باريت مختلف. فهو يحتوي على خطوة "شرطية". تخيل ممرًا به مفترق طرق:

الباب (أ): إذا كان السر صغيرًا، تذهب يسارًا.
الباب (ب): إذا كان السر كبيرًا، تذهب يمينًا.

اكتشف المؤلفون أنه بسبب هذا المفترق، يمكن لـ قيمة مخرجات واحدة على السلك أن تنتج عن طريق قناعين عشوائيين مختلفين بدلاً من قناع واحد فقط.

المخاوف: قد يرى المهاجم المخرجات ويفكر: "آها! يمكن أن يكون هذا ناتجًا عن القناع (أ) أو القناع (ب). لقد حصرت الاحتمالات!"
الواقع: أثبت المؤلفون أنه لا يمكن أبداً أن يكون أكثر من اثنين. ليس ثلاثة، أو أربعة، أو مئة. إنه محصور بدقة بين 0 أو 1 أو 2.

"حاجز البت الواحد" (The 1-Bit Barrier)

تسمي الورقة هذا الاكتشاف بـ حاجز البت الواحد.

إليك التشبيه:
تخيل أنك تحاول تخمين كلمة مرور.

الأمان المثالي: لديك 1,000,000 كلمة مرور محتملة، والمهاجم ليس لديه أي فكرة عن أي واحدة منها.
تسريب باريت: بسبب تأثير "البابين"، قد يدرك المهاجم: "إنها إما كلمة المرور (أ) أو كلمة المرور (ب)". لقد حصر المجال من 1,000,000 إلى مجرد 2.

من الناحية الرياضية، حصر المجال إلى احتمالين يكلفك بالضبط 1 بت من الأمان (بما أن $2^1 = 2$ ).

الادعاء: أثبت المؤلفون أن اختزال باريت لا يسرب أبداً أكثر من هذا الـ 1 بت. إنه سقف "محافظ". وفي كثير من الحالات، يكون التسريب في الواقع أقل من 1 بت لأن بعض المخرجات مستحيلة الوصول إليها (الحالة "0")، وهو أمر جيد في الواقع للأمان.

الوعد "المُتحقق آلياً" (The Machine-Checked Promise)

لماذا يجب أن نثق في هذا؟ عادةً، تُكتب البراهń الأمنية على الورق ويتم فحصها من قبل البشر، والذين قد يرتكبون الأخطاء.

نهج الورقة: استخدم المؤلفون برنامج كمبيوتر يسمى Lean 4 لكتابة البرهان.
التشبيه: بدلاً من أن يقول إنسان "أعتقد أن هذا الجسر آمن"، قاموا ببناء روبوت فحص كل مسمار وعارضة وبرغي في منطق تصميم الجسر. أبلغ الروبوت عن "صفر أخطاء" (أو "Zero sorry"، بمصطلحات الكمبيوتر).
النتيجة: هذا ليس مجرد نظرية؛ إنه شهادة موثقة رياضياً تعمل لأي "مقياس" (أي حجم للرقم السري) يُستخدم في المعايير الحالية مثل ML-KEM و ML-DSA.

لماذا فشلت شريحة "جسر آدمز" (Adams Bridge)؟

تشرح الورقة أيضاً لماذا وُجد أن تصميم شريحة معينة تسمى Adams Bridge معرض للخطر في دراسات سابقة.

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

ملخص النتائج

الثلاثية (The Trichotomy): الرياضيات وراء اختزال باريت بسيطة بشكل مفاجئ. لأي مخرج، يكون عدد الطرق للوصول إليه دائماً 0 أو 1 أو 2. ليس أكثر أبداً.
حد البت الواحد: هذا يعني أن أقصى قدر من المعلومات يمكن للمهاجم سرقتها من سلك واحد في هذه العملية هو 1 بت.
البرهان: تم التحقق من هذا بواسطة مساعد برهان كمبيوتري (Lean 4) مع صفر أخطاء، مما يجعله ضماناً ذهبياً لمصممي الأجهزة (Hardware).
الحل: للحفاظ على أمان النظام بأكمله، يجب على مصممي الأجهزة ضمان تجديد الأقنعة العشوائية بين كل مرحلة من مراحل الحساب. إذا فعلوا ذلك، فإن "حاجز البت الواحد" سيحمي المسار بأكمله.

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

إليك ملخص تقني مفصل للورقة البحثية بعنوان: "الحدود الكاردينالية (عدد العناصر) التي تم التحقق منها آلياً لتقليل باريت المقنع: حاجز تسرب القنوات الجانبية بمقدار 1 بت في أجهزة التشفير لما بعد الكوانتم."

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

تعتمد معايير التشفير لما بعد الكوانتم (PQC) مثل ML-KEM (FIPS 203) و ML-DSA (FIPS 204) بشكل كبير على خطوط معالجة تحويل "نمط عدد النظريات" (NTT). تتكون هذه الخطوط من مراحل "فراشة" (butterfly) خطية ومراحل تقليل معياري غير خطية، والتي تُنفذ عادةً باستخدام تقليل باريت (Barrett reduction).

بينما توفر أطر التحقق الرسمي الحالية (مثل ISW، t-SNI، PINI، DOM) ضمانات قوية للتقنيع البولياني (Boolean masking) فوق الحقل $GF(2)$ ، إلا أنها تفتقر إلى توصيفات تم التحقق منها آلياً للتقنيع الحسابي (arithmetic masking) فوق الحقول الأولية ( $\mathbb{Z}_q$ )، وتحديداً لتقليل باريت.

الفجوة: غالباً ما تعاني التنفيذات العتادية (مثل تصميم "جسر آدمز" Adams Bridge) من ثغرات في القنوات الجانبية لأن عملية الطرح الشرطي غير الخطية في تقليل باريت تكسر البنية الأفينية (affine structure) التي تفترضها نظريات التركيب القياسية.
السؤال: في ظل التقنيع الحسابي من الدرجة الأولى، ما هو حد التسرب الدقيق للأسلاك الداخلية لدائرة تقليل باريت؟ لم تستطع الأدوات السابقة تقديم إجابة عالمية تم التحقق منها آلياً، مما أدى إلى حالة من عدم اليقين في شهادات FIPS 140-3.

2. المنهجية

استخدم المؤلفون نهجاً للتحقق الرسمي باستخدام مساعد الإثبات Lean 4 ومكتبة Mathlib.

الصياغة الرسمية: قاموا بتعريف خريطة الأسلاك الداخلية لباريت جبرياً فوق $\mathbb{Z}_q$ (حيث $q$ هو المعامل). تأخذ الخريطة $f_x(m)$ سراً $x$ وقناعاً عشوائياً $m$ ، وتنتج مخرجاً بناءً على هيكل ذي فرعين يتم تحديده بواسطة طرح شرطي.
استراتيجية الإثبات: بدلاً من محاكاة حالات محددة، أثبتوا نظريات عالمية تصمد لجميع قيم $q > 0$ ومعاملات الإزاحة $s$ .
المفهوم الأساسي: قاموا بتحليل كاردينالية السوابق (preimage cardinality): بالنسبة لسر $x$ وقيمة مخرج $v$ محددة، كم عدد الأقنعة $m$ المتميزة التي يمكن أن تكون قد أنتجت $v$ ؟
سلسلة الأدوات: تحتوي الوثيقة (artifact) على 12 نتيجة مثبتة مع صفر من الـ sorry (أي لا توجد إثباتات غير مكتملة)، مما يضمن أن كل خطوة تم التحقق منها عبر النواة (kernel-verified) بواسطة Lean.

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

أ. نظرية التثليث (The Trichotomy Theorem)

تثبت الورقة أن خريطة الأسلاك الداخلية لباريت تظهر هيكلاً ثلاثي القيم للسوابق. لأي سر $x$ وأي مخرج $v$ ، يكون عدد الأقنعة $m$ بحيث $f_x(m) = v$ هو بالضبط 0 أو 1 أو 2.

الآلية: يخلق الطرح الشرطي فرعين أفينيين (إزاحات في $\mathbb{Z}_q$ ). سابقة أي قيمة هي مجموعة جزئية من مرشحين اثنين على الأكثر: $\{x - v, x - v + r\}$ ، حيث $r = 2^s \mod q$ .
العالمية: هذا ينطبق على أي معامل $q$ وإزاحة $s$ ، وبشكل مستقل عن معاملات الـ PQC المحددة.

ب. حاجز الـ 1 بت (The 1-Bit Barrier)

بناءً على التثليث، وضع المؤلفون حداً عالمياً للتسرب:

الحد الأقصى للتعدد (Max-Multiplicity): بما أن أقصى عدد من الأقنعة ينتج مخرجاً واحداً هو 2، فإن أقصى احتمال لملاحظة قيمة مخرج معينة هو $2/q$ .
حد الإنتروبي الأدنى (Min-Entropy Bound): الإنتروبي الأدنى الشرطي $H_\infty(\text{output} \mid x)$ مقيد من الأسفل بـ $\log_2(q) - 1$ .
التفسير: يسرب تقليل باريت بت واحداً كحد أقصى من الإنتروبي الأدنى لكل سلك داخلي تحت فحص الدرجة الأولى. هذا حد "محافظ" لأن العديد من قيم المخرجات غير قابلة للوصول (عدد السوابق = 0)، مما يعني أن التسرب الفعلي غالباً ما يكون أقل من 1 بت.

ج. إطار عمل PF-PINI

قدم المؤلفون PF-PINI (Prime-Field PINI)، وهو مقياس أمني جديد للأدوات الحسابية (gadgets) فوق $\mathbb{Z}_q$ :

التعريف: الأداة هي PF-PINI( $k$ ) إذا كانت كاردينالية السابقة محدودة بـ $k$ .
النماذج:
- مراحل الفراشة (Butterfly Stages): تحقق PF-PINI(1) (تقابل مثالي، صفر تسرب يتجاوز القناع).
- تقليل باريت (Barrett Reduction): يحقق PF-PINI(2) (حاجز الـ 1 بت).
ملاحظة التركيب: لاحظوا (رغم عدم إثباتها رسمياً بعد) أنه إذا تم فصل مراحل خط المعالجة بواسطة تقنيع مرحلي جديد (fresh inter-stage masking)، فإن الحد الأقصى لتعدد خط المعالجة المركب هو $\max(k_1, k_2)$ . وهذا يعني أن حاجز الـ 1 بت ينتشر عبر خط معالجة NTT بالكامل.

4. النتائج والتحليل

الإثباتات المحققة آلياً: تتضمن الوثيقة 12 نظرية مثبتة، بما في ذلك التثليث، وإثباتات الإحكام (tightness proofs) (التي تظهر أن العدد 2 قابل للتحقيق)، ونماذج PF-PINI.
اكتشاف فجوة الدعم: يكشف التحليل عن قيم مخرجات "غير قابلة للوصول" (عدد السوابق = 0). هذه ميزة أمنية وليست خطأً، لأنها تقلل من المعلومات الفعالة للمهاجم.
دراسة حالة جسر آدمز (Adams Bridge): حللت الورقة تنفيذ عتادي "جسر آدمز":
- فشل داخل المرحلة (Intra-stage failure): أظهرت أعمال سابقة (الورقتان 1 و 2) وجود ثغرات بسبب تفاعل الأجزاء (shares) دون تقنيع وسيط.
- فشل بين المراحل (Inter-stage failure): تحدد هذه الورقة أن جسر آدمز يفشل في تطبيق التقنيع الجديد بين المراحل. وبالتالي، فإن حد تركيب PF-PINI لا ينطبق، مما يسمح للتسرب بالتضاعف ( $k_1 \times k_2$ ) بدلاً من البقاء محصوراً في الحد الأقصى ( $\max(k_1, k_2)$ ). وهذا يفسر سبب كون التصميم عرضة للخطر رغم وجود حاجز الـ 1 بت لكل بوابة باريت على حدة.
الأثر الكمي:
- لـ ML-KEM ( $q=3329$ ): التسرب $\le 1$ بت (الإنتروبي الأدنى $\ge 10.70$ بت).
- لـ ML-DSA ( $q=8,380,417$ ): التسرب $\le 1$ بت (الإنتروبي الأدنى $\ge 21.99$ بت).

5. الأهمية

الجاهزية للشهادات: يوفر حاجز الـ 1 بت شهادة عالمية تم التحقق منها آلياً لمصممي العتاد. فهي تسمح للمقيمين باعتماد التنفيذات القائمة على باريت لمعايير FIPS 140-3 دون الحاجة لإعادة التحقق من مجموعات المعاملات المحددة.
توجيه التصميم: توضح الورقة أن المتطلب المعماري الأساسي للأمن هو التقنيع الجديد بين المراحل. إذا تم تنفيذ ذلك، فإن الطبيعة غير الخطية لتقليل باريت لا تخل بأمن خط معالجة NTT باستثناء فقدان ضئيل قدره 1 بت.
التحول المنهجي: تنقل هذه الورقة تحليل القنوات الجانبية من المحاكاة التجريبية والتحقق القائم على SAT إلى الإثباتات الجبرية المتحقق منها عبر النواة، مما يضع معياراً جديداً للتحقق من عتاد الـ PQC.
إكمال برنامج الأوراق الخمس: تغلق هذه الورقة الفجوة التي تركتها الأوراق السابقة في السلسلة، حيث انتقلت من بناء الأدوات (الورقة 1) وتقدير الهجمات (الورقة 2) إلى الأسس الجبرية (الورقة 3)، والتركيب الخطي (الورقة 4)، وأخيراً التوصيف غير الخطي (الورقة 5).

6. القيود والعمل المستقبلي

إثبات التركيب: الادعاء بأن $\max(k_1, k_2)$ ينطبق على خطوط المعالجة المركبة مع التقنيع الجديد هو حالياً ملاحظة وليس نظرية مثبتة رسمياً.
التقنيع من درجات أعلى: تقتصر النتائج على التقنيع من الدرجة الأولى ( $t=1$ ). يتطلب الأمن من الدرجات الأعلى تحليل السوابق المشتركة عبر أسلاك متعددة.
صياغة الإنتروبي: بينما تم إثبات الحد الجبري، فإن حد الإنتروبي الأدنى المعلوماتي يعتمد على تعريفات قياسية لم يتم دمجها بالكامل بعد في Mathlib.
عمليات تقليل أخرى: النتائج خاصة بتقليل باريت؛ وتتطلب عمليات تقليل مونتغمري (Montgomery) أو التقليل المباشر (schoolbook) تحليلاً منفصلاً.

باخت ملخص، تثبت هذه الورقة أن تقليل باريت آمن جوهرياً تحت التقنيع الحسابي من الدرجة الأولى، حيث لا يسرب أكثر من 1 بت من المعلومات لكل سلك، بشرما يتم تطبيق تقنيع جديد بين مراحل خط المعالجة. وهذا يوفر أساساً رياضياً صارماً لتأمين أجهزة الـ PQC من الجيل القادم.