Secret sharing with additive access structures from correlated random variables

ملخص تقني: مشاركة الأسرار باستخدام هياكل الوصول الجمعية من متغيرات عشوائية مترابطة

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

تقدم هذه الورقة نموذج هيكل الوصول الجمعي (AAS)، والذي يختلف عن نموذج EAS في طريقتين جوهريتين:

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

الهدف هو تحديد استراتيجية لمشاركة الأسرار تسمح للمجموعات المصرّح لها باستعادة السر بموثوقية عالية مع ضمان عدم تعلم المجموعات غير المصرّح لها لأي معلومات تذكر، كل ذلك مع تعظيم معدل السر (حجم السر المشترك مقسوماً على عدد ملاحظات المصدر).

المنهجية
يقترح المؤلفون استراتيجية لمشاركة الأسرار تعتمد على التصنيف العشوائي (Random Binning) المُكيف لبيئة ديناميكية. يتضمن جوهر المنهجية ما يلي:

• التصنيف العشوائي المكمّم: يلاحظ الموزع تسلسلاً $Y^n$ من مصدر مترابط $(Y, X_L)$. لكل خطوة زمنية $t$، يستخدم الموزع والمشاركون دوال تصنيف عشوائي محددة مسبقاً ($g_i$ و $h_j$) تقوم بربط تسلسلات المصدر بالمؤشرات (indices).
• الترميز التكراري: في كل خطوة زمنية $t$، يحدد الموزع عدد مؤشرات التصنيف ($k_t$) لتضمينها في الرسالة العامة، وعدد المؤشرات ($\sigma_t$) لتخصيصها كسر، بناءً على المجموعة المصرّح لها الحالية $A_t$ والمجموعة غير المصرّح لها $U_t$.
• تحديد الاستراتيجية المسبقة: يتمثل الجانب المبتكر في الإثبات في إدخال عدد مكمّم من عمليات التصنيف. يسمح هذا ببناء استراتيجية مشاركة أسرار واحدة محددة بالكامل مسبقاً. والأهم من ذلك، أن هذه الاستراتيجية لا تعتمد على معرفة كيفية تطور AAS في الخطوات الزمنية المستقبلية؛ إذ يحتاج الموزع فقط إلى معرفة هيكل الوصول الحالي لتحديد الرسالة والسر لتلك الخطوة المحددة.
• فك التشفير: يستخدم المشاركون المصرّح لهم ملاحظاتهم المحلية ($X^n_A$)، والرسائل العامة المتراكمة، ودوال التصنيف لتحديد تسلسل المصدر الفريد المتسق مع قيود النمطية (typicality constraints) ومؤشرات التصنيف المستلمة.

المساهمات والنتائج الرئيسية
تؤسس الورقة للنتائج النظرية التالية:

1. تحقيق معدلات الهيكل الثابت: يثبت المؤلفون وجود استراتيجية لنموذج AAS يكون فيها معدل السر القابل للتحقيق عند أي خطوة زمنية $t$ مستقلاً عن هياكل الوصول في جميع الخطوات الزمنية الأخرى. وتحديداً، يطابق معدل السر القابل للتحقيق $R_t$ أفضل المعدلات المعروفة القابلة للتحقيق لنموذج الهيكل الثابت:
   $$R_t = \min_{U \in U_t} H(Y | X_U) - \max_{A \in A_t} H(Y | X_A)$$
   تشير هذه النتيجة إلى أن الطبيعة الديناميكية لهيكل الوصول لا تؤدي بطبيعتها إلى تدهور معدل السر مقارنة بالسيناريو الثابت.

2. السعة لهياكل الوصول ذات العتبة (Threshold): تثبت الورقة أنه عندما يشكل هيكل الوصول في خطوة زمنية معينة هيكل وصول ذو عتبة (حيث أي مجموعة حجمها $\ge f_1(t)$ هي مجموعة مصرّح لها، وأي مجموعة حجمها $\le f_2(t)$ هي مجموعة غير مصرّح لها)، فإن الاستراتيجية المقترحة تحقق السعة القصوى. وفي حالة محددة حيث يشارك الموزع مفاتيح خاصة مستقلة مع المشاركين، تظهر السعة كالتالي:
   $$R_t = H(X)(f_1(t) - f_2(t))$$

3. القدرة الكلية مقابل السببية: إن النتيجة المثيرة للاهتمام هي أنه بالنسبة لحالة AAS ذات العتبة، فإن الموزع الذي يمتلك قدرة كلية (يعرف التسلسل الكامل لهياكل الوصول في المستقبل) لا يحقق أي ميزة على الموزع السببي (الذي يعرف الهيكل الحالي فقط) من حيث معدلات السر القابلة للتحقيق.

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

تؤكد الورقة أن النتيجة "المثيرة للدهشة" هي استقلالية المعدل القابل للتحقيق عند الزمن $t$ عن تاريخ أو مستقبل هيكل الوصول. وبينما تقدم الورقة إثبات وجود غير بنائي (non-constructive existence proof) لحالة AAS العامة (بالاعتماد على الطريقة الاحتمالية لإثبات وجود دوال تصنيف مناسبة)، فإنها تشير صراحة إلى أن تقديم إثبات قابل للتحقيق بنائي (constructive achievability proof) لحالة AAS العامة لا يزال مسألة مفتوحة، مما يميزها عن الإثباتات البنائية الموجودة للهياكل الثابتة.

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