مشكلة MPC والدوائر المموّهة لـ Yao

تتيح MPC لـ n أطراف، يحتفظ كل منها بمدخل خاص x_i، أن تحسب معًا f(x_1,...,x_n) من دون كشف مدخلاتها لبعضها — كما لو أن طرفًا ثالثًا موثوقًا أجرى الحساب.

في مسألة أصحاب الملايين التي طرحها Yao عام 1982، تريد Alice وBob معرفة من منهما أكثر ثراءً من دون الكشف عن ثروتيهما، ومن دون طرف ثالث موثوق. تحل MPC هذه المسألة بضمانات تشفيرية.

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

يمكن تمثيل أي دالة على شكل دارة بوليانية (بوابات AND وXOR وNOT). وغالبًا ما تعمل بروتوكولات MPC على مستوى الدارة، فتقيّم كل بوابة بأمان.

تعيّن Alice (المموِّهة) تسميتين عشوائيتين لكل سلك: واحدة للقيمة 0 وأخرى للقيمة 1. وتشفّر جدول الحقيقة لكل بوابة باستخدام تسميات أسلاك الإدخال. ويحصل Bob (المقيِّم) على تسميات مدخلاته فقط عبر النقل المتغاضي.

يتلقى Bob جداول مموهة (4 عمليات تشفير لكل بوابة AND). ويفك تشفير صف واحد بالضبط باستخدام تسميات مدخلاته، فيحصل على تسمية المخرج، من دون أن يعرف ما إذا كانت تمثل 0 أو 1.

أرفق "بت اختيار" عشوائيًا بكل تسمية. ويستخدم Bob بتات الاختيار للعثور على الصف المموه الصحيح في O(1) بدلًا من تجربة عمليات فك التشفير الأربع كلها. وهذا يقلل الحساب بمقدار 4×.

Kolesnikov & Schneider (2008): اختر إزاحة عامة Δ. ثم اجعل label_1 = label_0 ⊕ Δ لكل سلك. تصبح بوابات XOR مجانية (ولا تحتاج إلى تشفير)، مما يوفر نحو 30% من عرض النطاق الترددي.

Zahur et al. (2015): لا تتطلب كل بوابة AND سوى نصين مشفرين (بعد أن كانت تتطلب 4). وبالاقتران مع Free-XOR، يؤدي ذلك إلى خفض عرض النطاق الترددي للدارات المموهة القياسية إلى النصف.

الدارات المموهة التقليدية مخصصة لطرفين. أما الامتدادات متعددة الأطراف (مثل بروتوكول BMR) فتوزع عملية التعمية على جميع الأطراف بالتوازي، لكنها تتطلب اتصالًا من الرتبة O(n²). وهي عملية مناسبة للقيم الصغيرة لـ n.

في بروتوكول الدارة المموهة لدى Yao، كيف يحصل Bob على تسميات الأسلاك الموافقة لبتات مدخله الخاص؟

تتيح MPC للأطراف إجراء الحساب معًا من دون كشف المدخلات. وتشفّر الدارات المموهة الدوال البوليانية في جداول حقيقة مشفرة. وتجعل التحسينات (Free-XOR وHalf-Gates وPoint-and-Permute) هذه الدارات عملية. ويوفر OT تسميات مدخلات Bob بصورة خاصة.