A Traceable Dining Cryptographers Protocol — Simplified

Introduction

The Dining Cryptographers Protocol (DCP) is a classic problem that ensures anonymity: when a group of cryptographers pays for dinner, the others should not be able to tell who paid, only whether someone did.

In this version, we extend DCP with traceability and public channels only, while still protecting anonymity.

---

Requirements

1. All secret messages must be communicated over public channels.
2. Announcements must be traceable and verifiable, while preserving anonymity.

---

Cryptographic Ingredients

Each cryptographer (e.g., Wallace, Gromit, Feathers McGraw) prepares:

• A digital signature key pair: (KprX, KpbX)
• Performs a public Diffie-Hellman exchange with neighbors to get shared secret bits.
• Uses signatures to make announcements verifiable.

---

Step-by-Step Protocol (3 Participants)

Let’s assume we have Wallace, Gromit, and Feathers McGraw sitting in a circle.

1. Key Setup

Each cryptographer:

• Generates (KprX, KpbX)
• Publishes KpbX publicly

2. Derive Shared Bits

Using a Diffie-Hellman exchange over public channels, each pair (Wallace–Gromit, Gromit–Feathers McGraw, Feathers McGraw–Wallace) agrees on a shared secret bit by hashing their shared key.

• Wallace gets: bAB and bCA
• Gromit gets: bBC and bAB
• Feathers McGraw gets: bCA and bBC

3. Each Agent Picks a Message Bit

• mX = 1 if paying, otherwise 0

Let’s assume:

• Wallace is the payer → mA = 1
• Gromit and Feathers McGraw are not → mB = mC = 0

4. Calculate Announcement

Each agent calculates:

aX = left_bit ⊕ right_bit ⊕ mX

• Wallace: aW = bCA ⊕ bAB ⊕ 1
• Gromit: aG = bAB ⊕ bBC ⊕ 0
• Feathers McGraw: aF = bBC ⊕ bCA ⊕ 0

5. Sign and Announce

Each agent signs their announcement:

σX = {|aX|}KprX

They publish: (aX, σX)

6. Final XOR

All announcements are XORed:

A = aW ⊕ aG ⊕ aF

• If A = 0, then no one paid
• If A = 1, then exactly one person paid

No one knows who, because shared bits obscure the mX.

---

Summary of Benefits

Feature	How it’s Achieved
Secrecy	Shared bits derived securely using DH + Hash
Verifiability	Digital signatures used for announcements
Anonymity	XORing shared bits hides who paid
Traceability	Public keys validate origin of each announcement
Public-only	All messages use open/public communication

---

Conclusion

This version of the Dining Cryptographers Protocol meets modern cryptographic expectations:

• Works over public channels
• Allows verifiable attribution
• Maintains the core anonymity guarantee

It shows how classic privacy protocols can evolve with practical cryptographic tools.