تعيين عشوائيا عناصر N إلى وكلاء ن بحيث يعرف كل وكيل فقط عناصره

Question

مشكلة

أنا أعمل على تطبيق ينطوي على خلط وتوزيع أوراق اللعب للاعبين. كتحدي، حاولت حل هذه المشكلة بطريقة لا تتطلب وسيطا موثوقا به.

بعدة أخرى، المهمة هي العثور على خوارزمية موزعة

• يعين بشكل فريد $ n $ أرقام الوكلاء $ 1..N $
• يسمح لكل وكيل بمعرفة أي شيء حول المهمة ولكن الخاصة به
• عند الكشف عن المهمة، يسمح لاعبين آخرين للتحقق من المهمة

نفترض أيضا أن معرفة المهمة الأخرى هي ميزة لكل وكيل، وكشف عن عيبها قبل الأوان. يفترض أيضا أن الوكلاء قادرين على التحدث مع بعضهم البعض بطريقة مخفية من جميع الوكلاء الآخرين.

الحل الجزئي

الحل الذي توصلت إليه مع أعمال فقط تحت افتراض أن الخصوم لا يتعاونون.

الفكرة هي إنشاء مجموعة من $ n $ nonces، وتعيين كل وكيل بالضبط واحد غير متزوج. ثم يتم تمرير المجموعة من وكيل إلى وكيل بطريقة متفق عليها عند الطلب، مخفية من جميع الآخرين، حتى تلقى كل وكيل المجموعة مرة واحدة بالضبط. في كل مرة يتلق فيها الوكيل المجموعة، فإنه ينبذه NEWCE الخاص به مع جديد، ويحفظ NEWCE NEWCE، ويؤكد اسباغ المقدم للآخرين. يتم إجراء هذا الإجراء بأكمله مرتين، عند هذه النقطة، تلقى جميع الوكلاء المحدد مرة واحدة على الأقل بعد أن قامت جميع الوكلاء الآخرين بتبديل أخلاقهم، مما يجعل من المستحيل الاعتراف بالتعريف، وبالتالي الخريطة عن الوكلاء الآخرين.

عندما يتلقى الوكيل الأخير تعيين المرة المرة الثانية، فإنه يشاركه مع الجميع، ويتأكيد جميع الوكلاء الآخرين على أن nonce موجود في المجموعة. ثم تعيين العوامل عددا من كله في المجموعة المستندة إلى بذرة عشوائية متفق عليها، مما يتيح لنا المهمة الفريدة المطلوبة.

للسماح بتحقق الملكية، بدلا من الأخلاق، وضع الوكلاء قيمة التجزئة غير النظيرة في المجموعة، والكشف عن nonce الفعلي فقط عند التحقق مطلوب.

---

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

جميع الأفكار هي موضع تقدير!

Answer 1

هذه المشكلة هي جزء من مجموعة من المشكلات المعروفة باسم البوكر العقلي .

هناك مقالة ممتازة وصغيرة بواسطة Shamir ، Rivest و Adleman يصف طريقة عملية حول كيفية تنفيذ هذه الخوارزمية.

الملخص هو الذهب:

يمكن أن يلعب اثنين من اللاعبين غير شريفة لعبة عطل لعبة البوكر دون استخدام أي بطاقات (على سبيل المثال عبر الهاتف)؟

توفر هذه الورقة الإجابات التالية:

1. لا. (دليل رياضيات صارم مزود.)
2. نعم. (بروتوكول صحيح وكامل معين.)

أساسا، من وجهة نظر نظرية المعلومات، يلعب مثل هذه اللعبة مستحيلة بدون طرف ثالث موثوق به، ولكن من الممكن تصميم بروتوكول باستخدام وظائف التشفير الشديدة المعروفة.

---

ستعمل الخوارزمية على النحو التالي:

افترض أن لديك $ n $ (أرقام من $ 1 $ to $ n $ ). يتمتع كل مشارك في البروتوكول بالوصول إلى الوظائف السرية $ e_i $ و $ d_i $ والتي تستخدم للتشفير وفك تشفير البيانات. يجب أن تلبي هذه الوظائف بعض الخصائص، والتي سنقوم بتحليلها لاحقا.

يتم إعطاء المشارك الأول مجموعة كاملة من الأخلاق. إنه يقوم بتشفير كل nonce بوظيفته السرية $ e_1 $ ، خلطها بشكل عشوائي، ويمرر البيانات الناتجة للمشارك الثاني.

المشارك الثاني سيفعل نفس الشيء، ولكن في هذه الحالة ليس لديه أونسات، ولكن التقليب العشوائي للأقميات المشفرة. سيقوم أيضا بتشفير كل عنصر مع وظيفته السرية الخاصة به $ e_2 $ وخلط البيانات مرة أخرى.

ثم المشارك الثالث، وما إلى ذلك، حتى يتم خلط جميع المشاركين البيانات وتشفيرها مع وظيفتها السرية.

بشكل عام عملية الإعداد هي:

giveacodicetagpre.

بعد هذا الإعداد، كل عنصر من عناصر data هي غير موجودة مع جميع الوظائف السرية $ e_i $ في ترتيب عشوائي غير معروف لأي مشارك.

لاحظ أنه في هذه المرحلة أمر مستحيل بالنسبة لكل مشارك استنتاج كل nonce دون مساعدة من المشاركين الآخرين. وهذا يكفي أن يقوم أحد المشاركين بخلط البيانات بشكل عشوائي تماما لإزالة أي تحيز محتمل في النظام الناتج، بشكل مستقل إذا حاول بعض المشارك الخبيث التحيز بالترتيب.

المشارك $ I $ - يتم تعيين nonce nonce في وضع $ i $ $ . لاستعادة مثل هذا nonce، المشارك $ I $ يسأل كل مشارك آخر $ j \ neq i $ لفك تشفير القيمة مع وظيفتها السرية $ d_j $ في المنعطفات. في النهاية المشارك $ i $ $ سيكون لها مشفرة فقط مع دئتها السرية الخاصة به $ e_i $ so يمكنه استرداده باستخدام $ d_i $ .

استرداد nonce $ i $ :

giveacodicetagpre.

في نهاية هذا الإجراء يعرف كل مشارك أن غير مشارك نفسه، ولكن لا يوجد مشارك آخر يعرف شيئا عن ذلك.

بعد استخدام هذه القيم لمشكلتك الحالية، يمكن للمشغل أن يدعي أنهم حقا يتحكمون حقا في مثل هذه النشر، إما عن طريق نشر وظائف الأسرار $ e_i $ و $ d_i $ ، لذلك يمكن للجميع حساب جميع القيم محليا، أو فك تشفير قيمة القيمة القيمة بعد الخطوة الأولى ولكن قبل الخطوة الثانية، والنشر ثم استخدام هذه القيمة كإدخال في الخطوة الثانية لفك تشفيرها بالكامل.

الوظائف $ e_i $ و يجب أن تحتوي $ d_i $ الخصائص التالية:

1. $ e_i (x) $ هو الإصدار المشفهر من رسالة $ x $ ضمن المفتاح Span Class="Math-Container"> $ i $ ،
2. $ d_i (e_i (x))= x $ لجميع الرسائل $ x $ ومفاتيح $ i $ $ ،
3. $ e_i (e_j (x))= e_j (e_i (x)) $ لجميع الرسائل $ x $ ومفاتيح $ i $ $ و $ J $ ،
4. معطى $ x $ و $ e_i (x) $ ، من المستحيل بشكل حسابي على cryptanalyst مشتق $ I i $ ، لجميع $ x $ و $ I $ ، <

/ لى>

إعطاء أي رسائل $ x $ و $ y $ ، من المستحيل البحث عن المفاتيح SPAN CLASS="حاوية الرياضيات"> $ i $ $ و $ J $ مثل $ e_i (x )= e_j (y) $ .

كما هو مذكور في الورقة، فإن معظم هذه الافتراضات مشتركة بطريقة أو بأخرى باستثناء الممتلكات 3)، والتي تخبر وظائف التشفير يجب أن تنقل.

يقترحون مخطط تشفير بسيط يرضي هذه الخصائص. دعنا نقول أن جميع المشاركين يتفقون على بعض الأرقام الرئيسية الكبيرة $ P $ (لا بأس إذا تم إصلاحه في البروتوكول). وكل مشارك اختيار سري رقم عشوائي $ k_i $ مثل $ gcd (k_i، p - 1)= 1 دولار < / span>. دعونا نقول $ Q_I $ هو مثل هذه القيمة $ k_i \ cdot q_i \ equiv 1 \ mod (p -1) $ < / span>. ثم المشارك $ i $ يمكن استخدام الوظائف السرية:

$$ E_I (x)= x ^ {k_i} \ mod (p) $ $$ d_i (y)= y ^ {q_i} \ mod (p) $

بعض التحذيرات حول هذه الخوارزمية: لا يمكن للمشاركين الغش بهذه الطريقة التي تفيد بها التواطؤ معهم في تعلم النظير الآخر (ما لم يكن بالطبع $ n-1 $ < / span> compronants تولد، وفقط واحد nonce هو المتبقية). ومع ذلك، يمكن للمشاركين الضارون مهاجمة البروتوكول بأي مشاركات، ومما يتعاذر بشكل فعال عملية التعامل، لأن الكثير من الإجراءات مطلوبة من كل مشاركين بينما يتعاملون في التعامل مع الأخلاق. يمكنهم أيضا إنتاج جبرية، ولكن يمكن تخفيف ذلك تمديد البروتوكول للكشف عن المشارك الذي كان الجاني ومعاقبة مثل هذا المشارك على مستوى أعلى.

---

قمت بتنفيذ هذه الخوارزمية للحصول على لعبة البوكر في بالقرب من bullchain . يمكنك رؤية الكود في الصدأ هنا . لاحظ عدم وجود أي طرف ثالث موثوق به في كومة، ولكن هناك بيئة حوسبة موثوقة يمكن لجميع المشاركين استخدامها كآلية لتشغيل هذا البروتوكول.