owned this note
owned this note
Published
Linked with GitHub
# New Directions for Dining Cryptographers - 2008
###### tags: `Tag(HashCloak - DC Net Readings)`
Authors: Christian Franck
Paper: https://secan-lab.uni.lu/images/stories/christian_franck/FRANCK_Christian_Master_Thesis.pdf
Definitions:
### Table of Contents
[toc]
:::info
>Abstract: In the dining cryptographers protocol [7], a malicious participant can disrupt communication by providing a wrong output. Existing techniques only allow to limit the damage to some extent. This is a major obstacle to the practical usage of the protocol. The objective of this thesis is to provide a better response to this problem. Our starting point are the ideas presented by Golle and Juels in [21], where outputs of algebraic structure are generated based on the Diffie-Hellman key exchange [12], and where non-interactive zeroknowledge proof techniques allow to prove the correctness of these outputs.
:::
## Ch 1: Introduction
#### What is this Thesis About?
> Anonymous communication is important to protect privacy and freedom of speech.
Anonymous communication is important to protect privacy and freedom of speech. Several concepts have been invented to allow anonymous communication over a public network. The strongest known concept is the dining cryptographers protocol, presented by Chaum in [7]. It guarantees unconditional (information theoretical) sender and recipient untraceability, but it is very inefficient and therefore considered to be unpractical.
![](https://i.imgur.com/euN8k60.png)
> A major obstacle to the practical application is that malicious participants may disrupt communication by providing wrong outputs.
As illustrated in Figure 1.1, the participants P1, P2, ..., Pn respectively announce the outputs O1, O2, ..., On. These outputs are indistinguishable from random outputs, but they allow to compute an anonymous message M, typically according to the formula: M = O1 ⊕O2 ⊕...⊕On. The anonymous message appears but the sender and the recipient remain unknown.
#### Why is this Interesting?
![](https://i.imgur.com/ZD1c3Yh.png)
> Currently, most anonymisation systems that are used in practice are based on mixes. This concept was proposed by Chaum in [9]. As illustrated in 1.2, many senders send their messages to a common mix which shuffles the messages and forwards them to the receivers.
The problem is that this mix concept is weak:
1. First, participants must trust the mix owner, who knows which participant is the sender of a message.
2. The messages of all participants must be equal in size otherwise a global observer may deduce who is the sender of a message, by comparing the size of the messages entering and leaving the mix.
> This thesis starts from the dining cryptographers protocol, which is very strong and very inefficient, and then tries to make it more efficient. This thesis is about improving the dining cryptographers protocol itself.
#### What is the proposed solution?
The key contribution of this work is the presentation of verifiable superposed sending, a new technique which allows participants of the dining cryptographers protocol to generate verifiable outputs. We use a new kind of reservation phase which provides all participants with a digital pseudonym of the sender. Based on the ideas presented by Golle and Juels in [21], zeroknowledge proof techniques allow honest sender to prove that their outputs are correct, without who is the sender.
## Ch 2: Anonymous Communication
> This chapter is an introduction to anonymity and untraceable communication. We present existing concepts for untraceable communication, and explain what we expect from a protocol to obtain strong anonymity. We conclude with an introduction to mixnets.
![](https://i.imgur.com/VDNYJnA.png)
### 2.1 Anonymity and Untraceable Communication
> We want anonymity to protect our privacy against people who could use personal information about us to harm us. This is particularly important in many critical areas like voting, freedom of speech, treatment of medical data, financial data and similar.
One possibility to achieve anonymity is to physically access the network in a way that nobody can associate the usage of the access point to your person. Many methods to protect our privacy are expensive to realise and some are not legal. We
would prefer to have anonymity while using our own internet connection. This is why we need protocols for untraceable communication.
**Untraceability** means that people within the group will be able to communicate in a way that nobody can tell who is communication with whom. It should not be possible to follow the path of a message from one participant to another. This is the role of protocols for untraceable communication.
#### Anonymity Sets
> "Anonymity is the state of being not identifiable within a set of subjects, the anonymity set" [29].
The requirement to have an anonymity set is something special that makes anonymity differ from other security properties like secrecy or authenticity. As illustrated in Figure 2.1, we can distinguish between sender and receiver anonymity sets. Often all participants are into both sets, to allow bidirectional anonymous communication. Anonymity is not an absolute value, and one can have more or less anonymity. The maximal amount of anonymity that can be reached is dependent on the size of the anonymity set, as illustrated in Figure 2.2. The more people there are, the more anonymity one can achieve.
#### Related Concepts
* Pseudonymity: is the usage of a false name within a specific context.
* Plausible deniability: deniability means that an action could also have been made by someone else or could not have happened at all.
#### Fundamental Limitations and Other Problems
* Size of the anonymity set: If some action X was done anonymously, this means that nobody knows who has done X. However the group of all possible persons who could have done X is a finite number, and the degree of anonymity is related to the size of the group. This implies that there must be at least two entities in a group to achieve anonymity.
* Collusion of malicious participants: A problem is that if all the other members of the set work together, they can determine what a user is doing by exclusion. If several members of the set cooperate and share their information, this is called collusion.
* Detection of misbehaving participants: One fundamental problem of anonymous communication systems is the detection of misbehaving participants. Detection of the disrupters is difficult since everything is done anonymously.
### 2.2 Concepts for Online Communication
* Mixes: The mix concept was proposed by David Chaum in [9]. Multiple senders send their encrypted messages to a common mix, which decrypts and shuffles the messages, and forwards them to the receivers. This way it is difficult to link one message to one sender. This is illustrated in Figure 1.2. There is the possibility to add encrypted information to the message that will allow the receiver of the message to respond via a special return mix. This will not compromise the anonymity of the initial sender.
* Crowds: Presented by Reiter and Rubin in [30]. To become a member of a crowd, the user must register at a central server. The members of a crowd are called Jondos. A Sender creates a packet containing a message and the address of the intended recipient. This packet is then randomly forwarded from one Jondo to another, and finally sent to the recipient. Each intermediary Jondo throws a coin to decide if he should forward the message to another Jondo or to the recipient.
* Onion routing: Presented by Goldschlag et al. in [19]. A sender sends his message through several onion routers. He selects a path and encrypts the message several times. Each onion router decrypts one layer, and forwards the packet to the next router. The messages is routed through all the onion routers and finally sent to the destination.
* The dining cryptographers: The strongest known concept is the dining cryptographers protocol, presented by Chaum in [7]. It guarantees unconditional (information theoretical) sender and recipient untraceability, but it is very inefficient and therefore considered to be unpractical.
### 2.3 Attacker Models, Trust and Strong Anonymity
* Dolev-Yao: In the Dolev-Yao attacker model [14], the attacker is the network. It is assumed that every message that is send over the network is forwarded by the attacker. He can observe, create, drop or modify all the packages he wants. This model is often used to formally verify security protocols.
* Trust: Chaum’s mix concept only works, if the mix owner is assumed to be honest. Senders must trust the mix owner. If the mix is operated by an attacker, he knows everything. A possibility to approach (and eliminate) the problem of trust is to send message through a sequence of mixes. This is then called a mixnet, and we will see this in the next section.
* Strong Anonymity: Ideally we would like to have a system, which can guarantee anonymity against a Dolev-Yao attacker, without requiring trust in any third party. This is what we will call strong anonymity. The only concept that offers this level of security out of the box, is the dining cryptographers protocol. Unfortunately it is not practical as such, because it is too inefficient. Especially the problems related to malicious participants disrupting the communication are not solved in a satisfactory manner.
> Therefore systems used in practice are based on mixnets.
### 2.4 Mixnets
To avoid that senders must trust one single mix owner, often in practice a mixnet is used, wherein a set of messages is decrypted and shuffled consecutively by a set of mixes M ix1, M ix2, ..., M ixk. If there is one honest mix in the mixnet, messages will be shuffled and be untraceable. Trust can be completely eliminated, if each sender owns one mix. This gives each sender the opportunity to shuffle the whole set of messages, ensuring that the messages are honesty shuffled at least once. However, this is expensive in terms of bandwidth usage, and in terms of latency.
* Evolution of Mixnets: The evolution of cryptography has lead to new types of mixnets. This has been a very active area of research in the last 20 years.
* Early Mixnets: In a mixnet based on Chaum’s initial approach, senders encrypt their messages using a public key cryptosystem. As a message must be encrypted once for each mix, messages are intially very large. On their way through the mixnet, one layer of encryption is removed at every mix, which makes the packages shrink at every mix. This is not very efficient, because the packages are initially be very large.
![](https://i.imgur.com/UrfcJRP.png)
* Reencryption Mixnets: Reencryption mixnets use homomorphic encryption schemes, as described in appendix A.3.2, which allows to encrypt a message multiple times, without increasing the packet size. This principle was first presented by Park et al. in [25]. This requires less bandwidth, since the initial packets are kept small.
* Verifiable Mixnets: Verifiable Mixnets prevent a malicious mix server from manipulating the packets. Cryptographic proof techniques are used to construct a proof that the set of packets leaving a mix is a permutation and reencryption of the packets entering the mix. Zero knowledge proofs allow the verify that the packets were correctly mixed, without revealing the permutation. These types of mixnets are expensive in terms of computation.
### 2.5 Summary
> We want anonymity to protect our privacy.
Anonymity is the property of an element to be indistinguishable within a set, the anonymity set. Untraceable communication is communicating while making it impossible to follow the path of the message. Different concepts exist to realize untraceable communication. Some do not resist a strong attacker, others require trust in a third party. The dining cryptographers protocol is the strongest known concept, but it is not used in practice. In a mixnet, a list of messages is sent through a sequence of mixes. At each mix, the messages are shuffled. Mixnets are currently the most widely used anonymisation systems.
## Ch 3: The Dining Cryptographers
> The dining cryptographers protocol was described by Chaum in [7], and allows to achieve unconditional sender and recipient untraceability.
### 3.1 The Story
> Chaum presents his protocol with the following story (Illustrated in Figure 3.1). Three cryptographers are dining in a restaurant, and the bill was paid anonymously. They want to find out if one of them paid, or if it was their employer, the National Security Agency. If it was one of them, they want this person to remain anonymous, and therefore they decide to run the following protocol. Each cryptographer flips a coin and shows it to his right neighbour. Then everybody compares the coin on his right and the coin on his left and announces "same" or "different". Normally, there should be an even number of people which announce "different". Now, if one of them is paying, he will lie and announce the opposite of what he normally would. This will result in having an odd number of participants announcing "different". If this is the case, everybody knows that one of them lied, but nobody can tell who is the liar. So this allows to determine if one of them paid, while keeping this person anonymous.
![](https://i.imgur.com/JGRLqCu.png)
![](https://i.imgur.com/XA2YpX1.png)
![](https://i.imgur.com/NzLBk9O.png)
### 3.2 Superposed Sending
> The technique used to achieve sender untraceability is called superposed sending.
The participants P1, P2, ..., Pn respectively announce their outputs O1, O2, ..., On. Each value is indistinguishable from a random value, but the combination of all these values allows to obtain the anonymous message. The message M is obtained by a computation of the form: ![](https://i.imgur.com/Mh5vrba.png)
Which participant is the sender remains unknown.
**Key graph** For each round of superposed sending, pairs of participants must first establish secret keys.
* A key graph K represents which participants share a secret key. The vertices of the graph are the participants, and the edges indicate which participants share a secret key.
![](https://i.imgur.com/8ViiOHO.png)
> Figure 3.3 shows an example of a key graph with 5 participants. Any biconnected graph will work, but a complete graph offers the best protection against a collusion of malicious participants.
A secret key Ki,j is a random element of a group ![](https://i.imgur.com/s94V9He.png)
and we define that Kj,i = Ki,j . We also define Si = {k : {Pi, Pk} ∈ E}, which means Si is the set containing the indexes of the participants which share a secret key with participant Pi.
![](https://i.imgur.com/AljwzUX.png)
**Computation of Outputs** The participants compute their outputs based on the secret keys.
* The function sign(x) is 1 for x > 0, and −1 otherwise. Each participant Pi, except the sender, computes his output Oi with:
![](https://i.imgur.com/FtzAw4y.png)
* The sender Pi sends the message M. He computes his value Oi, using the secret keys he knows, according to:
![](https://i.imgur.com/uv8FF5C.png)
An example is given in figure 3.4. One can see that every key is used twice. One participant uses the key itself (Ki,j ), while another participant uses the inverse of the key (K−1 i,j ). The combination of all the outputs Oi combines of all the Ki,j and K−1 i,j elements. Therefore the message M is obtained by computing ![](https://i.imgur.com/nMFP1qK.png) As ![](https://i.imgur.com/GUa0NRG.png) all the secret keys cancel and only the message M remains.
#### 3.2.1 Key Establishment
> In order to obtain different outputs for each round, the pairs of participants must agree on new secret keys for each round.
From a conceptual point of view, participants secretly toss coins over a secure channel. Different techniques have been suggested to realize practical protocols.
#### 3.2.2 Reservation
> In one round of superposed sending, only one participant may send a message, otherwise messages collide. Therefore, rounds should be reserved prior to transmission.
Several techniques have been suggested for the anonymous reservation of rounds. After the reservation, each participant knows which rounds he can use, but does not know who is using the other rounds. Normally several rounds are reserved at a time. Such a set of rounds is called a transmission slot. We present now a brief overvier of various reservation techniques that have been suggested:
* Chaum’s Reservation Vector
* The reservation technique suggested by Chaum in [7] is to use a vector full of 0 bits, where each participants would randomly set one bit to 1.
* Participants use superposed sending with addition in GF(2).
* The resulting vector appears after adding all the outputs.
* By looking at the resulting vector, every participant can tell how many 1’s there are on the left of his 1 and thereby determine the transmission slot that he will use.
* If two or more participants happen to chose the same position, there is a collision and the whole reservation has to be repeated.
* The more participants there are, the larger he vector must be. Because of the birthday paradox, the required size of the vector grows rapidly with an increasing number of participants.
* Reservation based on the Factorisation of a Polynomial
* Each participant Pi sends a vector ![](https://i.imgur.com/9sXSBpD.png)
* The packets collide and one obtains the vector ![](https://i.imgur.com/08KO1hp.png)
* From this, a system of linear equations is build to find the coefficients of a polynomial P
* This polynomial is then again decomposed into factors which are ordered.
* The transmission slot that a participant receives, depends on the position of the factor related to his value Ai.
* R is random value which will be used to shuffle the results to prevent participants from influencing their position.
![](https://i.imgur.com/O92USs0.png)
* Reservation Map Technique
* The reservation map technique was described by Pfitzmann in [27] and by Waidner in [34].
* It is based on superposed sending, where G is an additive group modulo m.
* Each participant chooses one position in a vector of k elements, and sends a 1 in that position.
* In all other positions he sends 0.
* The resulting vector will indicate how many participants chose a particular position.
For example if 3 participants send a 1 in a position, the result will contain a 3. The positions which contain a 1 indicate a successful reservation, all others are skipped. Participants then use the transmission slots accordingly.
* Reservation based on Superposed Receiving
* Superposed receiving is a transmission technique described by Pfitzmann in [28], and by Waidner in [34], which takes advantage of the algebraic properties of superposed sending.
* Superposed sending is used with an additive group, such that a collision is the sum of all values.
* The transmission of n messages takes n rounds.
* In the first round, all participants send their messages and create a big collision. This gives the total sum of all values.
* In the next round, only the participants who had a value below the average send their messages, which divides the total sum into two sub sums.
* This process is repeated until all the messages have appeared.
* To compute the average, it must be known how many messages are colliding.
* Therefore participants send a vector (1, Mi) instead of just Mi.
* Reservation based on superposed receiving is done by having each participant chose a random number as his message.
* Then, similarly to the order of the bit in Chaum’s vector, the relative position of his number will tell a participant which transmission slot he can use.
* Reservation using a Mix Network
* In [33], Studholme and Blake suggest to make reservations for the Dining Cryptographers using a mixnet to create a secret permutation. Each participant secretly creates a ciphertext. All these ciphertexts are sent through a mixnet, and a vector is obtained, which contains a permutation and a reencryption of these ciphertexts. Eachparticipant can then recognise his ciphertext in the list, and use the corresponding transmission slot.
#### 3.2.3 Detection of Disrupters
> Malicious participants may disrupt communication by providing the wrong values. Such participants are called disrupters. The detection of these is difficult, because of the anonymity of the protocol.
* Trap based detection
* Presented by Chaum in [7] and refined by Waidner in [34]; the principle is that in case of disruption, an investigation phase is started, in which each participant reveals his secret keys and explains how he computed his output.
* This does however also reveal the sender and his message, and can therefore only be used for rounds which contain no message.
* Therefore, participants use some of the rounds they reserve as trap rounds, in which they will not send any message. If a participant detects that one of his trap rounds was disrupted, he reveals that it was trap and an investigation phase is started.
* A problem is that if a round containing a message is disrupted, then the disrupter can not be detected.
![](https://i.imgur.com/odnAJsz.png)
> The different phases of Chaum’s protocol improved by Waidner are illustrated in detail in Figure 3.6.
1. First, participants establish the secret keys that they need for the superposed sending.
2. Then follows a reservation phase which is preceded by a commitment phase.
* A commitment phase ensures that an attacker cannot change his output after seeing the output of another participant.
3. After the reservation phase, participants commit to encrypted trap announcements, which contain the information they want to use a round as a trap or not.
4. After this comes a palaver phase, in which participants verify if the reservation and the announcements are accepted by everybody (If nobody noticed a disruption).
* If there are complaints, an investigation phase is started where all the keys used in the first phases are revealed.
* If there are no complaints in the palaver phase, participants commit to their outputs for the sending phase.
5. In the sending phase, the messages are sent, trap rounds are left empty.
6. After the sending phase, there is another palaver phase, where participants may ask for investigation if one of their traps was disrupted.
7. Participants who asked for an investigation then open their trap announcements, to prove that the disrupted rounds are their traps, and everybody has to reveal the keys he used for those rounds, and to explain how he computed his output.
* Zero-knowledge proof techniques: In [21], Golle and Juels present two protocols which are based on zero knowledge proofs.
* The first protocol: is called the Short DC-net protocol, because it is designed to send single elements. Participants generate secret keys that have an algebraic structure. Each participants sends a vector containing n outputs, and can prove that n−1 of these outputs are correct and do not contain a message. This restricts a disrupter to disrupt 1 out of n rounds.
* The second protocol is called the Long DC-net protocol, and it can be used for longer messages. It is based on technique which is comparable to randomised partial checking [22]. Again, each participant sends a vector containing n outputs, and a participant can generate a proof that a high number of his outputs are correct.
### 3.3 Reliable Broadcast
> Receiver untraceability is based on reliable broadcast [34], which is defined by the following two properties [26]:
> * Every honest participant receives the same data.
> * If the sender is honest, every honest participant receives the (unfalsified) data sent by the sender.
The sender broadcasts his message to all potential recipients, so every recipient is equally likely to be the real receiver. If confidentiality is required, the sender can encrypt the message, so that only the unknown recipient can decrypt it. Reliable broadcast is important to be sure that every receiver receives the same unfalsified message. Otherwise an attacker (which could be the sender) can send different messages to different receivers, in order to identify the real receiver by his response.
**Physical Reliable Broadcast**
In the original story [7], the three cryptographers are sitting in a star restaurant and the reliable broadcast is physically guaranteed.
**The Byzantine Generals Problem**
In case the broadcast is not physically guaranteed, like in the story of the three cryptographers in the restaurant, we have the Byzantine Generals problem, which is introduced by Lamport et al. in [24]. Several generals hold Constantinople under siege. To conquer the city they must attack all the same time, otherwise they will lose the battle. So they must agree on what time to attack. Their problem is that they can only send messages to each other, and there can be traitors who intercept or modify the messages, so they are not sure if each general will really be there at the desired time.
**Byzantine Agreement**
Byzantine Agreement protocols are solutions to the Byzantine Generals problem. They are used to realize a reliable broadcast on networks which do not physically guarantee reliable broadcast. Depending on the initial assumptions, different solutions exist.
> One example is a computationally secure protocol suggested by Dolev and Strong in [13]. The sender signs his message and sends it to all other particpants. Recipients create signatures of the messages they received and send them to other participants.
**Fail-Stop Broadcast**
The idea of fail-stop broadcast is that the communication is interrupted as soon as two honest participants receive different messages. Waidner shows in [34], how this can be done in the Dining Cryptographers protocol. The keys for a round of superposed sending are computed such that they depend completely, but not exclusively, on the values that a participant received in the previous round. If two participants receive different values, their keys will become unsynchronised, and it will not be possible to transfer a message anymore. The computation of the message will then just return a random value.
### 3.4 Bandwidth Usage
> The dining cryptographers protocol combines superposed sending and reliable broadcast.
Superposed Sending requires each participant to generate one output per message, and Reliable Broadcast requires each participant to send his output to all other participants. For n participants, this means n(n − 1) bits are sent for one message bit. This is expensive for a high number of participants.
It is more efficient if participants locally combine their outputs and then forward the results only. In [7], Chaum gives the example of a ring network, in which each particpant combines his output with the value received from his predecessor, and then forwards the result to the next particpant. After one round, the message is computed, and it takes a second round to forward the message to all participants. This reduces the cost to 2n bits per message bit.
> In [31], Goel et al. use a star topology to achieve the same effect. One of the participants collects all the outputs, computes the result and forwards it to the other participants. The cost is again 2n bits per message bit. The problem of these more efficient techniques is that there is no broadcast from the sender to recipients anymore, and an intermediary may falsify
the message.
## Ch 4: A Verifiable Dining Cryptographers Protocol
We first present this method based on the assumption that a reservation phase provides participants with a digital pseudonym of the sender. Then we see how such a reservation can be realized. Finally we show what are the possible effects for reliable broadcast, and conclude by describing possible applications of the new methods.
### 4.1 Verifiable Superposed Sending
> In this section we present how a new method for superposed sending, which allows to generate verifiable outputs.
#### 4.1.1 Purpose
> A major problem of superposed sending (introduced in section 3.2) is the disruption of the transmission by malicious participants who provide a wrong output.
We want a superposed sending technique which allows participants to generate verifiable outputs. Each participant should be able to prove the correctness of his output.
![](https://i.imgur.com/BZ30P49.png)
This is illustrated in Figure 4.1. This will discourage malicious participant from providing wrong outputs, as it will be possible to detect them immediately.
#### 4.1.3 The Short DC-Net Protocol
> It is possible to prove statements about outputs if they are of algebraic structure. This idea was presented by Golle and Juels in [21]. We use their 'Short DC-Net Protocol' as our starting point.
**The Idea**
Participants establish their secret keys using the Diffie-Hellman technique. A multiplicative group ![](https://i.imgur.com/Qba5QdP.png) is known to all participants. Each participant Pi has a private key ai and a public key g^ai . The secret key established between Pi and Pj is then ![](https://i.imgur.com/lqNglTS.png) We define ![](https://i.imgur.com/UVqpZPi.png) as the set containing the indexes of the participants with whom Pi is sharing a secret key. The function sign(x) evaluates to 1 for x > 0, and to −1 otherwise. Each participant Pi, except the sender, computes his output by multiplying all his secret keys:
![](https://i.imgur.com/Pjv68gw.png)
This output has an algebraic structure. More precisely, Oi is of the form ![](https://i.imgur.com/fVvzO1n.png) where Y can be computed by everybody. We can use this property to prove statements about Oi using zero-knowledge proof techniques, as we will see later. First we have to see how we can extend the technique to multiple rounds.
**Multiple Rounds**
The Diffie-Hellman based technique that was just described allows to generate one set of secret keys, but if we have multiple rounds, we need a new set of secret keys for every round. To extend the technique to multiple rounds, we use the multiplicative groups ![](https://i.imgur.com/JaOdoxk.png) and H, and a bilinear map ![](https://i.imgur.com/BbfR6Gh.png) Additionally a public random generator is used, which provides a random value R ∈ G for each round. The secret key established between Pi and Pj is then ![](https://i.imgur.com/PFwtJ3t.png) The so obtained secret key is still based on the Diffie-Hellman technique but it is randomised for every new round. If Pi is not the sender, then his output is a multiplication of all his secret keys:
![](https://i.imgur.com/4xkJPzL.png)
This output has again the desired algebraic structure, so that we can prove statements about it using zero-knowledge proof techniques, as we will see next.
#### 4.1.4 Remaining Problems
The Short DC-Net protocol presents very interesting ideas, but it has the following problems.
1. A first problem is that no reservation is made, and collisions of messages are accepted. Even it was extended with a reservation phase, a disrupter would be able to disrupt 1 round out of n, while remaining undetected.
2. A second problem is coming from the bilinear map, which is used to generate secret keys for multiple rounds. The only currently known ways to realize a bilinear map are based on elliptic curve cryptography, and then the group H is a group based on the elliptic curve. The secret keys and the outputs are elements of H, but our messages usually are in Zp. The mapping of messages from Zp to H and back again is not trivial, and we would like to avoid this.
#### 4.1.5 Our Solution
> The Short DC-Net Protocol introduces interesting techniques, but because of the remaining problems we need something else.
This leaves us with the questions:
* Can we create outputs of algebraic structure for multiple rounds without using a bilinear map?
* Can we add a reservation phase, and consider the reservations in the proofs?
We will now see what is possible if we assume that we have a digital pseudonym of the sender.
**Assumptions**
![](https://i.imgur.com/QyEJhrl.png) be a group in which the Decision DiffieHellman problem is assumed to be infeasible. We assume that ![](https://i.imgur.com/JaOdoxk.png) is known to all participants. Each participant Pi has a private key ai and a public key ![](https://i.imgur.com/hUvpyiZ.png) Let us assume that from a reservation phase we have a digital pseudonym of the sender ![](https://i.imgur.com/ptRVM21.png) which known to all participants, and only the sender knows the private key x.
![](https://i.imgur.com/7qxzifm.png)
**Computation of Outputs**
Using the digital pseudonym ![](https://i.imgur.com/2fyJRvK.png), a participant Pi can establish a secret directly with the sender, and use this as his output:
![](https://i.imgur.com/SDLoXNC.png)
This output has the required algebraic structure. Furthermore, it is indistinguishable from a random output because the Decision Diffie-Hellman problem is infeasible in ![](https://i.imgur.com/wWV3OXY.png) Let ![](https://i.imgur.com/wQDT6BU.png) denote the set containing the indexes of all participants except the sender. The sender Pi computes his output to contain his message M, as follows:
![](https://i.imgur.com/xgdgIYp.png)
The message M can then be obtained by multiplying all outputs. An example is shown in Figure 4.2.
**Multiple rounds**
If for every reservation a new digital pseudonym is chosen, the outputs will be different for each round. The randomness is coming from the digital pseudonym.
> How are public keys derived in ETH2.0?
**Proving Correctness of Outputs**
An output Oi is correct if it has the form ![](https://i.imgur.com/vAt6a1Z.png) or if Pi is the sender. This means that either ![](https://i.imgur.com/e8oSaJQ.png)![](https://i.imgur.com/Y8WUgwd.png) or Pi knows x. Pi can prove that one of both statements is true, without revealing which one, by proving the following statement:
![](https://i.imgur.com/NhhElTa.png)
> How to prove this statement is given as an example at the end of appendix B.3. We have achieved our goal, the outputs are indistinguishable from random outputs, but verifiable.
#### 4.1.6 Long Messages
If the messages are longer, of the form (M1, M2, ..., Mk) instead of just M, then it is possible to create multiple outputs (Oi1, Oi2, ..., Oik) from one digital pseudonym.
Each participant Pi must have a secret vector ![](https://i.imgur.com/YLH5fX7.png) and a corresponding public vector ![](https://i.imgur.com/HjczZ28.png)instead of having only one private value ![](https://i.imgur.com/9vecWfR.png) and one public value ![](https://i.imgur.com/0FoTrnV.png) Then a new pair ![](https://i.imgur.com/vuY7LjV.png)is used for each output.
This allows to adjust the protocol to the desired maximal message size.
#### 4.1.7 Variations
> We assumed until now, that the message is computed as a multiplication of all outputs. As the sender knows the precise outputs of all other participants, other functions of the more general form M = f(O1, O2, ..., On) are also possible. The sender must then chose his output, such that the function evaluates to his message.
#### 4.1.8 Discussion
In our solution, all other participants use the Diffie-Hellman technique to establish a shared secret with the sender, while keeping the identity of the latter secret. This completely eliminates the need for pairs of participants to share secret keys. Outputs are indistinguishable from random outputs because of the Decision Diffie-Hellman assumption. The sender has more knowledge than before, when the outputs were generated based on a keygraph, as he knows in advance the precise outputs of all other participants. This is not a problem, since he is the sender himself. Any other participant does not have more information than before.
![](https://i.imgur.com/zyExc0K.png)
### 4.2 Reservation
> We assumed in the previous section that we had a reservation phase which provides the participants with a digital pseudonym of the sender. In this section we will see how this can be realized.
#### 4.2.1 What We Need
> Existing reservation techniques secretly inform each participant if he is the sender or not. We need a reservation technique which informs each participant if he is the sender or not, and additionally provides every participant with a digital pseudonym of the sender. This is illustrated in figure 4.3.
![](https://i.imgur.com/cK7CIWv.png)
#### 4.2.2 A Mixnet based Reservation
> We present a solution which is based on a mixnet (illustrated in Figure 4.4).
Each participant first privately generates a digital pseudonym, then participants use a mixnet to obtain a shuffled list of all their digital pseudonyms. A mixnet is the best known practical method to obtain such a shuffled list.
**Description**
Each participant Pi secretly chooses a number ![](https://i.imgur.com/2pbCq3j.png) and computes ![](https://i.imgur.com/N3tPkl1.png) All participants send their values ![](https://i.imgur.com/GPy7hII.png) through a mixnet to get ![](https://i.imgur.com/5hmORjq.png) a permutation of ![](https://i.imgur.com/AgnlYRH.png) To obtain computational security, a mixnet is used, in which each participant shuffles the list one time, such that no trust in a set of mix owners is required. The values ![](https://i.imgur.com/tEyShOv.png) are the digital pseudonyms and determine the order in which the participants will send their messages. Each participant Pi recognises his ![](https://i.imgur.com/EekOJI2.png) and knows which round he can use to send his message.
To prevent an attacker from reusing a digital pseudonym from another participant, each participant Pi should generate a non-interactive proof of knowledge of the secret key corresponding to his digital pseudonym ![](https://i.imgur.com/c3QX3QE.png) ![](https://i.imgur.com/Fb0ehNf.png) and send a packet through the mixnet which contains the public key and the proof of knowledge, so that other participants can verify that the participant who submitted a digital pseudonym also knows the corresponding private key.
> After receiving the list t (D1, D2, ..., Dn), participants verify that everybody received the same list, and each participant Pi verifies that his value ![](https://i.imgur.com/wOuqZja.png) is in the list.
**Discussion**
> For a computationally secure protocol, a mixnet seems to be the best choice.
A mixnet is naturally suited to do the reservation, since the keys are small and of equal size. Each participant mixes the list one time, so that no trust is required.
The mixnet is only used to shuffle randomly generated keys, and no message information is send through the mixnet. This has two advantages.
1. First, reservations can be made long time before the actual transmission of a message. Even if the reservation is a high latency process, this has no negative impact on the latency of the transmission of a message.
2. Second, it is not necessary to use a verifiable mixnet, with zero knowledge proofs about the inputs and the outputs of each mix. A verification at the end is sufficient. If a participant sees that his key is not in the list as it should, he can initiate an investigation phase. In order to find the misbehaving mix, all participants disclose the values they used. This does not compromise any message information, and the disclosed keys can just be ignored and replaced by new ones. This means that a simple reencryption mixnet can be used, which is easier to realize than a verifiable mixnet.
> A possible alternative could be a reservation based on superposed receiving, but it would be more complicated to realize.
### 4.3 Effects on the Broadcast
> The advantage of having a digital pseudonym of the sender for the broadcast, is related to what as described in section 3.4.
The sender can sign the message, and a recipient can use the digital pseudonym to verify the signature. This allows to realize efficient topologies, where for example one participant collects all outputs, computes the message and sends it to all participants. Because the message is signed, the intermediary can not replace the message with a fake message.
To obtain a reliable e broadcast, it is however still necessary to verify that everybody received the same message. In case the intermediary was the malicious sender, he could send different signed messages to different recipients.
### 4.4 Applications
> In this chapter, we describe how this can be used to realize systems for:
> * Electronic voting,
> * Low latency anonymous communication, and
> * Fast multiparty computation
#### 4.4.1 Electronic Voting
> Using the new techniques to implement a simple electronic voting system is straightforward. What is described next is illustrated in Figure 4.5.
1. First, the voters execute a reservation phase to obtain a list of digital pseudonyms. Each voter has one digital pseudonym in the list. This list is signed by all voters to ensure that the list is correct and that everybody has the same list.
2. Then, each voter generates a ballot which contains an output and a proof for each digital pseudonym. When a voter encounters his digital pseudonym, he can cast his vote. All outputs look like random outputs, so that the vote is not revealed. The proofs allow to verify that the voter behaved correctly.
3. Finally, all the ballots are combined and the votes appear. The votes are pseudonymously signed, so it is possible to use the list of digital pseudonyms to verify the pseudonymous signatures. This shows that each vote is originating from the voter who holds the secret key corresponding to the digital pseudonym. The signed list of digital pseudonyms and the list of the pseudonymously signed votes can be used to prove the correctness of the result to any third party.
> The advantages of the proposed system are that it is easy to implement, and that the result that can be used to prove the correctness of the results to a third party.
> A disadvantage is that every voter must submit his ballot, otherwise the votes cannot be computed.
![](https://i.imgur.com/itH8oqm.png)
#### 4.4.2 Low Latency Anonymous Communication
> We can also build low latency communication systems, using the techniques described in previous chapter.
**Reservation of Rounds**
As described previously, participants use a mixnet to anonymously reserve the rounds for transmission. In communication system, they just continuously generate new random keys and send them through the mixnet. There will be an initial delay until the first set of keys is coming out of the mixnet, but then each step provides a new set of digital pseudonyms.
**Transmission of Messages**
> For the transmission of messages, participants can use a star or a tree topology. The combination of an pseudonymously signed message and the proofs that the individual values are correct, allows to efficiently aggregate the values and broadcast the message. This is described in the next paragraphs, and it is illustrated in Figure 4.6.
* A message is pseudonymously signed by the respective sender.
* Intermediary nodes can then aggregate the received outputs with their own and forward the result.
* The participant at the root of the tree computes the message and verifies the signature.
* If the signature is not valid, an investigation phase is started and the participants must provide the proofs that their values were correct.
* If the signature is valid, then the pseudonymously signed message is sent to the other participants.
* Each participant uses again the signature to verify that the root did not cheat.
* This gives total bandwidth costs that are linear relative to the number of participants.
To achieve receiver untraceability, participants must ensure that all of them received the same message. Otherwise a malicious sender could generate several signed messages, and provide different participants with different messages. Therefore, after reception of the message, each participant generates a signature of the message he received and forwards his signature to all other participants.
![](https://i.imgur.com/rF5c7vG.png)
**Traffic Announcement**
> It is possible to announce the traffic, in order to efficiently use the available bandwidth.
This is especially useful for large messages. In a system without traffic announcement, as illustrated in Figure 4.7, a message is transmitted for each digital pseudonym, and all these messages are of the same size. In a system with traffic announcement, we will have two phases, illustrated in Figure 4.8.
1. First, we make traffic announcements, in which each sender indicates the size of his message.
2. Then, the messages are transmitted according to the announced sizes.
![](https://i.imgur.com/pt6dMuK.png)
![](https://i.imgur.com/BAbrVuM.png)
Participants which do not have a message to transmit do not unnecessarily waste bandwidth. The message size can be arbitrarily long, and the interval between the reservation (an traffic announcement) steps can be chosen. This allows to realize networks with a high number of participants, which use low bandwidth when nobody is sending a message.
**Comparison with Mixnets**
> The new solution is much more flexible than a mixnet of the same level of security.
It allows to obtain a better performance in terms of bandwidth usage and latency. A mixnet is sequential, and for n participants to achieve computational security (without trust), a mixnet will require n steps. The new solution works with any tree topology, so the latency can be chosen to be very low.
Mixnets also require to have one message from each participant, and the messages must all be of the same size. The new solution allows to use messages of variable size, and to use traffic announcement techniques to efficiently use the bandwidth.
#### 4.4.3 Secure Multi-Party Computation
> Another area of application is secure multi-party computation, first presented by Yao in [36].
Participants perform a computation where the input from each participant remains secret, and where only the result is publicly known. Sometimes intermediary results have to be passed through a mixnet. The sequential mixing is time consuming and slows down the multiparty computation. The techniques presented herein allow to realize mixing rounds with a very low latency, which makes these multiparty computations faster.
### 4.5 Summary
In this chapter we:
* Presented verifiable superposed sending, a computationally secure version of superposed sending, which allows participants to generate verifiable outputs.
* We used a digital pseudonym, which is a public key of the form gx, and only the anonymous sender know the corresponding secret key x. This digital pseudonym is very useful, as illustrated in figure 4.9.
* Participants use the digital pseudonym and the Diffie-Hellman key exchange to establish a shared secret with the sender, while keeping the identity of the latter secret.
* This allows to generate outputs of algebraic structure, which are indistinguishable from random outputs in a group where the Decision Diffie Hellman problem is assumed to be infeasible.
* The discrete logarithms based nature of the digital pseudonym and of the outputs allows to use standard proof techniques to prove statements about them.
* A participant can prove that he participated correctly, without revealing if he is the sender or not.
* The sender can also use his private key x to sign his message, and all other participants can verify the signature using the digital pseudonym. This allows combine computation and broadcast, which reduces bandwidth usage.
> For example one participant can collect all the outputs, compute the message and then forward it to the other participants.
* The pseudonymous signature allows other participants to verify that the intermediary did not cheat, and that the message is really coming from the sender.
* We saw how to obtain a digital pseudonym from the sender, using a reservation phase based on a mixnet.
> The new methods can be applied to electronic voting, low latency anonymous communication, and multiparty computation.
## Ch 5: Conclusions
Our initial problem was the detection of malicious participants which disrupt communication in a dining cryptographers protocol by providing wrong outputs.
* We presented the verifiable superposed sending technique, which allows participants to prove the correctness of their outputs, without compromising the anonymity of the sender.
* This solves our problem, as disrupters are now immediately detectable. The possibility to verify the correct behaviour of a participant, which exists for many years in mix based networks, is now available in the dining cryptographers protocol, which makes it a practicable alternative to mixnets.
* It can even outperform a mixnet in terms of latency, and it allows to use traffic announcement techniques to keep the bandwidth usage low.
* We presented possible applications of our new techniques in the fields of electronic voting, low latency anonymous communication and secure multi-party computation.
> Interesting activities for future research, are the study of the behaviour of our techniques in a real network. Especially the presented idea for a low latency anonymous communication systems, in combination with the presented traffic announcement technique, has the potential to generate interesting applications, for a high number of anonymous senders and recipients.