مسئله شام خوردن رمزنگاران

۳ رمزنگار برای صرف شام گرد یک میز جمع شده‌اند. پس از صرف شام و هنگام پرداخت پول میز، پیشخدمت به آنها خبر می‌دهد که پول میز توسط یکی از رمزنگاران یا آژانس امنیت ملی پرداخت شده‌است. در نتیجه همهٔ آنها از این موضوع با خبر می‌شوند و به این کار که به طور ناشناس انجام شده‌است احترام می‌گذارند و از هویت فرد رمزنگار سؤال نمی‌پرسند تا هویت او گم نام باقی بماند؛ ولی می‌خواهند بدانند که آیا یکی از آنها پرداخت کننده پول میز بوده یا سازمان امنیت ملی این کار را انجام داده‌است. به خاطر همین آنها به تبادل پروتکل زیر اقدام می‌نمایند:

هر رمزنگار یک رقم ۰ یا ۱ را به دلخواه برای خود انتخاب می‌کند. سپس به طور خصوصی رقم انتخابی خود را به فرد سمت چپی خود اعلان می‌کند. هر رمزنگار رقم دریافتی را (رقمی را که از نفر سمت راستی خود دریافت کرده‌است) با رقم انتخابی خود (رقمی که انتخاب کرده بود و به نفر سمت چپی خود فرستاده بود) فصل ضمنی (xor) می‌کند. اگر پرداخت کننده نباشد حاصل را به طور عمومی اعلان می‌کند. وگرنه مخالف باینری (not) حاصل را به طور عمومی اعلان می‌کند. سه رقمی که اعلان عمومی شده‌است با هم فصل ضمنی (xor) می‌شوند. اگر حاصل صفر باشد یعنی سازمان امنیت پرداخت کننده‌است و اگر ۱ باشد یعنی یکی از رمزنگاران پرداخت کننده‌است. اما به هر حال در این مسئله چنانچه یکی از رمزنگاران صورتحساب را پرداخت کرده باشد هویتش گم نام باقی می‌ماند و رمزنگاران فقط می‌دانند که پول میز توسط سازمان امنیت ملی پرداخت نشده‌است.

هرچند که این الگوریتم ساده و ظریف است اما محدودیت‌هایی نیز دارد:

1. تصادم: هرگاه دو رمز نگار پول میز را پرداخت کرده باشند، پیام هریک پیام دیگری را خنثی می‌نماید و در نهایت نتیجه XOR آنها برابر با صفر می‌شود. این حالت را تصادم در مسئله می‌نامند که فقط در هر دوره تنها یک رمز نگار می‌تواند با این پروتکل به انتقال پیام خود بپردازد. به طور کلی‌تر هرگاه تعدادی زوج از رمزنگاران مبادرت به انتقال پیام خود نمایند این حالت به وقوع می‌پیوندد. در طرح پیشنهادی دیوید چام بیان می‌شود که بعد از تصادم یک بار دیگر پیام فرستاده شود اما در مقالهٔ او هیچ توضیح دقیقی دربارهٔ ترتیب ارسال پیام داده نشده‌است.
2. رمزنگاری که در انتها بیت را دریافت می‌کند می‌تواند نتیجه را دستکاری کند. به عنوان مثال اگر رمزنگار انتهایی درستکار نباشد همواره می‌تواند پروتکل را نقض کند و نتیجه را صفر اعلام نماید؛ که این اتفاق به این سبب حادث می‌گردد که از فناوری کلید عمومی در این پروتکل استفاده نشده‌است. اما بدتر از آن موضوع این که پروتکل فاقد مکانیسمی برای تشخیص و اطمینان از پیروی کردن شرکت کنندگان از پروتکل است.
3. پیچیدگی: این پروتکل نیازمند این است که کلید مخفی مشترکی بین هر دو شرکت کننده توزیع شود که اگر تعداد شرکت کنندگان زیاد باشد این خود به مسئله‌ای تبدیل می‌شود. هرچند که این پروتکل خاصیت امنیت بدون قید و شرط را داراست ولی زمانی تحقق می‌یابد که کانال بین آن‌ها نیز همین گونه باشد که در عمل طراحی چنین کانال ارتباطی نا ممکن می‌باشد.