Concordia there is an even output then







Concordia Institute for Information
Systems Engineering



Foundations of Cryptography (INSE

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!

order now



Dining Cryptographers Problem


Submitted to

Prof. Jeremy Clark


Submitted By

Siddharth Gandhi

Student Id – 40059762


Date – 20th December, 2017



In the
increasing use of internet, it has increased the treat of privacy to the users.
It is nearly impossible to keep confidentiality of who has sent the message and
to trace down the origin of the message. In this paper we will go through one
of the most powerful protocol – Dining Cryptographers protocol. The
unconditional security provided in “The Dining Cryptographers Protocol” in
based on the use of one time key or the use of public key. The main objective
of this paper is to study the general approach and some practical


According to the Dining
Cryptographers Protocol, presented by David Chaum 1, there are three
cryptographers who went to one of their favorite restaurant for dinner. The
waiter there informs them that the arrangement of their dinner is already done
and the bill for the dinner is already paid. “It could be one of the
cryptographers who paid the bill or the NSA (National Security Agency) has paid
their bill.” 1 The cryptographers respect the decision to pay the bill
anonymously but they wanted to know if NSA had paid the bill. They try to
resolve the uncertainty by following the below protocol:

Each cryptographer flips an unbiased
coin such that only he and the cryptographer to the right of him knows the
value of the coin flip. Then each cryptographer states the value of the coins
he sees, i.e., whether the one he flipped and the one his left side neighbor
flipped were same or different.

If any of the cryptographer is
paying the bill he will call out the opposite of what he saw. If there is an
odd number of difference on the table it means that one of the cryptographers
is the payer of the bill. If there is an even output then NSA has paid their
bill. This protocol only lets them know that the bill is paid by one of the
cryptographer or NSA but does not tell anything about who has actually paid the

For example, that after the coin tossing, cryptographer A and B
share a secret bit 1, A and C share 0, and B and C share 1. Supposing
none of the cryptographers paid, then A announces 1 XOR 0=1, B announces 1 XOR
1=0, and C announces 1 XOR 0=1. On
the other hand, if A paid, he announces – (1 XOR 0) =1

Fig. 1:  In the above figure the Cryptographer 1 has
paid the bill and announces the value negative of the coin flips he has seen.

Let us consider the dilemma that
the cryptographer who did not pay bill wanted to find which cryptographer paid
the bill, there would be two cases.

Case 1, if the coin flips he saw
were same and one of the cryptographer said same and the third cryptographer
said different. “If the hidden outcome of the cryptographers who said different
were same then the cryptographer who said different is the payer;” 1 where as
if the cryptographer who said same but saw different outcomes, then the
cryptographer who said same is the payer. But since the flip of the coin is
unbiased thus the probability of both the outcomes are equal.

Case 2, if coin flips the
cryptographer saw were different and both the other cryptographers also says
that the coin flips they saw were also different, it is not possible for any of
the cryptographer to find the actual payer of the bill since the probability of
getting the same outcome or different outcome of the coin flip is equal.

General Approach

In the Dining Cryptographers
protocol the number of participants can be any number more than one. And each
participant has exactly one secret key shared with all the other participants.  The output of each participant is sum, modulo
of two, of all the keys he shares with the other participants 1. If any of
the participant wants to transmit the message, then he will announce the
negative of the output of what he has, or else he would announce the output as
it is. The Global output is modulo two sum of all the outputs would be equal to
0 if no participant transmits any message as all the keys are shared twice
across the channel ( x XOR x = 0),
and would be equal to 1 if one of the participant decides to transmit any
message in the channel. draw key graph and explain it in general approach

Key Sharing

For DC-net protocol to be
untraceable, there must be either a completely secure key agreement channel
among the participants or the attacker must be assumed to have computational
limitations. All the participants in each round agree on new secret keys to get
unique output for each round. Different techniques have been proposed to share
keys among participants in real world. Chaum in 1 proposes two different ways
to share keys among participants. First, the participants can toss multiple
coins beforehand and store the resulting bits on two same disks and then share
one of the disk with the participant which allows participant to send messages
for longer time in future. In the other technique, he proposes to generate a
small key initially between two participants and then extend that key as needed
using pseudo-random generators. Keys can also be shared using public key
distribution technique such as Deffie-Hellman.

Sender Untraceability

Superposed sending is the technique used to achieve the sender
untraceability. For participants to send messages in each round, they should
first establish a key between themselves. The key graph below shows keys shared
among participants.

Here, each participant shares a secret key(K) with every other participant.
The vertices of graph indicate the participants and the edges show the keys
shared between the participants. The participants of the DC protocol announce
their outputs and these outputs are then combined to give a message. Suppose P
is the set of participants. P = {p1, p2,  .. pn} and they output their
results as R; the set of results output by participants is R = {r1, r2,
. . rn}. The key shared between two participants Px and Py
will be Kxy. Also, Kxy=Kyx. All these outputs
are combined to get the message m. m = r1 XOR r2 XOR r3…XOR rn. Thus, message can be
known by this protocol but the anonymity of the sender of that message is
preserved. The general formula to calculate the output for each of the
participant is written as:


Where Oi is the output for the ith participant,
Mi is the message that the person sends and sign is function that
gives -1 when ij and 0 if i=j and Ki,j is the key
that is exchanged between any two participants.

Sign (x)= -1 ,    
x<0              = 0 ,       x=0              = 1 ,       x>0

The sum of all the outputs Oi  is equal to the message Mi since
the summation of Oi would cancel the Ki, j

For example, if we take three participants
trying to share some message keeping the sender untracability, each participant
will share some key with each other K12 being shared between
participant 1 and 2, K13 being the key shared between participant 1
and 3 and K23 being the shared key between participant 2 and 3.

O1= K12 XOR K13

O2 = K12

O3 = K23 XOR K13

Thus the global sum of all the participants would be

S = O1 XOR

S = K12

S = M2

Reliable Broadcast

Reliable Broadcast is one of the
major contributor of Receiver Untraceability and it depends one 2 factors:

1.       Every
two-honest participant will receive same data.

2.       Each
honest participant will have same character received that is sent by an honest

The sender will send the data to
every other participant, it is more likely to be that all the participants are
real receivers. If the sender wants to that the message is confidential, he can
encrypt the message and broadcast it so that not every participant can decrypt
it and know the message. It is important for reliable broadcast that all the
receiver receives the correct message without any alteration, or else an
attacker can send a falsified message to know the real receiver. 5

There are two protocols for
attaining reliable broadcast:

1.       Physical
Reliable Broadcast,

2.       Byzantine
Agreement based on the Byzantine general Problem

Physical Reliable Broadcast: This type of broadcast is said to be
physical as it depends on the usable communication protocol. Like in the story 1
by D. Chaum where three cryptographers were physically sitting in a restaurant,
and the physical communication is guaranteed.

Byzantine General Problem: Unlike the physical presence of
participant where the physical reliable broadcast is guaranteed, there is
Byzantine General Problem introduced by Leslie Lamport, Robert Shostak, and
Marshall Pease. 4

It states that a group of
Byzantine army lead by several Generals went to attack the enemy city. All the
generals could talk with each other over messages only and agree to attack the
city at the same time to conquer the city. But there may be some disloyal
Generals as well who may prevent the loyal Generals to come to a common
agreement to attack. Their algorithm must guarantee the following properties:

All loyal generals decide upon the same plan of

A small number of traitors cannot cause the
loyal generals to adopt a bad plan.

Byzantine Agreement is the solution for
the Byzantine General Problem, where depending on the situation there can be
different solutions. For example, one of the solution suggested is oral
communication by the general to every other member such that the message is
sent correctly, and the receiver would get to know the who sent what. The other
solution suggested is that the sender signs the message he send to all

Fail Stop Broadcast: The main aim of fail stop broadcast is to stop
the communication once any of the genuine sender receives any incorrect
messages. In case any difference is detected the sender can stop the
communication by disturbing the superposed sending in the subsequent rounds.

Security issues


The communication network is
anonymous in DC protocol and the roles of the sender and receiver are kept hidden.
If the role of any participant is known by the attacker then there will be
security breach as the attacker will know the role of the participant and he
can figure out some pattern in the communication and thus, the communication
will no longer be anonymous. The attacker who is observing the communication
may collude with all the participants of the network except one. Once, the
attacker colludes with all the participants; he will know the shared keys and
outputs of all the participants except one. Thus, the anonymity of the one who
is not included in collusion will be broken and it will result in breach of
security. 3


The participant in the DC
protocol or the malicious cryptographer can try to jam the network and disrupt
the communication between other participants by sending random bits. These
random bits affect the final output and disrupts the communication. In real
system there is no practical solutions for disruption because any participants
can continuous to disrupt the system. However, the genuine non-disrupters can
help in stopping the disrupters from disrupting the system. There are various
methods by which non-disrupters can do so:

Making the key-sharing graph public

The output of each participant is agreed in such
a way that no participant can change their output after seeing others output
for any round

There can be some of the round that contains
inversions such that the untraceablity of any participant is not compromised.


to the solution of Dining Cryptographers deals with the sender untraceability and
the receiver untraceability. In the sender untraceability or superposed sending
the keys are shared between each pair of participants. It is hard to obtain superposed
sending because for n participants the number of keys shared in each round would
be n(n-1).  Reliable Broadcast or receiver
untraceability depends on each honest participant. It depends on physical reliability
and Byzantine agreement. The major security issues in dining cryptography are collusion
and disruption. It is also difficult to      stop any
disrupters from sending false communication and disrupt the network but non-disrupters
can help system from avoiding disruption.



1 Chaum, D. (1988). The dining
cryptographers problem: Unconditional sender and recipient untraceability. Journal
of cryptology, 1(1), 65-75.

2 Bauer, J., & Staudemeyer,
R. C. (2017, June). From Dining Cryptographers to dining things: Unobservable
communication in the IoT. In Computer Aided Modeling and Design of
Communication Links and Networks (CAMAD), 2017 IEEE 22nd International Workshop
on (pp. 1-7).

3 Scholz, I. (2007). Dining
Cryptographers. The Protocol. In 24th Chaos Communication Congress,

4 Lamport, L., Shostak, R.,
& Pease, M. (1982). The Byzantine generals problem. ACM Transactions
on Programming Languages and Systems (TOPLAS), 4(3), 382-401.

5 Waidner, M. (1989, April).
Unconditional sender and recipient untraceability in spite of active attacks.
In Workshop on the Theory and Application of Cryptographic
Techniques (pp.
302-319). Springer, Berlin, Heidelberg.

6 Sender, C. S., & Franck,
C. (2008). New Directions for Dining Cryptographers