مشكلة خبراء التشفير في المطاعم

في علم التشفير، تُعنى مسألة "مُشفّري العشاء" بدراسة كيفية إجراء عملية حسابية آمنة متعددة الأطراف لدالة XOR المنطقية. وقد طرح ديفيد تشاوم هذه المسألة لأول مرة في أوائل ثمانينيات القرن الماضي، واستخدمها كمثال توضيحي لإثبات إمكانية إرسال رسائل مجهولة الهوية مع ضمان عدم إمكانية تتبع المُرسِل والمُستقبِل بشكل كامل. وغالبًا ما يُشار إلى شبكات الاتصال المجهولة الهوية القائمة على هذه المسألة باسم شبكات DC (حيث يرمز DC إلى "مُشفّري العشاء"). ^{[ 1 ]}

على الرغم من كلمة "تناول الطعام" ، فإن مشكلة خبراء التشفير الذين يتناولون الطعام لا علاقة لها بمشكلة الفلاسفة الذين يتناولون الطعام .

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

في المرحلة الأولى، يقوم كل اثنين من خبراء التشفير بإنشاء سر مشترك مكون من بت واحد، على سبيل المثال عن طريق رمي عملة معدنية خلف قائمة طعام بحيث يرى اثنان فقط من خبراء التشفير النتيجة بالتناوب لكل اثنين من خبراء التشفير. لنفترض، على سبيل المثال، أنه بعد رمي العملة، يتشارك خبير التشفير أ و ب بتًا سريًا.${\displaystyle 1}$يشترك كل من A و C${\displaystyle 0}$، ويشترك كل من B و C${\displaystyle 1}$.

في المرحلة الثانية، يعلن كل خبير تشفير علنًا عن بت، وهو:

• إذا لم يدفعوا ثمن الوجبة، فإن عملية " أو الحصرية " (XOR) للبتّين المشتركين اللذين يمتلكونهما مع جاريهم،
• إذا دفعوا ثمن الوجبة، فإن عكس ذلك هو XOR.

بافتراض أن أياً من خبراء التشفير لم يدفع، فإن (أ) يعلن${\displaystyle 1\oplus 0=1}$أعلن ب${\displaystyle 1\oplus 1=0}$ويعلن C${\displaystyle 0\oplus 1=1}$من ناحية أخرى، إذا دفعت (أ)، فإنها تعلن${\displaystyle \lnot (1\oplus 0)=0}$.

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

ابتكر ديفيد تشاوم مصطلح شبكة خبراء التشفير في المطاعم ، أو DC-net، لهذا البروتوكول.

بروتوكول DC-net بسيط وأنيق. ومع ذلك، فإنه يعاني من عدة قيود، وقد تم استكشاف بعض الحلول لها في أبحاث لاحقة (انظر قسم المراجع أدناه).

تصادم

إذا دفع اثنان من خبراء التشفير ثمن العشاء، فإن رسائلهما ستلغي بعضها البعض، وستكون نتيجة عملية XOR النهائية هي${\displaystyle 0}$يُطلق على هذا اسم التصادم، ويسمح لمشارك واحد فقط بالإرسال في كل مرة باستخدام هذا البروتوكول. في حالة أعم، يحدث التصادم طالما أن أي عدد زوجي من المشاركين يرسل رسائل.

خلل

بإمكان أي خبير تشفير خبيث لا يرغب في نجاح تواصل المجموعة أن يُعطّل البروتوكول بحيث تصبح نتيجة عملية XOR النهائية عديمة الفائدة، وذلك ببساطة عن طريق إرسال بتات عشوائية بدلاً من النتيجة الصحيحة. تكمن المشكلة في أن البروتوكول الأصلي صُمم دون استخدام أي تقنية مفتاح عام ، ويفتقر إلى آليات موثوقة للتحقق من التزام المشاركين بالبروتوكول. ^{[ 2 ]}

تعقيد

يتطلب البروتوكول مفاتيح سرية مشتركة بين المشاركين، وهو ما قد يُشكل إشكالية في حال وجود عدد كبير منهم. كما أن بروتوكول DC-net، رغم كونه "آمنًا بشكل مطلق"، يعتمد في الواقع على افتراض وجود قنوات "آمنة بشكل مطلق" بين أزواج المشاركين، وهو أمر يصعب تحقيقه عمليًا.

تقوم خوارزمية شبكة الفيتو المجهولة ذات الصلة بحساب عملية OR المنطقية لمدخلات العديد من المستخدمين، بدلاً من عملية XOR المنطقية كما هو الحال في شبكات DC، والتي قد تكون مفيدة في التطبيقات التي تناسبها عملية دمج OR المنطقية بشكل طبيعي.

فكّر ديفيد تشاوم لأول مرة في هذه المشكلة في أوائل ثمانينيات القرن العشرين. وكان أول منشور يوضح الأفكار الأساسية الكامنة وراءها من تأليفه. ^{[ 3 ]} وقد نُشرت النسخة الدورية في العدد الأول من مجلة علم التشفير . ^{[ 4 ]}

يمكن تعميم شبكات التيار المستمر بسهولة للسماح بعمليات إرسال أكثر من بت واحد لكل جولة، وللمجموعات التي يزيد عدد المشاركين فيها عن ثلاثة، ولـ "أبجديات" عشوائية بخلاف الأرقام الثنائية 0 و1، كما هو موضح أدناه.

إن الإجراء الذي اقترحه ديفيد تشاوم في الأصل لتجنب التصادمات هو إعادة إرسال الرسالة بمجرد اكتشاف التصادم، لكن الورقة لا تشرح بالضبط كيفية ترتيب إعادة الإرسال.

يتجنب نظام Dissent إمكانية حدوث تصادمات غير مقصودة باستخدام عملية خلط قابلة للتحقق لإنشاء جدول إرسال لشبكات DC، بحيث يعرف كل مشارك بالضبط أي البتات في الجدول تتوافق مع خانة الإرسال الخاصة به، ولكنه لا يعرف من يملك خانات الإرسال الأخرى. ^{[ 9 ]}

يقسم برنامج Herbivore شبكة إخفاء الهوية الكبيرة إلى مجموعات أصغر، مما يُمكّن المشاركين من تجنب محاولات التعطيل عن طريق مغادرة المجموعة المُعطّلة والانضمام إلى مجموعة أخرى، حتى يجد المشارك مجموعة خالية من المُعطّلين. ^{[ 10 ]} يُؤدي هذا النهج إلى خطر يتمثل في إمكانية قيام مُهاجم يمتلك العديد من العُقد بتعطيل المجموعات التي لم يخترقها بالكامل ، وبالتالي "توجيه" المشاركين نحو مجموعات قد تكون فعّالة تحديدًا لأنها مُخترقة بالكامل. ^{[ 11 ]}

يُطبّق بروتوكول Dissent عدة آليات لمواجهة التشويش. استخدم البروتوكول الأصلي ^{[ 9 ]} عملية خلط تشفيرية قابلة للتحقق لتشكيل جدول إرسال شبكة DC-net وتوزيع "مهام الإرسال"، مما يسمح بالتحقق من صحة النصوص المشفرة اللاحقة لشبكة DC-net باستخدام فحص تجزئة تشفيرية بسيط . مع ذلك، تطلبت هذه التقنية عملية تحقق جديدة قبل كل جولة من جولات DC-net، مما أدى إلى زمن استجابة طويل. تسمح آلية لاحقة أكثر كفاءة باستمرار سلسلة من جولات DC-net دون عمليات خلط وسيطة في حال عدم وجود تشويش، ولكنها تستخدم عملية خلط استجابةً لحدث تشويش لتوزيع اتهامات مجهولة المصدر ، مما يمكّن ضحية التشويش من كشف هوية الجاني وإثباتها. ^{[ 5 ]} أخيرًا، تدعم الإصدارات الأحدث شبكات DC القابلة للتحقق بالكامل - بتكلفة كبيرة في كفاءة الحساب نظرًا لاستخدام التشفير بالمفتاح العام في شبكة DC - بالإضافة إلى وضع هجين يستخدم شبكات DC فعالة قائمة على XOR في الحالة العادية وشبكات DC قابلة للتحقق فقط عند حدوث خلل، لتوزيع الاتهامات بسرعة أكبر مما هو ممكن باستخدام عمليات الخلط القابلة للتحقق. ^{[ 8 ]}