مشاركة الأسرار المرئية والمخططات الجمعيّة

تقسم المشاركة المرئية للأسرار (Naor & Shamir، 1994) صورةً إلى n ورقة شفافة بحيث يكشف تراكب k أوراق شفافة عن الصورة السرية، في حين لا تكشف أي مجموعة أقل من ذلك شيئاً — حتى لمهاجم غير محدود حسابياً.

تُوسَّع كل بكسل من الصورة السرية إلى كتلة بحجم 2x2. بالنسبة إلى بكسل أسود: يحصل كل من الجزأين على نمط مكمل للآخر، وعند تراكبهما يصبح اللون أسود بالكامل. وبالنسبة إلى بكسل أبيض: يحصل الجزءان على النمط نفسه، وعند تراكبهما تكون نسبة الأسود 50%، أي يظهر اللون الرمادي. وتدرك العين الفرق.

بالنسبة إلى سلاسل البتات: شارك السر S بتوليد R_1, R_2, ..., R_{n-1} عشوائياً. اضبط R_n = S XOR R_1 XOR ... XOR R_{n-1}. يؤدي تطبيق XOR على الحصص n كلها إلى الحصول على S. وتكون أي مجموعة فرعية من n-1 حصة عشوائية بانتظام، فلا تكشف شيئاً عن S.

المشاركة باستخدام XOR أو المشاركة الإضافية هي من نوع n-of-n، أي تتطلب جميع الحصص. أما SSS الخاصة بـ Shamir فهي من نوع k-of-n، أي تكفي أي k حصص. المشاركة الإضافية أبسط وأسرع، بينما تتعامل Shamir مع عتبات عامة. وغالباً ما تستخدم بروتوكولات MPC المشاركة الإضافية للعمليات الحسابية.

بالنسبة إلى الأسرار الصحيحة: شارك S على الصورة S = s_1 + s_2 + ... + s_n (mod p). كل s_i عنصر عشوائي من Z_p. ولجمع قيمتين مشتركتين A+B، يجمع كل طرف حصتيه محلياً: (a_i + b_i) mod p. ولا يلزم أي تواصل لإجراء عملية الجمع.

يتطلب ضرب القيم المقسّمة سرياً تفاعلاً بين الأطراف. وتتمثل طريقة Beaver triple الكلاسيكية في الحوسبة المسبقة للثلاثية العشوائية المشتركة (a, b, c=ab). ولحساب x*y، يكشف الجميع (x-a) و(y-b)، وهما لا يكشفان شيئاً عن x,y، ثم يحسبون x*y باستخدام الثلاثية.

يحقق مخطط المشاركة السرية الخطية (LSSS) أي بنية وصول رتيبة. وتُعد Shamir مخطط LSSS. وتشكل LSSS لبنة أساسية للتشفير القائم على السمات (ABE) وأنظمة التحكم في الوصول متعددة السلطات.

تشارك Shamir المعبأة عدة أسرار في كثير حدود واحد: إذ ترمّز k من الأسرار على هيئة معاملات لكثير حدود من الدرجة (n-k). ويسمح ذلك بتوزيع تكلفة الاتصال على عدة قيم في بروتوكولات MPC عندما يلزم مشاركة قيم كثيرة في الوقت نفسه.

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

التشفير المرئي: مصادقة المستندات المطبوعة، وبطاقات الاقتراع الآمنة. المشاركة الإضافية: بروتوكول SPDZ لـ MPC، والتجميع الآمن في التعلم الاتحادي (Google). مخططات العتبة: النسخ الاحتياطي لبذور محافظ الأجهزة، وإدارة مفاتيح المؤسسات.

يكون مخطط المنحدر (k,n) أضعف؛ إذ تكشف أقل من k-d حصة معلومات جزئية، أي d مستويات من السرية. ويُستخدم عندما لا تكون السرية التامة للحصص الجزئية مطلوبة، لكن تكون كفاءة التخزين بالغة الأهمية. كما يتيح حصصاً أقصر من تلك التي توفرها Shamir.

يقسم التشفير المرئي الصور إلى أوراق شفافة، وتستخدم المشاركة الإضافية XOR في مخططات n-of-n، بينما تتعامل Shamir مع k-of-n. ويستخدم MPC المشاركة الإضافية مع ثلاثيات Beaver لإجراء الضرب. التالي: التوقيعات ذات العتبة والاستخدام الواقعي.