💻 computer science

Partial Derandomization for Leakage-Resilient Shamir's Secret Sharing over Composite Order Fields

تقدم هذه الورقة تجريداً عشوائياً جزئياً لأماكن التقييم لتقاسم أسرار شامير المقاوم للتسريب عبر حقول الرتبة المركبة، وذلك عن طريق استبدال $n$ من النقاط العشوائية المستقلة بتكرارات لدالة نسبية ثابتة، مما يقلل العشوائية المطلوبة من $nd \log p$ إلى $d \log p$ بت مع تحقيق أمن تام ضد تسريب الكتلة الواحدة لأنظمة معلمات محددة.

المؤلفون الأصليون: S. Venkitesh

نُشر 2026-08-03

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

CC BY 4.0

المؤلفون الأصليون: S. Venkitesh

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

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

ومع ذلك، فإن الحياة الواقعية فوضوية. قد لا يتمكن لص ماكر من سرقة قطعة كاملة من اللغز، لكن يمكنه استراق النظر إلى معلومات صغيرة جداً من قطعة كل صديق في آن واحد. ربما يمكنه رؤية ما إذا كان ضوء معين في شريحة كمبيوتر يعمل أو لا، أو الاستماع إلى طنين كهربائي ضئيل. وهذا ما يسمى التسريب المادي للبتات (physical bit leakage). الأمر يشبه لصاً لا يستطيع سرقة المفتاح بأكمله، لكن يمكنه الشعور بشكل أسنان كل مفتاح في حلقة المفاتيح، بروزاً واحداً صغيراً في كل مرة. وإذا تم ترتيب قطع اللغز بإهمال، فإن هذه النظرات الصغيرة يمكن أن تتراكم لتكشف السر بالكامل.

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

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

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

ملخص تقني: نزع العشوائية الجزئي لمشاركة سر شامي (Shamir's Secret Sharing) المقاومة للتسريب فوق حقول ذات رتب مركبة

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

تتناول الورقة بناء أماكن تقييم صريحة لمخططات مشاركة سر شامي (SSS) التي تكون مقاومة لـ تسريب البتات الفيزيائية (physical-bit leakage) عبر حقول ذات رتب مركبة ( $\mathbb{F}_{p^d}$ حيث $d \ge 2$ ).

في مخطط SSS القياسي، يتم مشاركة سر بين $n$ من الأطراف بحيث يمكن لأي $k$ منهم إعادة بنائه. بينما تُعرف البناءات العشوائية (اختيار أماكن التقييم بشكل موحد عشوائياً) بأنها آمنة إحصائياً ضد التسريب المحلي، إلا أنها تتطلب عشوائية عامة موثوقة. في الممارسة العملية، قد يؤثر الخصوم على البذرة العشوائية (random seed)، مما يوجه المخطط نحو أماكن تقييم معرضة للاختراق.

أرست الأعمال السابقة ما يلي:

فوق الحقول الأولية ( $\mathbb{F}_p$ )، تؤدي أماكن التقييم العشوائية إلى مقاومة التسريب باحتمالية عالية.
فوق الحقول المركبة ( $\mathbb{F}_{p^d}$ )، أثبت نجوين (EUROCRYPT 2025) وجود ثنائية مثالية: أي مخطط مشاركة سر قائم على الأكواد الخطية يكون إما آمناً تماماً (المسافة الإحصائية 0) أو غير آمن تماماً ضد تسريب البتات الفيزيائية.
ومع ذلك، بالنسبة للحقول المركبة، لم يكن معروفاً أي بناء صريح وحتمي لعائلات أماكن التقييم لـ $k > 2$ أو لأنظمة الكتل العامة (general block-leakage regimes). اعتمدت البناءات الصريحة الموجودة للحقول الأولية على خصائص استخراج البتات غير الخطية التي لا تنطبق على خرائط الإحداثيات الخطية للحقول المركبة.

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

2. المنهجية والبناء

يقترح المؤلف استراتيجية نزع عشوائية جزئي. بدلاً من اختيار $n$ من نقاط التقييم المستقلة عشوائياً، يقوم ببناء أماكن التقييم كمتتالية من تطبيق دالة نسبية $\Phi$ على نقطة أساس مختارة عشوائياً $x_0$ .

البناء:

إعداد الحقل: ليكن $\mathbb{F} = \mathbb{F}_{p^d}$ مع عنصر أولي $\alpha$ .
عامل الخطوة: عرّف تحويل موبيوس (Möbius transformation) كـ $\Phi(x) = \frac{\alpha x}{x + 1}$ .
أماكن التقييم: تُعرّف أماكن التقييم الـ $n$ كـ $x_j = \Phi^j(x_0)$ لـ $j = 0, \dots, n-1$ ، حيث $x_0 \in \mathbb{F}^*$ هي نقطة أساس مختارة عشوائياً.
تقليل الإنتروبيا: يتطلب تحديد المخطط فقط $d \log p$ بت (لاختيار $x_0$ )، وهو تقليل كبير عن $nd \log p$ بت المطلوبة لـ $n$ من النقاط العشوائية المستقلة.

الرؤية الهيكلية الرئيسية:
يعتمد تحليل الأمان على الأقطاب المتمايزة (distinct poles) لمتتالية $\Phi^j$ .

$\Phi^0(x) = x$ له قطب عند $\infty$ .
لـ $j \ge 1$ ، يكون لـ $\Phi^j(x)$ قطب عند نقطة منتهية متميزة في $\mathbb{F}^*$ .
هذا "تمايز الأقطاب" أمر بالغ الأهمية. ويقارن المؤلف هذا بـ $\Psi(x) = \alpha x$ (التمدد النقي)، حيث تشترك جميع المتتلات في نفس القطب عند $\infty$ ، مما يؤدي إلى انهيار حجة الأمان.

3. النهج التقني

يسير البرهان عبر ثلاث مراحل، مستفيداً من الثنائية المثالية التي أثبتها نجوين (2025):

الثنائية المثالية (المرحلة 1):
تستخدم الورقة حقيقة أن استخراج الإحداثيات في $\mathbb{F}_{p^d}$ هو خطي فوق $\mathbb{F}_p$ . وبناءً عليه، فإن خريطة التسريب هي خطية. وهذا يعني أن المسافة الإحصائية بين توزيعات التسريب للأسرار المختلفة هي إما 0 أو 1. يتحقق الأمان المثالي إذا وفقط إذا كانت خريطة التسريب شاملة (surjective). هذه الحالة تكافئ كون مصفوفة الاختبار $\Theta_{\vec{i}}$ (المشتقة من أماكن التقييم ونمط التسريب) ذات رتبة كاملة (full column rank) فوق $\mathbb{F}_p$ .
عدم انحلال الكسور الجزئية (المرحلة 2):
لإثبات أن مصفوفة الاختبار ذات رتبة كاملة، يجب على المؤلف إثبات أنه لا يوجد أي مزيج خطي غير بديهي لقوى أماكن التقييم يتلاشى. يعرّف دالة نسبية $G_\ell(x) = \sum c_j \eta(i_j) (\Phi^j(x))^\ell$ .
باستخدام تفكيك الكسور الجزئية (partial fraction decomposition)، يستغل المؤلف الأقطاب المتمايزة لـ $\Phi^j$ . ولأن الأقطاب متمايزة، فإن بقايا (residue) $G_\ell$ عند أي قطب محدد يتم تحديدها بواسطة حد واحد فقط في المجموع. إذا كانت $G_\ell$ متطابقة مع الصفر، فيجب أن تتلاشى جميع المعاملات. هذه الحجة الخاصة بـ "عدم الانحلال" تحد من عدد نقاط الأساس "السيئة" $x_0$ التي تسبب فشل شرط الرتبة.
التمديد متعدد الكتل (المرحلة 3):
يتم تمديد الحجة إلى التسريب متعدد الكتل (حيث يتم تسريب عدة إحداثيات لكل حصة). يتعامل المؤلف مع معاملات الحقل الناشئة عن التجميعات الخطية داخل الحصص، موضحاً أن حجة الكسور الجزئية تظل صالحة طالما أن نمط التسريب "مقبول" (distinct block positions per share).

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

النظرية 1.1 (الأمان المثالي ضد تسريب الكتلة الواحدة):
بالنسبة للمعاملات $n = O(d / \log_p d)$ وأي عتبة $k \ge 2$ ، توجد مجموعة من نقاط الأساس "السيئة" $Bad \subset \mathbb{F}^*$ بحجم $|Bad| \le n + n(dp)^n$ . لأي $x_0 \notin Bad$ ، يكون المخطط المستخدم في أماكن التقييم $x_j = \Phi^j(x_0)$ آمناً تماماً (المسافة الإحصائية تساوي 0 بالضبط) ضد أي نمط تسريب كتلة واحدة.

هذا يعني الأمان المثالي ضد تسريب بت فيزيائي واحد لكل حصة لأي عدد أولي $p$ .
ضمان وجود $x_0$ جيد عندما يكون $d > n(1 + \log_p d) + \log_p(2n)$ .

النظرية 1.2 (تسريب متعدد الكتل):
بالنسبة لنمط تسريب مقبول ثابت يحتوي على $M$ من إجمالي الكتل المسربة، يتم تحديد حجم المجموعة السيئة بـ $|Bad| \le n + n \cdot p^M$ . يوجد $x_0$ جيد إذا كان $M < d - \log_p(2n)$ .

للأمان الشامل ضد جميع الأنماط التي تحتوي على $\le M$ من الكتل، يكون حد $|Bad| \le n + n(dpe)^M$ ، مع ضمان الوجود عندما يكون $d > M(\frac{5}{2} + \log_p d) + \log_p(2n)$ .

المصنف (Classifier):
تقدم الورقة مصنفاً صريحاً (الخوارزمية 1) الذي، بمعلومية $x_0$ مرشح، يتحقق من شرط الرتبة الكاملة لجميع أنماط التسريب. يعمل هذا كاختبار سليم للمصادقة على أمان البناء الهيكلي.

5. الأهمية والمقارنة

تدعي الورقة المساهمات والتمايزات التالية:

الأمان المثالي مقابل الأمان الإحصائي: على عكس البناءات العشوائية السابقة فوق الحقول المركبة التي قدمت أماناً إحصائياً ( $\epsilon = 2^{-\Omega(d)}$ )، يحقق هذا البناء أماناً مثالياً (المسافة الإحصائية 0) لنطاق محدد من المعاملات.
نزع العشوائية: يقلل من العشوائية المطلوبة لتحديد المخطط من $nd \log p$ بت إلى $d \log p$ بت عن طريق قصر أماكن التقييم على عائلة ذات بارامتر واحد (مدار $\Phi$ ).
بناء صريح: يوفر أول عائلة صريحة من أماكن التقييم لـ $k > 2$ فوق الحقول المركبة التي تقاوم تسريب البتات الفيزيائية، متجاوزاً نموذج "الأماكن العشوائية".
القيود والمقايضات:
- عدد الأطراف $n$ محدود بـ $O(d / \log_p d)$ ، بينما تدعم البناءات العشوائية $O(dk / \log_p d)$ . يفترض المؤلف أن هذا الفقد في عامل $k$ هو أمر متأصل في البناءات ذات البارامتر الواحد.
- الشمولية متعددة الكتل محدودة حالياً بعنق زجاجة في تعداد الأنماط، مما يؤدي إلى حدود أسية للمجموعة السيئة في $M$ .
- يعتمد البناء على الهيكل الجبري المحدد لتحويل موبيوس $\Phi(x) = \alpha x / (x+1)$ ; بينما يفشل التمدد البديل $\alpha x$ في توفير الأمان.

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