بروتوكول GMW والنقل الغافل

يقيّم بروتوكول Goldreich-Micali-Wigderson (GMW) الدارات البوليانية باستخدام مشاركات أسرار من نوع XOR. تُقسّم قيمة كل سلك بين جميع الأطراف، وتتفاعل الأطراف بوابةً تلو الأخرى.

يحتفظ الطرف i بمشاركة s_i بحيث يكون s_1 ⊕ s_2 ⊕ ... ⊕ s_n = w (قيمة السلك الحقيقية). وتكون بوابات XOR مجانية، إذ يجري كل طرف عملية XOR محليًا على مشاركاته.

بالنسبة إلى بوابة AND على السلكين a وb، يتوسع حساب (a_1⊕a_2)(b_1⊕b_2) إلى حدود متقاطعة. ويتطلب تقييم الحد المتقاطع a_i·b_j بين الطرفين i≠j استخدام النقل المتغاضي.

في نقل 1 من أصل 2 (1-out-of-2 OT)، يملك المرسل الرسالتين (m_0, m_1)، ويملك المستقبل بت الاختيار c. يحصل المستقبل على m_c، ولا يعرف المرسل شيئًا عن c، كما لا يتعلم المستقبل شيئًا عن m_{1-c}.

يعتمد البروتوكول على Diffie-Hellman: ينشئ المستقبل مفتاحين عامين بحيث يعرف اللوغاريتم المتقطع لأحدهما فقط. ويشفّر المرسل كل رسالة باستخدام أحد المفتاحين. ولا يستطيع المستقبل فك تشفير إلا النص المشفر الذي اختاره.

Ishai et al. (2003): انطلاقًا من k عمليات OT أساسية، يمكن إنشاء m >> k من عمليات OT باستخدام عمليات مفاتيح متماثلة فقط. ويخفض تمديد IKNP تكلفة OT إلى نحو 3 استدعاءات لـ AES لكل عملية OT بعد إعداد يُجرى مرة واحدة.

تحتاج كل بوابة AND إلى عملية OT واحدة لكل زوج من الأطراف. ومع تمديد OT، يتيح الحساب المسبق لجميع عمليات OT في مرحلة غير متصلة أن تقتصر المرحلة المتصلة على تبادل XOR واحد لكل بوابة.

يمكن جعل GMW شبه الأمين آمنًا ضد الأطراف الخبيثة باستخدام براهين المعرفة الصفرية أو OT بأسلوب cut-and-choose. وتزداد التكلفة بمقدار 3 إلى 8 مرات، لكن ذلك يضمن الأمان ضد الأطراف التي تغش.

يوسّع MASCOT (Keller et al.) بروتوكول OT لإنتاج ثلاثيات AND موثقة في نموذج الأطراف الخبيثة، مما يتيح بروتوكول SPDZ — الذي تتناوله الوحدة التالية.

تطبّق EMP-toolkit وMOTION بروتوكول GMW مع تمديد OT. وتحققان ملايين بوابات AND في الثانية بين طرفين عبر شبكة LAN، مما يجعل التطبيقات الحقيقية ممكنة.

لماذا لا تتطلب بوابات XOR في بروتوكول GMW أي اتصال بين الأطراف؟

يستخدم GMW مشاركات أسرار من نوع XOR فوق الدارات البوليانية. وتكون بوابات XOR مجانية، بينما تحتاج بوابات AND إلى OT. ويجعل تمديد OT عمليات OT منخفضة التكلفة. ويضيف الأمان ضد الأطراف الخبيثة براهين المعرفة الصفرية أو أسلوب cut-and-choose. وتحقق مكتبات مثل EMP معدل نقل عمليًا للتطبيقات الحقيقية.