Asymptotically Ideal Hierarchical Secret Sharing Based on CRT for Integer Ring

إليك ملخص تقني مفصل للورقة البحثية بعنوان "تقاسم الأسرار الهرمي المثالي تقاربيًا القائم على نظرية الباقي الصينية (CRT) في حلقة الأعداد الصحيحة."

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

تسمح مخططات تقاسم الأسرار (SS) بتوزيع سر ما بين المشاركين بحيث لا يمكن استرداده إلا من قبل مجموعات مصرح لها فقط. وبينما تعامل مخططات العتبة التقليدية من نوع $(t, n)$ جميع المشاركين بالتساوي، فإن السيناريوهات الواقعية غالبًا ما تتطلب تقاسم أسرار هرمي (HSS)، حيث يتم تقسيم المشاركين إلى مستويات ذات عتبات سلطة مختلفة.

تواجه مخططات HSS الحالية مقايضات كبيرة:

• المخططات المثالية (معدل المعلومات $\rho=1$): المخططات القائمة على استكمال بيرك هوف (Birkhoff interpolation) أو الماترويدات متعددة الأشكال (polymatroids) هي مخططات مثالية ولكنها غالبًا ما تتطلب وقتًا حسابيًا أسيًا للموزع أو تحققًا معقدًا للمصفوفات.
• المخططات القائمة على نظرية الباقي الصينية (CRT): توفر المخططات التي تستخدم نظرية الباقي الصينية أحجام حصص مرنة وتعقيدًا حدوديًا. ومع ذلك، فإن مخططات HSS السابقة القائمة على CRT تعاني من أحد عيبين:
  • عيوب أمنية: ثبت عدم أمان بعض المخططات المقترحة (مثل تلك الخاصة بـ Harn و Tiplea وغيرهما).
  • معدل معلومات منخفض: المخططات الآمنة القائمة على CRT (مثل تلك الخاصة بـ Ersoy وآخرين) لديها معدل معلومات أقل بكثير من $1/2$.
  • نقص المرونة: بعض المخططات المثالية لا يمكنها استيعاب أحجام حصص مرنة.

التحدي الجوهري: بناء مخططات HSS (سواء كانت انفصالية Disjunctive أو تجميعية Conjunctive) تكون آمنة، ومثالية تقاربيًا (معدل المعلومات $\to 1$)، وتدعم أحجام حصص مرنة، وتحافظ على تعقيد زمني حدودي للموزع.

2. المنهجية

يقترح المؤلفون مخططين جديدين: مخطط تقاسم أسرار هرمي انفصالي (DHSS) ومخطط تقاسم أسرار هرمي تجميعي (CHSS).

الأدوات الرياضية الأساسية

1. نظرية الباقي الصينية (CRT) عبر حلقات الأعداد الصحيحة: تُستخدم لاستعادة الأسرار من الحصص النمطية (modular shares).
2. متتاليات $k$-المدمجة من الأعداد الأولية المرافقة: تسلسل محدد من الأعداد الصحيحة $L = \{m_0, m_1, \dots, m_n\}$ حيث $m_0$ عدد أولي كبير، والأعداد الأولية اللاحقة تحقق الشرط $km_0 < m_i < km_0 + m_0^\theta$ (حيث $k \ge 1, \theta \in (0,1)$). يضمن هذا الهيكل استيفاء قيد "أسموث-بلوم" (Asmuth-Bloom) تقاربيًا، مما يسمح بمعدلات معلومات عالية.
3. الدوال أحادية الاتجاه (One-Way Functions): تُستخدم لإخفاء القيم الوسيطة وضمان أن المجموعات غير المصرح لها لا يمكنها استنتاج السر حتى لو امتلكت معلومات جزئية.

بناء المخطط

يتبع كلا المخططين إطار عمل متشابهًا ولكنهما يختلفان في هيكل الوصول الخاص بهما:

أ. تقاسم الأسرار الهرمي الانفصالي (DHSS)

• هيكل الوصول: تكون المجموعة مصرح لها إذا استوفت العتبة $t_\ell$ لأي مستوى $\ell$ (أي يوجد $\ell$ بحيث $|A \cap \bigcup_{w=1}^\ell P_w| \ge t_\ell$).
• توليد الحصص:
  • يقوم الموزع بتوليد سر $s \in \mathbb{Z}_{m_0}$.
  • يتم تخصيص أعداد صحيحة عشوائية $c_i$ للمشاركين في المستويات الدنيا.
  • لكل مستوى $\ell$، يتم حساب قيمة $y_\ell = s + \alpha_\ell m_0$.
  • تُشتق حصص المستويات العليا من $y_\ell \pmod{m_i}$.
  • الخطوة الحاسمة: ينشر الموزع $w_i^{(\ell)} = (y_\ell - h_\ell(s_i, \ell)) \pmod{m_i}$، حيث $h_\ell$ هي دالة عامة أحادية الاتجاه. هذا يربط الحصص بعتبة المستوى المحدد دون الكشف عن $y_\ell$ مباشرة.
• إعادة البناء: يقوم المشاركون المصرح لهم بحساب $s_i^{(\ell)}$ باستخدام الدالة أحادية الاتجاه والقيم العامة، ثم يستخدمون CRT لاستعادة $y_\ell$ وأخيرًا $s = y_\ell \pmod{m_0}$.

ب. تقاسم الأسرار الهرمي التجميعي (CHSS)

• هيكل الوصول: تكون المجموعة مصرح لها فقط إذا استوفت العتبة $t_\ell$ لجميع المستويات $\ell$ (أي لكل $\ell$، $|A \cap \bigcup_{w=1}^\ell P_w| \ge t_\ell$).
• توليد الحصص:
  • يتم تقسيم السر $s$ إلى $m$ من الحصص العشوائية $\delta_1, \dots, \delta_m$ بحيث $\sum \delta_i \equiv s \pmod{m_0}$.
  • يتم التعامل مع كل $\delta_\ell$ بشكل مشابه للسر في مخطط DHSS، حيث يتم توليد قيم $y_\ell = \delta_\ell + \alpha_\ell m_0$.
  • يتم توزيع الحصص وإخفاؤها باستخدام دوال أحادية الاتجاه مشابهة لمخطط DHSS.
• إعادة البناء: يعيد المشاركون بناء كل $\delta_\ell$ بشكل مستقل باستخدام CRT، ثم يجمعونهم $\pmod{m_0}$ لاستعادة $s$.

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

1. أول مخطط HSS مثالي وآمن قائم على CRT: صاغت الورقة أول مخططات DHSS و CHSS آمنة ومثالية تقاربيًا بناءً على نظرية الباقي الصينية لحلقة الأعداد الصحيحة.
2. أحجام حصص مرنة: على عكس المخططات المثالية السابقة (مثل Tassa و Cheng) التي تتطلب أحجام حصص ثابتة، تسمح المخططات المقترحة للمشاركين بحمل حصص بأحجام متفاوتة، وهي ميزة متأصلة في النهج القائم على CRT.
3. الكمال التقاربي: ثبت أن المخططات مثالية تقاربيًا. فمع زيادة حجم السر ($m_0$)، يقترب تسرب المعلومات إلى المجموعات غير المصرح لها من الصفر.
4. معدل معلومات تقاربي: يقترب معدل المعلومات $\rho$ من $1$مع$m_0 \to \infty$. ويتحقق ذلك من خلال استخدام متتاليات$k$-المدمجة من الأعداد الأولية المرافقة، والتي تحقق قيد "أسموث-بلوم" مع تقليل الفجوة بين مساحة السر ومساحة الحصة.
5. التعقيد الحدودي: يظل التعقيد الحسابي للموزع حدوديًا، متجنبًا المتطلبات الزمنية الأسية للمخططات المثالية السابقة القائمة على الماترويدات متعددة الأشكال.

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

• إثبات الأمان: أثبت المؤلفون النظرية 2 (الكمال التقاربي) و النظرية 4 (الصحة). لقد أظهروا أنه لأي مجموعة غير مصرح لها $B$، فإن الإنتروبيا الشرطية $H(S|V_B)$ تقترب من إنتروبيا السر $H(S)$ عندما $m_0 \to \infty$.
  • يعتمد الإثبات على تحليل عدد العناصر في مجموعة السر المرشح ($G$) المتوافق مع حصص المجموعة غير المصرح لها. باستخدام خصائص المتتاليات $k$-المدمجة، أظهروا أن نسبة المرشحين الصالحين تتقارب إلى ثابت، مما يؤدي إلى تلاشي فقدان المعلومات $\Delta$.
• معدل المعلومات:
  • لمساحة السر $S = \mathbb{Z}_{m_0}$ وأقصى مساحة حصة $S_{max} = \mathbb{Z}_{m_n}$، يكون المعدل $\rho = \frac{\log_2 m_0}{\log_2 m_n}$.
  • بما أن $m_n < m_0 + m_0^\theta$ (بالنسب لمتتاليات 1-مدمجة)، فعندما $m_0 \to \infty$، فإن $\rho \to 1$.
• المقارنة:
  • مقارنة بـ Harn et al. [7] و Tiplea et al. [9]، فإن المخطط المقترح آمن (حيث ثبت عدم أمان المخططين الآخرين).
  • مقارنة بـ Ersoy et al. [8]، فإن المخطط المقترح لديه معدل معلومات أعلى (يقترب من 1 مقابل أقل من $1/2$).
  • مقارنة بـ Tassa [4] و Chen et al. [5]، يدعم المخطط المقترح أحجام حصص مرنة وله تعقيد حسابي أقل.

5. الأهمية

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

1. الأمان/المثالية (ولكن بتعقيد عالٍ أو عدم مرونة).
2. المرونة/السرعة (ولكن بعدم أمان أو معدل معلومات منخفض).

من خلال الدمج الناجح لـ المتتاليات $k$-المدمجة مع الدوال أحادية الاتجاه في إطار عمل CRT، قدم المؤلفون حلاً عمليًا وفعالًا وسليمًا من الناحية النظرية. وهذا يتيح نشر التحكم في الوصول الهرمي في الأنظمة واسعة النطاق (مثل التخزين الموزع، أو حوكمة البلوكشين، أو أمن الشركات) حيث يكون للمشاركين مستويات امتياز مختلفة، ويجب تحسين أحجام الحصص، وتقليل تسرب المعلومات إلى أدنى حد.