في المقال السابق تطرقنا إلى مشكلة شهيرة في علم التشفير وهي مشكلة عشاء علماء التشفير.
تستطيع رؤية المقالة السابقة من هنا: http://www.isecur1ty.org/?p=6578
سنشرع أولا في شرح حل النظرية ومن ثم سنوضح كيف تم الإستفادة منها في علم التشفير.
حل المشكلة:
افتراض: سأفترض أن إلقاء القطعة النقدية ينتج عنه أحد أمرين، إما ملك أو كتابة (كما نطلق عليها في مصر).
كما سبق وذكرنا في تلميح المقالة السابقة، الفكرة تعتمد على وجود قطعة نقدية بين كل عالمين من أصل 3 علماء (أي أن هناك 3 قطع نقدية) بحيث أنه لا يعلم نتيجة القطعة النقدية إلا عالمين اثنين فقط. الآن لنفرض أن كل القطع النقدية كانت “ملك”. في حالة أن الذي دفع هو المؤسسة، فسيكون الناتج لدينا 0 مختلف. (أي أن الجميع أجابوا بإن القطعتان متطابقتان). أما إذا كان أحد العلماء هو من دفع، فسيكون لدينا 1 مخلتف و 2 متطابق (تذكر أن العالم الذي دفع سيعكس نتيجته دائما).
دعونا نفرض أن الثلاث عملات منهم 2 “ملك” وواحدة “كتابة”. سيكون الناتج لدينا 2 مختلف إذا كانت المؤسسة هي التي دفعت، وواحدة (أو 3) مختلف إذا كان أحد العلماء هو الذي دفع. تستطيع تجربة كل الإحتمالات وستظهر لديك النتيجة الأخيرة نفسها.
إذا كان عدد الذين قالوا مختلف عدد زوجي، فإن المؤسسة هي التي دفعت، أما إذا كان العدد عدد فردي فإن أحد العلماء هو الذي قام بالدفع.
إذا ازداد عدد العلماء إلى 4 أو 5 أو أكثر ستكون النتيجة نفسها.
تطبيقات المشكلة:
تُستخدم النظرية في علم يسمى بـ “Secure Multi-Party Computation” وهي استخراج النتيجة بدون معرفة المدخلات (كما في المثال الآتي).
أفرض أن لديك عدد س من الناس، تريد أن تعرف من هو الأغنى بينهم بدون معرفة ما هو مقدار ما يملكه أيٌ منهم! بالضبط! تستطيع استخدام هذه النظرية لفعل هذا.
أيضا يمكن استخدامها في “Zero-knowledge proof” وهي طريقة ليثبت أحد أطراف الإتصال للطرف الآخر أن معلومة معينة صحيحة بدون الكشف عن أي معلومات. كإثبات أن كلمة المرور صحيحة بدون إرسالها إلى الطرف الآخر. وهذا مفيد جدا لمنع المتنصتين من معرفة كلمة المرور إذا ما تم إرسالها مباشرة عبر الإنترنت.
انت قلت ان نتيجة العملة يعرفها فقط عالمان ولا يعرفها الثالث فكيف اذا عندما يقولون النتيجة احد العلماء سيقول العكس وهو يعلم ان النتيجة يعرفها العالم الآخر؟
النتيجة التي يقولها العالم إما “مماثل” أو “مختلف”. لا يذكر العالم نتيجة كلا الناتجين أو أحدهما!
لنفرض أن لديك العلماء أ، ب، جـ. “أ” و “ب” قاموا برمي العملة والناتج “ملك”. “جـ” لا يعرف ما ناتج العملة، فقط “أ” و “ب” الذين قاموا برميها هم من يعلمون نتيجتها.
الآن “أ” و “جـ” سيرميان العملة، لنفرض أنها “ملك” أيضا. (لا يعلم بالنتيجة إلا “أ” و “جـ”)
و “ب” و “جـ” رميا العملة، والناتج “كتابة”. (لا يعلم بالنتيجة إلا “ب” و “جـ”)
الآن لا أحد يعلم “كلا” الناتجين من عملية رمي العملتين لـ “أ” مثلا! نعم “ب” يعلم واحدة و “جـ” يعلم الآخرى! ولكن لا أحد يعلمهما جميعًا.
الآن إن قال أ أن النتيجة مماثلة أو مختلفة لن تستطيع إثبات هل هو من قام بالدفع أم لا!
كل عالم من علماء “c”,”a”,”b” يعلم نتيجتين ف a يعلم نتيجته مع b و c اي يعلم نتيجتين فمثلا اذا كان a و b كانت النتيحة “ملك” وبين a و c “ملك” فعندما يجيب a فلن يستطيع ان يعكس كلا نتيجتين لانه يعلم ان النتيجة معروفة بينه وبين العالم الآخر.
ممكن تفصل يا صديقي
هو لن يعكس النتيجة! المطلوب منه أن يقول إما متساويتان (أي أن نتيجته مع b و c كلتاهما نفس النتيجة) أو أنهما مختلفتين. ولا أحد يعلم هذه النتيجة إلا هو! فـ b يعلم نتيجته مع a، ولكنه لا يعلم نتيجة a مع c! لهذا لن يستطيع معرفة ما إذا كان a يقول الحقيقة أم لا. أرجو أن أكون قد أوضحتها أكثر، وإذا كان لديك أي استفسار يسعدني الإجابة عليه 🙂
لقد اتضحت الفكرة الآن
لكن تبقى هذه الطريقة غير مجدية 100% لأنه يمكن لاي طرف ان يقول نفس ما قاله أخر وبالتالي لن يكون هناك اي اختلاف والله اعلم 🙂
هذا صحيح! أحسنت. إذا قام عالمان بعكس إجابتيهما لن تكون للطريقة أي فائدة، وهذه أحد عيوب النظرية.