Canonical Byte-String Encoding for Finite-Ring Cryptosystems

إليك ملخص تقني مفصل لورقة البحث بعنوان "الترميز المعياري للسلاسل البايتية للأنظمة التشفيرية ذات الحلقات المحدودة" (Canonical Byte-String Encoding for Finite-Ring Cryptosystems) للباحثين كيريلو ريابوف وسيرهي كريفاي.

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

تعمل الأنظمة التشفيرية ذات الحلقات المحدودة (مثل تلك المستخدمة في التشفير المحافظ على التنسيق، والحوسبة متعددة الأطراف، والتشفير المتماثل كلياً) على عناصر رياضية داخل الحلقة $\mathbb{Z}_m$ (الأعداد الصحيحة بمقياس $m$). ومع ذلك، فإن البيانات في العالم الحقيقي توجد كـسلاسل بايتات (Bytes) عشوائية (مثل نصوص UTF-8 أو الملفات الثنائية).

تعتمد التنفيذات الحالية غالباً على أبجديات مصممة يدوياً بشكل غير مدروس أو جداول رموز ثابتة صغيرة لربط البايتات بالبواقي. يفتقر هذا النهج إلى طبقة تمثيل معيارية وعامة الغرض يمكنها التعامل مع أي بيانات بأي طول (حتى $2^{64}$ بايت) قبل بدء خطوة التشفير الجبري. تعالج هذه الورقة الحاجة إلى "ترميز" (Codec) حتمي وذاتي التحديد، يقوم بخرائط سلاسل البايتات إلى قوائم من البواقي بمقياس $m$ دون غموض أو فقدان للمعلومات.

2. المنهجية: ترميز base-$m$-len

يقترح المؤلفون ترميزاً جديداً يسمى base-$m$-len، والذي يحول سلسلة بايتات إلى تدفق من البواقي في $\mathbb{Z}_m$. تصميم هذا الترميز مستوحى من rANS (نظم الأرقام غير المتماثلة للنطاق) ولكن تم تكييفه ليكون تحويلاً حتمياً ومنتظماً من بايت إلى باقٍ بدلاً من كونه ترميزاً إنتروبياً احتمالياً.

تنسيق الأسلاك (Wire Format)

يتكون المخرج المشفر من ثلاثة مكونات متميزة:

1. بادئة الطول (Length Prefix): ترميز ثابت العرض لطول سلسلة البايتات الأصلية ($|bytes|$).
2. بادئة الحالة (State Prefix): ترميز ثابت العرض للحالة النهائية للحمولة (Payload).
3. تدفق الحمولة (Payload Stream): تسلسل من البواقي الناتجة عن معالجة البايتات المدخلة.

خوارزمية الترميز (Encoding Algorithm)

• حساب الرأس (Header Calculation): بالنسبة لمقياس $m$ معين، يحسب النظام عرضاً $k = \min \{j \in \mathbb{N}_0 : m^j \ge 2^{64}\}$. يتم ترميز كل من الطول والحالة النهائية باستخدام بالضبط $k$ من أرقام الأساس-$m$ بنظام "Little-endian".
• تحويل الحمولة (Payload Transduction): يقوم المرمز بمعالجة بايتات الإدخال بترتيب عكسي. يحافظ على متغير حالة $x$، يبدأ عند حد سفلي محدد $L$. لكل بايت $b$، يتم تحديث الحالة عبر $x \leftarrow 256x + b$. قبل كل تحديث، يخرج المرمز أرقاماً ($x \mod m$) ويعيد تطبيع الحالة ($x \leftarrow \lfloor x/m \rfloor$) حتى تنخفض الحالة عن حد المرمز.
• المخرج: يتم عكس أرقام الحمولة المنبعثة لتشكيل تدفق FIFO (الذي يعمل بمبدأ "الداخل أولاً يخرج أولاً") لفك التشفين.

خوارزمية فك التشفير (Decoding Algorithm)

• تحليل الرأس (Header Parsing): يقرأ فك التشفير أول $k$ رقم لاستعادة الطول المعلن $\ell$. إذا كان $\ell = 0$، فإنه يعيد سلسلة فارغة فوراً.
• تهيئة الحالة (State Initialization): يتم قراءة الـ $k$ رقم التالية لإعادة بناء حالة الحمولة الأولية.
• إعادة البناء (Reconstruction): يقوم فك التشفير بالتكرار $\ell$ من المرات. في كل خطوة، يستخرج بايتاً واحداً ($x \mod 256$)، ويحدث الحالة ($x \leftarrow \lfloor x/256 \rfloor$)، ويستهلك أرقام حمولة جديدة لإعادة تطبيع الحالة مرة أخرى إلى الحد الأدنى لفك التشفير.
• التسامح مع اللاحقة (Suffix Tolerance): من المهم جداً أن يتوقف فك التشفير تماماً بعد إعادة بناء $\ell$ من البايتات. أي أرقام صالحة متبقية في التدفق (لاحقة) يتم تجاهلها، مما يجعل الترميز متيناً ضد البيانات الملحقة.

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

1. تعريف ترميز معياري: تحدد الورقة ترميزاً (Codec) معيارياً يعتمد على معامل المقياس، وهو مناسب للبروتوكولات ذات الحلقات المحدودة، ويتمحور حول تنسيق أسلاك base-$m$-len.
2. التحقق الرسمي (Lean 4): يقدم المؤلفون صياغة رسمية تم التحقق منها آلياً باستخدام Lean 4. ويتضمن ذلك:
   • إثباتات عكس البادئة ثابتة العرض (مما يضمن إمكانية استعادة الطول والحالة بشكل مثالي).
   • إثباتات حدود حالة الحمولة (لضمان عدم تجاوز الحالة لـ $2^{64}$).
   • صحة التدفق من البداية للنهاية (إثبات أن Decode(Encode(bytes)) == bytes).
   • إثبات التسامح مع اللاحقة (إثبات أن فك التشفير يتجاهل الأرقام التابعة).
3. تنفيذ مرجعي: مكتبة Rust عالية الأداء (sym-adv-encoding) تنفذ الترميز، بما في ذلك واجهات UTF-8 ومجموعات اختبار الأداء.
4. تحليل التعقيد: يعمل الترميز بزمن قدره $O(n)$ وحالة عمل قدرها $O(1)$ (باستثناء أجهزة التخزين المؤقت للإدخال/الإخراج)، مما يجعله خطياً وفعالاً لتطبيقات البث (Streaming).

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

• الصحة: تضمن صياغة Lean 4 الرياضية أنه لأي مقياس مدعوم $m$ (حيث $2 \le m$ و $256 \le \text{decoderLowerBound}(m)$) وأي سلسلة بايتات بطول أقل من $2^{64}$، تكون عملية الذهاب والإياب دقيقة تماماً.
• الكفاءة: تظهر اختبارات الأداء على جهاز Apple M3 Pro أن تنفيذ Rust الأصلي يتفوق بشكل كبير على خطوط الأساس لـ BigUint radix-conversion.
  • مثال: ترميز 1 KiB بمقياس $m=257$ يحقق 217.0 MiB/s، مقارنة بـ 25.2 MiB/s لخط الأساس BigUint.
  • فك التشفير أسرع حتى، حيث يصل إلى 640.5 MiB/s لنفس الإعداد.
• العبء الإضافي (Overhead): تحلل الورقة المقايضة بين حجم المقياس والعبء الإضافي. المقياسات الأكبر تقلل معدل الحمولة (بالاقتراب من 1 رقم لكل بايت عندما $m \to 256$) ولكنها تزيد من حجم الرأس الثابت. بالنسبة لـ $m=257$، يكون معدل الحمولة $\approx 0.9993$ رقماً لكل بايت، مع رأس ثابت مكون من 16 رقماً.

5. الأهمية والقيود

الأهمية:

• التقنين (Standardization): يوفر "طبقة ربط" مفقودة لبروتوكولات التشفير القائمة على الحلقات، مما يسمح بنقل أي بيانات بأمان إلى مجالات $\mathbb{Z}_m$ دون الحاجة لخرائط مخصصة وعرضة للخطأ.
• الثقة الرسمية: توفر الإثباتات التي تم التحقق منها آلياً مستوى عالٍ من الضمان للبنية التحتية التشفيرية الحرجة، وهو أمر نادر في تنفيذات الترميز (Codecs).
• العملية: تثبت اختبارات الأداء أن هذا البناء النظري قابل للتطبيق في التطبيقات الواقعية ذات الإنتاجية العالية.

القيود و السياق الأمني:

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

في الختام، تنجح هذه الورقة في عزل وحل مشكلة تمثيل البايتات للأنظمة التفيرية ذات الحلقات المحدودة، مقدمةً حلاً معيارياً عالي الأداء ومثبتاً رياضياً يسد الفجوة بين البيانات الخام والتشفير الجبري.