الحسابات المتعددة الأطراف الآمنة

الحسابات المتعددة الأطراف الآمنة (والمعروف أيضا باسم حساب مؤمن أو تأمين التعددية الحزبية (إم بي سي)) هو حقل فرعي من علم التعمية. والهدف من أساليب الحسابات المتعددة الأطراف الآمنة هو تمكين الأطراف من حساب معادلة مشتركة على مدخلاتهم، ولكن مع الحفاظ على سرية هذه المدخلات في نفس الوقت. فعلى سبيل المثال، يمكن أن يحسب اثنان من المليونيرات على من هو أكثرهم ثراء، ولكن دون الكشف عن صافي ثرواتهم. في الواقع، اقترح هذا المثال في البداية من جانب اندرو ياو في بحث في عام 1982، وسُميّ في وقت لاحق مشكلة ياو المليونير.
وهذا المفهوم مفهوم هام في مجال علم التعمية ويرتبط ارتباطا وثيقا بفكرة المعرفة الصفرية. وبشكل عام فإنه يشير إلى النظم الحاسوبية التي يرغب أطراف متعددة في الاشتراك بحساب قيمة تستند على معلومات شخصية سرية، ولكنهم لا يرغبون في الكشف عن أسرارها لأي شخص آخر في هذه العملية. على سبيل المثال، قد يرغب شخصان من الذين يملكون بعض المعلومات – x وy- على التوالي، بالاشتراك بحساب معادلة f(x,y) من دون الكشف عن أية معلومات حول x أو y الا ما يمكن استخلاصه بشكل معقول بمعرفة القيمة الفعليى للمعادلة f(x,y)، حيث «استخلاصه بشكل معقول» غالبا ما يتم تفسيرها بالتحسيب في وقت متعدد الحدود. وان الدافع الأساسي لدراسة طرق تأمين الحساب هو لتصميم نظم تتيح الاستفادة القصوى من المعلومات دون المساس بخصوصية المستخدم.
وتم تقديم تأمين حساب رسميا في 1982 من قبل أندرو ياو (وبالمناسبة، فإنه كان أول متلق لـ جائزة كانوث) وكان تأمين حساب طرفين.
وقد أفسحت مشكلة المليونير حلها طريق إلى التعميم بروتوكولات متعددة الأطراف. في الحسابات المتعددة الأطراف الآمنة، يوجد عدد معين من المشاركين P1، P2...PN ولكل متشارك بياناته الخاصة، على التوالي d1، d2... dN. ويرغب المشاركون في حساب قيمة المعادلة العامة F على عدد N من المتغيرات على النقاط (d1، d2...dN). يُطلق على بروتوكول الحسابات المتعددة الأطراف الآمنة «آمن» إذا لم يتمكن مشارك من معرفة المزيد من المعلومات من خلال وصف المعادلة العامة ونتيجة الحساب العالمية أكثر مما يعلمه من خلال مدخلاته الخاصة—في ظل ظروف معينة وذلك اعتمادا على النموذج المستخدم.
ومثل العديد من بروتوكولات علم التعمية، فان تأمين بروتوكول الحسابات المتعددة الأطراف الآمنة يعتمد على افتراضات مختلفة:
يمكن أن يكون حسابي (أي يعتمد على بعض المعادلات الرياضية، مثل العوامل) أو غير خاضع لشروط (عادة مع بعض احتمال للخطأ الذي يمكن أن يكون صغير).
قد يفترض النموذج الذي وصف من خلاله المخطط أن المشاركين يستخدمون شبكة متزامنة (رسالة تبعث عند «التكتكة» وتصل دائما عند «التكتكة» التالية)، ووجود قناة اذاعية آمنة ويمكن الاعتماد عليها، ووجود قناة اتصال آمنة بين كل زوج من المشاركين (لا يمكن لخصم قراءة، أو تعديل، أو إنشاء رسائل في القناة)، الخ.
يمكن للخصم ان يمكن سلبي (يسمح له فقط بقراءة بيانات عدد معين من المشاركين) أو مشارك (يمكن أن يفسد تنفيذ البروتوكول أو عدد معين من المشاركين).
يمكن أن يكون الخصم ثابت (يختار ضحاياه قبل بدء حساب التعددية الحزبية) أو حركي (يمكن اختيار ضحاياه أثناء تنفيذ حساب التعددية الحزبية). وتحقيق الأمن ضد الخصم الحركي غالبا ما يكون أصعب بكثير من تحقيق الأمن ضد عدو ثابت.
ويمكن تعريف الخصم على أنه هيكل سدّي (وهذا يعني أنه يمكن أن يفسد أو مجرد يقرأ ذاكرة عدد من المشاركين يصل إلى حد أدنى)، أو يمكن تعريفه بأنه هيكل أكثر تعقيدا (يمكن أن يؤثر على بعض مجموعات فرعية محددة مسبقا للمشاركين، مع نمذجة تأمرات مختلفة). ويشار عادة إلى هذه الهياكل باسم الهياكل الخصمية. وترتبط المجموعة المقابلة المكونة من مجموعات من الأطراف النزيهة التي يمكن لها ان تنفذ مهمة حسابية باسم هياكل الوصول.
ومبدأ مهم في تأمين حساب التعددية الحزبية هو نقل النسائين.
ويرتبط تأمين حساب التعددية الحزبية الغير مقيد أو ذات المعلومات النظرية ارتباطا وثيقا بمشكلة تقاسم السر، وبشكل أكثر تحديدا تقاسم السر الذي يمكن التحقق منه (VSS)؛ والكثير من بروتوكولات تأمين حساب التعددية الحزبية المؤمنة التي تحمي ضد الخصوم تستخدم VSS.
يقدم تأمين حساب التعددية الحزبية حلولا لمشاكل من واقع الحياة المختلفة مثل توزيع التصويت، والعطاءات والمزادات الخاصة، وتقاسم التوقيع أو فك تشفير المعادلات، واسترجاع المعلومات الخاصة، الخ. وأول تطبيق على نطاق واسع لحساب التعددية الحزبية جرى في الدنمارك في يناير 2008، كما وصفه بوجيتوفت.
حساب حزبين
ان المشكلة الفرعية لتأمين حساب التعددية الحزبية والتي حظيت باهتمام خاص من قبل الباحثين بسبب علاقتها القريبة من العديد من مهام علم التعمية يُشار إليها بـ تأمين حساب الحزبين (2PC) أو تقييم أمن مهمة (SFE). وهذه المنطقة من البحث تتعامل مع السؤال التالي: 'هل يمكن لحساب طرفين أن يتحقق بشكل أكثر كفاءة وتحت افتراضات أمنية أضعف من الحسابات المتعددة الأطراف الآمنة؟’
بروتوكول الطرف الافتراضي
بروتوكول الطرف الافتراضي هو بروتوكول SMC الذي يستخدم أطراف افتراضية ورياضيات معقدة لاخفاء هوية الأطراف.
مراجع
وصلات خارجية
Solution to the Millionaire's Problem A description of Yao's algorithm
Helger Lipmaa's links about multiparty computation
Nick Szabo, "The God Protocols"
Secure distributed CSP (DisCSP) solvers — a web-application with an applet-interpreter to design and run your own full-fledged secure multiparty computation (based on the SMC declarative language). Uses secure arithmetic circuit evaluation and mix-nets.
VMCrypt A Java library for scalable secure computation. By Lior Malka.
The Fairplay Project — Includes a software package for secure two-party computation, where the function is defined using a high-level function description language, and evaluated using Yao's protocol for secure evaluation of boolean circuits.
The SIMAP project; Secure Information Management and Processing (SIMAP) is a project sponsored by the Danish National Research Agency aimed implementing Secure Multiparty Computation.
Secure Multiparty Computation Language - project for development of a 'domain specific programming language for secure multiparty computation' and associated cryptographic runtime.
VIFF: Virtual Ideal Functionality Framework — Framework for asynchronous multi-party computations (code available under the رخصة جنو العمومية الصغرى). Offers arithmetic with secret shared values including secure comparison.
Sharemind: a framework for privacy-preserving data mining — A distributed virtual machine with the capability to run privacy-preserving operations. Has a privacy-preserving programming language for data mining tools. Includes developer tools.
Virtual Parties in SMC A protocol for Virtual Parties in SMC (Secure Multi Party computation)
MPC Java-based implementation A Java-based implementation of the MPC protocol based on Michael.B، Shafi.G and Avi.W's theorem ("Completeness theorems for non-cryptographic fault-tolerant distributed computation") with Welch-Berlekamp error correcting code algorithm to BCH codes. Supports multiple players and identification of "cheaters" with Byzantine protocol. By Erez Alon, Doron Friedland & Yael Smith.
SEPIA A java library for SMC using secret sharing. Basic operations are optimized for large numbers of parallel invocations (code available under the رخصة جنو العمومية الصغرى).
Essential bibliography Secure Multiparty Computation
بروتوكولات تعمية