Antoine Guellier

Christophe Bidan

Nicolas Prigent

Homomorphic Cryptography-based Privacy-Preserving Network Communications

Keywords: Privacy, Anonymous, Network, Communications, Routing, Protocol, Homomorphic Cryptography

The development of worldwide communications, along with the dramatic increase of computational and storage capacities promise numerous benefits for societies in the years to come. For these systems to develop, security and privacy are necessary. This work presents a novel protocol for privacy preserving network communications, using homomorphic cryptography. The malleability properties of homomorphic encryption allows routing without ever disclosing the sender or receiver of a message, while resisting against basic end-to-end attacks. We first present our protocol in an abstract network model, and instantiate it for ad-hoc networks as a use-case example.

Introduction

Ubiquitous computing and worldwide communications are now part of the daily life of many individuals. We expect from these systems availability and security in order to provide reliable, confidential, and authenticated communications. Since the Snowden revelations [START_REF] Greenwald | No Place to Hide[END_REF], we also expect these systems to provide strong privacy. Nowadays, privacy preserving solutions are being adopted by a wider public. The Tor network [START_REF] Dingledine | Tor: The second-generation onion router[END_REF] is the most striking example, with more than 2 million users all over the world.

In general, in any information system, anyone can rightfully require her actions to stay private with respect to a set of chosen individuals. However, in a censored or totalitarian regime, a nonconformist reporter needs privacy to exercise her freedom of speech and communicate with the outside. Indeed, the simple fact of connecting to a blacklisted website or participating in a network exposes her to serious consequences [START_REF] Cohn | Yahoo's china defense[END_REF]. We focus on private communications within contexts where privacy is a necessity.

Anonymity and privacy for network communications begin with Chaum's MIX-nets [START_REF] Chaum | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF]. They inspired a large portion of works in this field [START_REF] Diaz | Taxonomy of mixes and dummy traffic[END_REF], although some may differ by modifying the number of MIX nodes or points in their functioning. Solutions introducing high latency between the sending of a packet and its reception are in general more resistant to end-to-end attacks and traffic analysis than their low latency counterparts. On the other hand, they are not suited for time-critical or interactive applications such as web surfing or SSH. For instance, Tor [START_REF] Dingledine | Tor: The second-generation onion router[END_REF] and more generally onion routing is a low-latency protocol, while Mixminion [START_REF] Danezis | Mixminion: Design of a type iii anonymous remailer protocol[END_REF] or MorphMix [START_REF] Rennhard | Introducing morphmix: Peer-to-peer based anonymous internet usage with collusion detection[END_REF] are protocols aiming at resisting against endto-end attacks and thus induce high latency.

Our main contribution is to propose a routing protocol that allows strongly private bidirectional interactive communication using homomorphic cryptography. To the best of our knowledge, it is the first routing protocol relying on this technology. By distributing the trust and using a proactive topology dissemination, our protocol resists both internal and external passive adversaries. In addition, our protocol not only hides the relation between senders and receivers, but also decorrelates every message from its sender and receivers everywhere in the network. We further provide an analysis of our protocol in terms of privacy, and study its integration in a real-world example.

Using homomorphic cryptography is motivated by the limitation of traditional cryptography. Indeed, homomorphic encryption (HE) schemes allows to publicly compute the encrypted value HEnc(f (m 1 , m 2 , . . . , m k )) for some function f using the individual encryptions HEnc(m i ) for i ∈ [0..k] [START_REF] Vaikuntanathan | How to compute on encrypted data[END_REF]. Because they are sufficient for our purposes, we solely consider partial HE schemes as Paillier or Elgamal [START_REF] Fontaine | A survey of homomorphic encryption for nonspecialists[END_REF].

The rest of the paper is organized as follows. In Sect. 2 we present the required tools, our models, and privacy goals. The protocol itself is presented in Sect. 3, while Sect. 4 discusses its properties and further improvements. Before concluding, Sect. 5 investigates its integration in ad-hoc networks [START_REF] Chlamtac | Mobile ad hoc networking: imperatives and challenges[END_REF].

Preliminaries

Cryptographic tools

Homomorphic encryption. This work makes extensive use the Elgamal cryptosystem [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF], for its good efficiency compared to other partial schemes and its scalar exponentiation capacity. To make this cryptosystem secure, it must work within a group G where the Decisional Diffie-Hellman (DDH) assumption holds, i.e. in a group of prime order q. Typically, G ⊂ Z * p is a subgroup of the multiplicative group of prime order p = k.q +1 for some integer k. Keys are of the form (pk, sk) = (h = g x , x) ∈ G × Z q where G = g . The encryption of a message m ∈ G is c = HEnc(pk, m) = (g r , m.h r ) ∈ G 2 for some random value r ∈ Z q . Elgamal supports multiplication of ciphertexts HEnc(pk, m 1 ) × HEnc(pk, m 2 ) = (g r1+r2 , m 1 .m 2 .h r1+r2 ) = HEnc(pk, m 1 .m 2 mod p), scalar multiplication ScMult(m 1 , HEnc(pk, m 2 )) = (g r , m 1 .m 2 .h r ) = HEnc(pk, m 1 .m 2 mod p), and scalar exponentiation ScExp(HEnc(pk, m 1 ), m 2 ) = (g r.m2 , m m2

1 .h r.m2 ) = HEnc(pk, m m2 1 mod p). Elgamal also supports re-randomisation: a ciphertext c = (c[0], c [START_REF] Catalano | Practical homomorphic macs for arithmetic circuits[END_REF]) for some message can be turned into a different looking, randomly distributed ciphertext for the same message: ReRand(pk, c) = (c[0].g r , c [START_REF] Catalano | Practical homomorphic macs for arithmetic circuits[END_REF].h r ).

Threshold homomorphic encryption. This work also uses a threshold homomorphic encryption (THE) scheme [START_REF] Damgård | A generalisation, a simplification and some applications of paillier's probabilistic public-key system[END_REF]. This type of homomorphic scheme can have its secret keys split into parts and distributed among several entities. As a result, for some threshold t, t entities or more can collaboratively decrypt ciphertexts, but less than t entities do not learn anything on the underlying plaintexts. In practice, key generation is performed by an authority who publicizes the public key and distributes shares of the secret key. Encryption is performed as usual, but decryption requires at least t share holders: each one locally decrypts the ciphertext using its share, and the outputs are then combined to recover the plaintext. Although any THE scheme may be suitable, this work uses the threshold variant of Paillier from Damgård et al. [START_REF] Damgård | A generalisation, a simplification and some applications of paillier's probabilistic public-key system[END_REF]. We denote encryption, decryption using a share, and combining primitives of a THE scheme by THEnc(pk, m), THDec(share, c), and THComb(ĉ 1 , . . . , ĉt ).

Note that in the rest of the paper, standard public-key encryption (PKE) is denoted by Enc, and symmetric-key encryption using key K is denoted {•} K .

Models and Goals

In the rest of the paper, we denote the node initiating a connection source, and its intended receiver destination. We should however mention that once the connection is established, information may flow in both directions. Nodes between a source and a destination relay the messages on a multi-hop path. We call a message any data transiting through the network, whether it is applicationlevel data or routing information.

Distributed trust. We rely on a distributed trust model, where any node may initiate, relay or be the receiver of a connection. By distributing the routing and removing all hierarchy among the nodes, we limit the consequences of node corruption. As there is no central network entity nor dedicated relays, corrupting a node brings very little power on the network as a whole. Actually, in our model, a node is unable to make use of the routing information on its own to run the protocol: it must collaborate with other network member. This suggests a corrupted node alone can not break the privacy of our protocol.

Privacy Goals. We refer to Pfitzmann and Köhntopp [START_REF] Pfitzmann | Anonymity, unobservability, and pseudonymitya proposal for terminology[END_REF] to define the concept of unlinkability in our setting: two items of interest are unlinkable if the adversary is unable to distinguish whether they are related or not. Using this terminology, we aim at ensuring the following properties.

Source/message unlinkability (SMU) Given a message m and a node S, it is impossible to distinguish whether S is the source of m or not;

Destination/message unlinkability (DMU) Given a message m and a node D, it is impossible to distinguish whether D is the destination of m or not; Source/destination unlinkability (SDU) Given two nodes, it is impossible to distinguish whether they communicated or not; Message/message unlinkability (MMU) Given two messages, it is impossible to distinguish whether they belong to the same source-destination pair communication or not;

Adversary Model. We consider two adversary models: a passive, non-collusive adversary internal to the network (also called honest-but-curious) (AdvI), and a global eavesdropper (AdvII). The first type of adversary participates in the network and is compliant with the protocol, but tries to get as much knowledge as possible on the network and other nodes. The second is still passive but more powerful, although it does not participate in the network. We do not give the adversary the ability to tamper with the network by dropping, replaying, or performing DoS or Sybil attacks for instance. Note that when considering information theoretic adversaries, notably against cryptographic primitives, we use the probabilistic polynomial-time (PPT) model. In any case, the goal of the adversary is to break the properties stated above.

Non-goals. We do not intend to provide an implementation-ready, nor an efficient protocol. Our first goal is to design a routing protocol for interactive communications achieving as much privacy as possible, and to extract interesting properties from it. Improvements in terms of efficiency and routing optimizations belong to future work. At last, protecting messages at the application level, although necessary, is outside the scope of this work. In particular, to resist against fingerprinting techniques on the Internet [START_REF] Nikiforakis | Cookieless monster: Exploring the ecosystem of web-based device fingerprinting[END_REF], content and identity should be protected end-to-end using SSL, application-level anonymization proxy or similar tools.

The protocol

Bearing in mind the desired privacy properties, we aim at designing a protocol that constructs and uses routes so that any node can contact any others at any time. This section describes our solution in two steps: it first shows how to disseminate topology without using nodes' identities, and then how the routing information is used to allow message sending.

Infrastructure

Initially, we consider an abstract network model where nodes are randomly placed and connected to their neighbors through a bare physical medium. Prior to describing our protocol, we introduce several values associated to a node X.

-ID X : X's network identity. It is a random value chosen by X prior to network setup, typically extracted from a large public set so that collisions between two nodes' identifiers occur with negligible probability. Generally speaking, nodes are willing to keep their identity concealed to other network members.

-(pk perm X , sk perm X ): the permanent key pair of X, possibly certified or publicly linked to X's identity.

-(pk X , sk X ): one of X's temporary key pairs, decorrelated from X's identity.

A node may own many temporary keys and dynamically generate them. src X : a value generated by X and used in its routing activity as a source (or relay) node. This value is unconditionally kept secret by X. dst X : a value generated by X and used in its routing activity as a destination node. This value is unconditionally kept secret by X.

We assume that prior to network setup, nodes willing to communicate exchanged their respective network identifiers, long term public keys, and possibly some auxiliary information, in the same manner as PGP keys are exchanged. In a very constrained context such as a censorship, a very high latency but highly private and secure protocol allowing the transport of small data, such as MIAB [START_REF] Invernizzi | Message in a bottle: Sailing past censorship[END_REF], can be used.

Routing while concealing identities

As we aim at concealing every node's identity, the main challenge we have to face is to transport a message to its intended recipient without knowing its actual identity. More exactly, we need to find a solution to route without network members knowing other nodes' network-wide identities. For this, we introduce the notion of local identifiers: instead of using a destination D's identity ID D to designate it, a node X uses a value derived from values belonging to D and itself. This value is collaboratively computed by X and D upon creation of the route. It should allow X to route messages towards D, but must prevent X from making the link with ID D . We denote this value LocalID X D and define it as:

LocalID X D = ID D .g srcX.dstD
, where g = G Because most of our operations are performed within the Elgamal group G ⊂ Z * p , the local identifiers and more generally all values in our protocol are computed modulo p (unless specified otherwise).

The local identifiers resolve the question of destination addressing. However, we also need a way for node to forward messages towards some local identifier on a multi-hop path. Indeed, message must travel from node to node in order to reach its destination. This implies that nodes must be able to address specific neighbors, still without knowing their identities. To enable private neighborhood discovery, we borrow a technique from Zhang et al. [START_REF] Zhang | Mask: anonymous on-demand routing in mobile ad hoc networks[END_REF]. It consists, for every pair of neighboring node in the network, in engaging in a Diffie-Hellman (DH) handshake in order to obtain a common secret, and to derive symmetric keys and link identifiers from this secret using cryptographic key derivation functions. A link identifier between two nodes X and Y, denoted L X,Y or L Y,X indifferently, acts as a MAC address in a traditional LAN. The key K X,Y associated to L X,Y serves to encrypt the message on the link. The particularity of this construction is that link identifiers and keys are only used one time. New ones are generated for each message (without the need for a new handshake), in such a way that it is impossible to relate two links (or keys) stemming from the same handshake. We now describe how to disseminate the topology without revealing any node identity. The general idea works as follows: when a node knows a route, it proposes this route to its neighbors. Said otherwise, it offers its neighbors to forward messages towards some destination for them. We make use of the elements defined above, and store routing information into two different tables: a Destination Route Table (DRT) and a Forwarding Route Table (FRT). To explain how these tables are filled, we use the example from Fig. 1 depicting a toy network of 4 nodes in a row.

In a first phase (in blue), D broadcasts to all its neighbors a route proposal : it proposes itself as destination. The goal of this route proposition is to make neighboring nodes aware of D and compute their local identifiers towards D. For this, the neighboring node Y generates a random number r, and computes ScMult r, ScExp(HEnc(pk D , g dst D ), src Y ) using the homomorphic properties of Elgamal. It sends a re-randomization of the result so as to ensure the ciphertext looks random, and a second half of a DH handshake (encrypted, to avoid manin-the-middle attacks). D decrypts the ciphertext, computes ID D .r.g dst D .src Y = r.LocalID Y D and sends the result back using the newly generated link identifier and key. Y recovers r.LocalID Y D and simply multiplies by (r -1 mod p). After these exchanges, D inserts a new entry in its FRT: L D,Y , K D,Y , null . The null value indicates the end of a route, and allows D to know that it is the intended receiver of messages incoming from the link L D,Y . As for Y, it inserts an entry in its DRT:

LocalID Y D , L Y,D , K Y,D , pk D , ReRand(pk D , HEnc(pk D , g dst D ))
, where the last value is simply a re-randomized copy from D's first message.

In the second phase (in green), Y proxies the route proposal from D to its own neighbors. D silently discards the proposal upon noticing it is the destination. The protocol is then very similar, except that the handshake is handled somewhat differently, and that Y must act as proxy between X and D because D is the only node able to decrypt X's answer. After the exchanges, Y inserts in its FRT L X,Y , K X,Y , LocalID Y D , and X insert in its DRT LocalID X D , L X,Y , K X,Y , pk D , ReRand(pk D , HEnc(pk D , g dst D )) .

Local id Link id Key Dest. pk Route prop.

LocalID Y D L (1) Y,D K (1) Y,D pkD HEnc(pkD, g dst D ) LocalID Y X L (1) Y,X K (1) Y,X pkX HEnc(pkX , g dst X ) LocalID Y S L (2) Y,X K (2) Y,X pkS HEnc(pkS, g dst S )
Destination Table

Link id Key Local id L (2) Y,D K (2) Y,D null L (3) Y,X K (3) Y,X null L (3) Y,D K (3) Y,D LocalID Y X L (4) Y,D K (4) Y,D LocalID Y S L (4) Y,X K (4)
Y,X LocalID Y D Forwarding Table Link ids with different parenthesized exponents stem from two different DH handshakes.

Fig. 2. Routing tables of Y after topology dissemination

This procedure is repeated, X proposing the route to S and X and Y proxying S's answer. In the general case, the procedure is repeated until the whole network is aware of D's presence. Furthermore, all nodes self-propose in the same manner as D to advertise their presence. As a result, each node's presence in the network will eventually be known by all, while its identity remains undisclosed. In our example, Y's tables are eventually filled as described in Fig. 2.

Using regular timeouts for table entries, and by repeating the proposals periodically, tables can be updated in case a node leaves or moves in the network. Although the complexity of this topology dissemination method is considerable (at least quadratic in the number of nodes in the network), it is only necessary to run it once at network setup.

Sending a message

At this point, each node has at least one route towards every other node. Note that completely anonymous communications are possible: the two tables allow any two nodes in the network to connect to each other using local identifiers. However, nodes can not know who they are connecting with, and the tables do not directly allow a source to reach a specific destination of its choice.

In order to allow connection of S to D without breaching privacy, S and D not being 1 hop neighbors, our solution makes S ask for help to another node. Also, we use a THE scheme with threshold t = 2 and make the assumption that there exist a pair of keys (pk * , sk * ) for this scheme such that pk * is publicly known, but sk * is unknown to all network members. However, every node X owns a share of the decryption key, sh X . The key pair and shares can be generated by a third party for instance. Finally, we suppose that, in addition to its identity and public key, D gave S the auxiliary value THEnc(pk * , dst D ).

Figure 3 describes the message sequence for S to be able to send a message msg to D. The first phase (in blue) is called route initialization: this is the part where S and X cooperate using THE to find a route from X to D 1 . Before running this protocol, S generates a random number r and computes C = ReRand(pk * , ScMult(r, THEnc(pk * , dst D ))). S and X then use their respective decryption shares sh S and sh X to cooperatively decrypt C. X obtains a 1 In the general case, S can choose any node in the network to play the role of X. blinded value of dst D , v = r.dst D , by using the THComb primitive. X then computes in the clear (g srcX ) v , encrypts it under one of its keys using Elgamal, and sends back the result C . If r and p -1 are co-prime, applying ReRand(pk X , ScMult(ID D , ScExp(C , r -1 mod (p -1)))) on the ciphertext C received by S yields a random-looking encryption of LocalID X D , which X is able to decrypt. X looks up in its DRT for a route towards this local identifier, and forwards the payload encrypted under D's permanent key. The second phase (in green) simply consists in table look ups. Upon receiving the message, Y looks up in its FRT to find the entry corresponding to L X,Y . Y recovers the relevant local identifier from this entry, looks up in its DRT for a route toward it, and forwards accordingly. If at any moment, a table look up fails, a notification is sent back. D knows it is the destination thanks to the null value in its FRT entry corresponding to L Y,D .

Discussion

This section explains our technical choices, analyses our protocol, and discusses its properties.

Interaction and THE in route initialization

In our model, the interaction in the route initialization is necessary in order to ensure DMU. Indeed, because of the way routes are built, the same local identifiers may be used both to emit or to forward a message to a given destination. Suppose a source S could, on its own, find a route towards a specific destination D, i.e. S can find the value LocalID S D in its DRT and knows it actually designates D. Later on, if S is asked to forward a message towards the same destination D, S will use the value LocalID S D (as explained in Sect. 3.3). Thus, S will infer the message is for D and break DMU. Therefore, for DMU to hold, a source S must not be able to initiate a communication alone.

The most straightforward solution is for S to hand all its messages to some other node X, and for X to forward messages towards the actual destination D. This means that X must find the relevant LocalID to send the messages to, but for DMU to hold, it must not uncover the actual intended destination. For the same reason, S must not make the link between ID D and LocalID S D . In other words, through an oblivious interaction with S, X must learn LocalID X D . We argue that to achieve secure computation of LocalID X D , a strong assumption need to be done: every node must possess a universal auxiliary information on the network. That is to say, a value that does not relate to a particular node, but on the contrary relates to all nodes. We actually show in appendix of this paper, that without such auxiliary information, an efficient and secure route initialization is impossible in our model 2 . In a nutshell, if we do not use universal auxiliary information, we show that, because X can not use any knowledge it has on D (else X would know the intended destination beforehand, which is absurd), X does not bring any input to the computation of LocalID X D except src X . This means that S must know the rest of the inputs necessary to compute it, i.e. S knows ID D and dst D . Therefore, S can compute LocalID S D by itself, and break DMU as explained above. The proposed solution is to give the power to S and X to compute together something they could not compute by themselves. We achieve this via a piece of information that each node keeps secret, different for each node and useless by itself, but when several pieces are combined, they produce a necessary input to all LocalID values. In practice, we instantiate these auxiliary information by shares of a secret key of a THE scheme.

Privacy analysis

Our protocol, as described in the previous section, is still vulnerable to many endto-end attacks and traffic analysis. To prevent them, we fix a constant message size 3 and we borrow techniques from MIX networks such as the introduction of random delays and message batching [START_REF] Diaz | Taxonomy of mixes and dummy traffic[END_REF]. These techniques unfortunately incur a loss of performances under the form of additional latency. We reject the insertion of dummy messages, for their prohibitive cost compared to the additional privacy they provide [START_REF] Oya | Do dummies pay off? limits of dummy traffic protection in anonymous communications[END_REF].

Preliminary properties Intuitively, our design ensures the following properties:

(1) By construction, routes are partially disjoint: for a given source-destination pair there may exist several routes, and for two different source-destination pairs, routes may overlap. Thus, in Fig. 4, Z can not know whether messages come from S 1 or S 2 , as the link identifier is the same for both routes. (2) If the Decisional DH assumption holds and secure cryptographic key derivation functions exist, link identifiers are secure: for a given pair of neighboring nodes (X, Y), link messages are unlinkable for AdvI and AdvII. That is to say, the pairs (L

X,Y , K

X,Y ) and (L

X,Y , K

X,Y ) stemming from two different DH handshakes are unlinkable.

2 There is a way to achieve route initialization by performing an exhaustive search in both S and X's DRTs, but this yields a quadratic complexity in the number of nodes. Proof sketches of these properties are available in appendix. We merely note here that property 3 seem to hold for the same reason that Elgamal is semantically secure. Indeed, LocalID X D can be seen as an Elgamal encryption of ID D under key dst D using randomness src X . However, the proof can not be the same, as in our case, the random coins src X are known to X.

Privacy properties Assuming the properties stated above hold, our protocol fulfills our privacy goals. We provide proof sketches in appendix.

-SMU holds against

• AdvI, because messages are exempt from any direct or indirect information on the source or its location in the network. • AdvI, if property 1 holds. Except in the special case of node X in Fig. 3.

• AdvII, if property 2 holds.

Shortcomings and future improvements

The above analysis is mainly intuitive. Formal proofs are desirable in order to confirm that the privacy goals are met. For this, the framework of Hevia and Micciancio [START_REF] Hevia | An indistinguishability-based characterization of anonymous channels[END_REF] provides a formal definition of source, destination and/or message unlinkability against adversary models that are very close to ours. Because we mainly focused on privacy, our solution is neither efficient nor optimized. In particular, it does not give any guarantee on the connectivity of the network, it does not manage route lifetimes, does not handle routing loops and does not limit the size of the routes. For a practical routing algorithm, mechanisms handling those points are necessary. The difficulty is to design such mechanisms while preserving privacy.

Our protocol is vulnerable to active attacks. To port security against active internal non-collusive adversaries, it has to be modified so that homomorphic evaluations performed by one party can be verified by another. For this, one may use homomorphic message authentication codes, which certify that some ciphertext stem from the correct homomorphic computation [START_REF] Catalano | Practical homomorphic macs for arithmetic circuits[END_REF].

Also, our protocol is vulnerable to a collusion of merely 2 nodes. For instance, if S and X collude in the route initialization protocol, they uncover the secret value dst D of D and S eventually break DMU. To resist against a collusion of t nodes, we can ask the relay nodes between S and X (assuming X is not neighbor to S) to participate in the threshold decryption protocol.

It would also be interesting to remove the strong assumption of universal auxiliary information. Indeed, although it is acceptable for particular contexts, assuming that each node owns a share of a common secret is unrealistic in general. As we have seen, in our solution, this hypothesis is necessary to obtain an efficient route initialization. A solution is to distribute the secret and secret shares generation, but in this case, the dynamic insertion of nodes is very complex. Other choices, models or assumptions might allow circumventing the impossibility result while enabling efficient route initialization. For instance, decorrelating the activities of sources and relays, so as to avoid issues raised in Sect. 4.1, would remove the need for interaction and universal auxiliary information.

At last future work should focus on testing the protocol against typical network attacks, and to assess the practical usability of our design measuring efficiency, available bandwidth and scalability through simulations.

Adaptation to a real-wold example: ad-hoc networks

We defined our protocol in a general, abstract network. As in our model, a simple physical medium is necessary, our protocol can work on top of any bare network graph. Indeed, no infrastructure nor any specific routers are required for our protocol to be deployed. Now, this section investigates how our protocol can be instantiated to a real world example. Because of the similarities with our model, we envision an adaptation to ad-hoc networks [START_REF] Chlamtac | Mobile ad hoc networking: imperatives and challenges[END_REF].

Indeed, these networks are infrastructure-less: there is no central node(s), and the routing is completely distributed. Ad-hoc routing protocols are either reactive or proactive. In the formers, routes are created only when necessary in an on-demand fashion while the others behave more as IP routing, where topology is flooded in the network. Although anonymous reactive routing designs are overwhelming, proactive ones are quite rare [START_REF] Liu | Performance evaluation of anonymous routing protocols in manets[END_REF]. The few we are aware of either make assumptions we reject such as the presence of nodes willing to disclose their identities, or provide only a weak form of privacy (but better efficiency). Our solution stands out by its proactive nature, by the strong privacy it provides, and by the use of homomorphic cryptography, which has never been used before in ad-hoc networks.

Ad-hoc networks allow a smooth integration of our protocol. Indeed, we can directly work above the MAC layer, assuming that nodes are able to function in promiscuous mode and to set their address to the broadcast address. Thus, nodes always use MAC broadcasting to communicate, and link identifiers to address specific neighbors, as described originally by Zhang et al. [START_REF] Zhang | Mask: anonymous on-demand routing in mobile ad hoc networks[END_REF]. Thanks to the broadcast nature of ad-hoc networks, privacy is even re-enforced. Indeed, when a node emits a message using link identifiers, AdvII can not even know which neighbor was addressed. This is not the case with wired networks, where links are point-to-point.

If we envision an adaptation to ad-hoc networks, the main shortcoming of our protocol is its inefficiency. The cost of cryptographic primitives is prohibitive for ad-hoc network nodes, which are typically small devices with limited battery power. At last, for an adaptation to mobile ad-hoc networks (MANETs), we have to take in account the nodes' mobility, which might cause route exhaustion and imprecise knowledge of the neighborhood. To deal with frequent topology changes, a trivial yet inefficient solution is to increase the frequency of route proposals. Another possibility is to rely on the fact that, as several routes are created from each source-destination pair, there will always be a valid route.

Conclusion

This preliminary work lays the foundations for strongly private network communications using homomorphic encryption. We presented a privacy preserving routing protocol suitable for distributed environments, exhibited its main features, and provided a partial proof of its privacy properties. As practical use-case, we showed that an adaptation to ad-hoc networks is at hand. Many points need to be addressed, and several others can be improved. In particular, future work will include advanced experimentations to attest the gain in privacy provided by our protocol and its efficiency. Even though we do not expect our protocol to perform as good as the state-of-the-art, we assume our users are willing to trade some efficiency against strong privacy (a feature often lacking in presently deployed solutions 5 ). If possible, privacy properties should be proved formally, but how to do so is still an open question. Even technologies already widely deployed, which benefit from years of experience, regularly suffer attacks. Of course, we do not intend to replace these solutions, but merely to complete them. We see our work as a proof of concept for new strongly private interactive communications, offering free communications in any circumstances.

A Correctness and performances of arithmetic operations

Our design makes extensive use of Elgamal, and most of the cryptographic operations are performed within the Elgamal group G. For instance, in order to take full advantage of the scheme's homomorphic properties, the local identifiers and the node identities need to belong to the same space as the ciphertexts. This is a non-standard use of Elgamal: usually, messages belong to Zq, and a message encoding function from Zq to G is applied to them. In our case, messages are directly taken in G. Furthermore, the arithmetic operations we use often modify both the Elgamal ciphertext and the underlying plaintext. The most representative example is the modular root computation during the route initialization, that takes place inside a ciphertext.

To check the correctness of our computations, and more specifically of the ScMult and ScExp functions and the modular root, we developed a simple PHP script 6 . By programming an encoding-free version of Elgamal, we successfully verified that the computation of the local identifiers the route proposal and initialization protocols yield the right output. The choice of the language was motivated by the facility and rapidity to develop with PHP. The code should not, in any case, be considered secure or be used for any other purpose than checking correctness of the arithmetic operations involved in the protocol.

Although a highly non-optimized coding, we report in Table 1 the timings for a toy instantiation of Elgamal with security parameter λ = 10, without taking in account any notion of communication delay. The threshold decryption phase is also not represented. Table 2 compares the running times of the C++ (with the GMP library) and the PHP modular exponentiation algorithm on the same test platform. The results show that we can hope augmenting performances by a factor of at least 50, 000 in future implementations.

Table 1. Running times of poof-of-concept PHP implementation for λ = 10.

KeyGen Enc

Dec Ctxt mult. ScMult ScExp ReRand Rt prop. Rt init. 47.46ms 0.14ms 0.24ms 0.13ms 0.07ms 0.13ms 0.20ms 1.32ms 1.25ms

B Proof of privacy properties

This appendix gives arguments towards proving that our protocol achieves the privacy goals stated in Sect. 4.2, by first showing that the seven properties from the same section hold. These "proofs" are merely written arguments, sometimes making reference to hard problems in cryptography, such as the discrete logarithm problem. Indeed, although there exists metrics or formal tools for anonymity in network communications, we reject their use here (mainly because our work is preliminary).

In [START_REF] Díaz | Towards measuring anonymity[END_REF], the authors measure anonymity by modeling the knowledge of the adversary with respect to some event (e.g. the sending of a message) as a probability distribution on the nodes' identities. This probability distribution is then compared to the uniform probability distribution by computing the difference of their Shanon entropy. As the authors themselves underline, the metric suffers from several shortcomings. First, it gives no indications so as to generating the adversary's knowledge, and it is straightforward in small examples, this task is uneasy in general. Secondly, the adversary's auxiliary information is not taken into account. For instance, the adversary may know that Alice and Bob participate in the network, and that they are likely to communicate. We add to these facts that setting the threshold of entropy difference above which the privacy is considered broken is unclear. Furthermore, whether the threshold should be chosen depending on the number of nodes, the density of the network, or the number of corrupted nodes is also an open question. At last, in our case, identities are not disclosed at all, so the probability distribution modeling the adversary's knowledge can not be based on them.

Another measure of privacy as been proposed by Hevia and Micciancio under the form of a cryptographic framework [START_REF] Hevia | An indistinguishability-based characterization of anonymous channels[END_REF]. They define privacy properties in a very formal way, and express security through cryptographic games and in terms of indistinguishability. Their model seems is close to ours, and their framework seems suited to our setting. However, the authors do not give any clue towards using it. And in the general case, it is unclear how to use their game-based security definition.

For all these reasons, we will settle for rather informal proofs, reasoning at a high level.

B.1 Preliminaries

When possible security properties are formalized via game-based security definitions. In those definitions, the adversary is denoted A. The oracle for a function or primitive f (x) is notedO f (•) . An adversary having access to the oracle for function f is denoted

A O f (•) .

B.2 Preliminary properties

This section considers the seven properties from Sect. 4.2 and discusses them one by one.

Property 1 By construction, routes are partially disjoint: for a given source-destination pair there may exist several routes, and for two different source-destination pairs, routes may overlap. Thus, in Fig. 4, Z can not know whether messages come from S1 or S2, as the link identifier is the same for both routes.

This property simply follows from observations on how routes are constructed. We refer to Fig. 4 in the following paragraph. Using the route proposal sub-protocol described in Sect. 3.2, the routes were constructed in the following order:

-First, D proposed itself to its neighbor. Z learned here the value LocalID Z D , and D and Z formed the link LZ,D.

-Then, Z proposed this newly learned route to its own neighbors. For each neighbor, a different link identifier was formed: LY,Z and LB,Z . -In a third phase, B and Y simultaneously proposed their newly learned route to D. The new links are then LX,Y and LA,B. -After two more steps, S1 and S2 were aware of D. Now, we can see that: (i) two sources may share a portion of route towards the same destination, and (ii) one source may have several routes towards the same destination.

For (i), there are two examples: S1 and S2 share the links LY,Z and LZ,D. In Fig. the links for the green route and the blue dashed one are noted differently, but all links drawn between Y and Z are designated by the same link identifier LY,Z (the same goes for links between Z and D). Therefore, whether a message was originally sent by S1 or S2, Z receives it from the same link identifier, and forwards it on the same link identifier. The second example is the portion of route between Z and D, shared between the dashed blue route coming from S1 and the dotted one coming from S2. But in this case, Z can make the difference between a message from S1, which arrives from LY,Z , and a message from S2, which arrives from LB,Z .

Concerning the second fact (ii), we have an example with S1. It has a route using X, and another using A. This means messages from the same communication between S1 and D may take each a different path, and a corrupted node on one route will only see a fraction of the communication.

Property 2 If the Decisional DH assumption holds and secure cryptographic key derivation functions exist, link identifiers are secure: for a given pair of neighboring nodes (X, Y), link messages are unlinkable for AdvI and AdvII. That is to say, the pairs (L

(1) X,Y , K (1)
X,Y ) and (L

(2) X,Y , K (2)
X,Y ) stemming from two different DH handshakes are unlinkable.

As the link identifier structure is borrowed from a construction by Zhang et al. [START_REF] Zhang | Mask: anonymous on-demand routing in mobile ad hoc networks[END_REF], we refer to their work. Note however that the authors, in order to achieve authentication during the neighbor discovery phase, make use of an external trusted third party and a bilinear map. As authentication is not a goal for us, we solely need regular Diffie-Hellman handshakes and cryptographic key derivation functions (KDF). Assuming the DH handshake led to the common value S, in our protocol, two neighboring nodes (X, Y) compute their i-th key and link identifier as LX,Y = KDF(S, salt, 2i) and KX,Y = KDF(S, salt, 2i + 1). Therefore, if the Decisional DH assumption holds and KDF exists, the generation of link identifiers is secure in our sense. Indeed, the secret S can only be known by X and Y, thus they are the only ones able to generate such links. If the KDF is collision resistant, a different handshake or a different index i lead to different links and keys. If the KDF is one-way (or pre-image resistant), it is impossible for a PPT adversary to find v given H(v), thus the secret S can not be found. Finally, if the KDF is pseudo-random, the link and key for index i and the ones for index i + 1 both look random (to a PPT adversary), and are thus unlinkable. In the same way, the links and keys for two different DH handshakes are computationally indistinguishable from random, and are thus unlinkable (even for the entities that performed the DH handshake).

Property 3

The local identifiers are secure: for all X and D, LocalID X D is known only to X; if the Computational DH assumption holds, given LocalID X D it is not possible to recover the inputs that formed it; and if the DDH assumption holds, for any X, D1, D2, LocalID X D 1 and LocalID X D 2 , X is unable to know which local identifier points to which destination.

Prior to formalizing the security definition of local identifiers, we abstract their structure. For this, we give an abstract definition of the computation of local identifiers in 3 steps, as in the route proposition. The first and last steps are made by the destination, while the second is made by the source (or relay) node. We denote by Gen : {0, 1} * → {0, 1} * the function taking in input the security parameter λ and generating the public parameters pp, including the sets X , Y and By Comp1 : X → Y we denote the ideal function computing the first step of the local identifiers computation on the destination side. We say a local identifier structure is secure if the following properties hold for all nodes X and D: -Secrecy: LocalID X D must be known by X only. -Collaborative oblivious computation: For all X and for all D = X, LocalID X D can not be computed by a network entity by itself, and must be the result of a protocol between several parties where each party keeps its inputs secret.

-Uniqueness: For all nodes W, X, Y, Z such that

¬(W = X = Y = Z), LocalID X W = LocalID Z Y with high probability. -Indistinguishability: Adversary A O Gen(•) ,O Comp(•,•,•) = (A1,

Game Exp ind

LocalID (A)

pp ← Gen(1 λ ); (x (1)
1 , y (1) ), (x

1 , y (2) ) ← U(X × Y) (x2, state) ← A1(pp, y (1) , y (2)

) b * ← U({0, 1}); LocalID * ← Comp(x (b * ) 1 , x2, y (b * ) ) b ← A2(state, LocalID * ) Return b = b *
-Computational One-Wayness: For an adversary A, the following probabilities are negligible in λ.

P r[pp ← Gen(1 λ ) :

A(1 λ , pp, x2, Comp(x1, x2, y)) = y] P r[pp ← Gen(1 λ ) : A(1 λ , pp, x2, y, Comp(x1, x2, y)) = x1]
We now show that our structure of local identifiers indeed fulfills these properties. Note that in our case, x1, x2 and y respectively correspond to dstD, srcX and IDD, and that we want to prevent a node X who knows the value LocalID X D from being able to link it to y = IDD or to recover the value x1 = dstD.

The Pairness, Secrecy and Collaborative computation properties relate to the dynamics of the network. We can only argument them. For the 3 other properties, proof sketches can be given. Pairness is trivially true: we use srcX which is generated and belongs to X, and IDD and dstD which are generated and belong to D. Secrecy is indeed verified because LocalID X D is never seen in clear by any other node than X: it is always encrypted, either by Elgamal either by link keys. Thus Secrecy relies the security of those encryptions. The only exception appears in the route proposition, where D sees the values r.g dst D .src X and r.LocalID X D . But D learns nothing from this value, because of the blinding factor r. Collaborative oblivious computation is also respected: local identifiers are indeed collaboratively computed in the route proposition and initialization. In the route proposition, srcX remains secret to X assuming the discrete logarithm is a hard problem, and dstD and g dst D remain secret to D assuming Elgamal is semantically secure. As for IDD, it remains secret if we manage to prove the Computational one-wayness property. In the route initialization, dstD stays secret to D by the security of the THE scheme with respect to S, and thanks to the blinding factor r with respect to X. srcX stays secret by the security of Elgamal, and again IDD is secret if Computational one-wayness holds.

Proof Sketch for Uniqueness. By reflexion on the birthday attack. It is know that, for a function f : {0, 1} L → {0, 1} l with L > l, and a collection of uniformly distributed elements x1, . . . , x k ∈ {0, 1} L , the probability that at least one of the pair (xi, xj) with i = j is a collision is roughly p = k 2 2 -l . In our case, l = |q| ≈ 2λ, L = 3l, and k is the number of distinct local identifiers in the network. As there are n nodes, and each node has n local identifiers, k = n 2 . For a constant maximum number of nodes equal to 10 6 , the probability that two local identifiers are the same is:

p = 10 12 2 2 |q|
This value is indeed negligible in the security parameters λ. For example, when λ = 80, p ≈ 2 -80 and for λ = 128, p ≈ 2 -180

Proof Sketch for Indistinguishability. As LocalID X D = IDD.g src X .dst D can be seen as an Elgamal encryption of IDD under key dstD and randomness scrX , it would be convenient to borrow the semantic security proof of the scheme. However, it is not possible, because in our case the adversary has access to additional knowledge. Indeed, if the adversary is the node X, she knows srcX , which corresponds to the randomness used for encryption if we consider LocalID X D as an Elgamal encryption. Hence, we need a different proof.

The idea is to show that, for a node X, given srcX of its choice, the identity of two nodes IDD 1 and IDD 2 , and the value LocalID X D * (its local identifier for one of D1 or D2), X can not know if LocalID X D * is equal to LocalID X D 1 or LocalID X D 2 . Let's review the possibilities of X. She can proceed as follows: it begins by assuming the local identifier is towards D1 and computes (assuming srcX and p -1 are co-prime):

src X LocalID X D * IDD 1 = g dst D * IDD * IDD 1 1/src X = g dst D * .g (logID D * -logID D 1 )/src X
In both cases, what X obtains is computationally indistinguishable from a uniformly sampled element of G. Indeed, if D * = D1, X obtains g dst D 1 which is uniformly distributed, because dstD 1 is itself uniformly distributed (and unknown to X). And if D * = D2, even though X can compute g (logID D * -logID D 1 )/src X and obtain g dst D 2 the result is again uniformly distributed for the same reason. If X had assumed that D * was D2, the same argument applies. The other possibility for X is to first divide by IDD 1 and compute the root afterwards. But the result is the same, and even X may find g dst D * in several ways, it can never confirm or refute its hypothesis and distinguish the two cases. So A can not win the game with non-negligible probability.

Proof Sketch for Computation one-wayness. This property follows from the Indistinguishability property and from the hardness assumption of the discrete logarithm problem. Indeed, if we consider the first probability. If the adversary was able to recover y with with non-negligible probability, she would win the game Exp ind LocalID with nonnegligible probability (assuming P r[y (1) = y (2) ] is negligible, which is the case). Regarding the second probability, the adversary's success is bounded by its ability to compute a discrete logarithm.

Property 4 Route propositions are indistinguishable for AdvI. Because, locally, the messages exchanged are the same in both cases, whether a route proposition emanated from the destination itself or a proxy is indistinguishable for AdvI.

This property can also be modeled by a cryptographic game. We consider a setup where either the node X is a direct neighbor to D, either there are one or several nodes between X and D. We give the adversary the right to provoke at will as many propositions as it wants, but not to change the network setting after the beginning of the game. The goal of the adversary, of type AdvI and in the situation of X, is to distinguish the two cases (finding out if the destination D of the proposition is a direct neighbor or not). We assume that the adversary can not perform timing analysis. We discuss this assumption in the paragraph concerning property 5.

Proof sketch. Informally, it is easy to show that from the point of view of X, and without taking in account message transmission delays, the two cases are exactly the same. Indeed, the number of messages received and emitted by X is respectively two and one in both cases. Also, the respective size of the first, second and third messages are the same in both cases. The first message contains the destination's public key, a half of DH handshake freshly (uniformly) generated, and a re-randomized ciphertext always encrypting the same value. Assuming the re-randomization indeed outputs ciphertexts uniformly distributed in the range of the encryption primitive, the distributions of the first message in each case are computationally indistinguishable. The second message is produced by X, and thus is not of interest here. Then, the third message contains a link identifier and a symmetric encryption of r.LocalID X D using the link key. The distributions of the third message are thus also computationally indistinguishable, assuming link identifiers are secure, and that the correct value r.LocalID X D is always returned. For a formal proof, it would be necessary to simulate and compare X's views in the two cases.

Property 5 If route propositions are indistinguishable for AdvI, if the encryption schemes used are semantically secure, if the link identifiers are secure, and if we use MIXing techniques in the route proposal, then up to a certain point, AdvII can not distinguish whether a proposition emanated from the destination or a proxy.

Firstly, if AdvII does not perform traffic analysis but merely records the message and only has a local view, she is not able to distinguish whether a route proposition emanated from the destination itself or a proxy. By property 4, the respective distributions of the first and third message are the same whether X is a direct neighbor to D or not. And by the semantic security of the PKE scheme used, the re-randomization property, the uniform sampling of b (and thus g b ), the distributions of second message are also computationally indistinguishable. Now, if AdvII is able to perform traffic analysis and has a global view, she can trace sequences of route proposals moving away from the destination D. Thus, AdvII can distinguish when the route is proposed by the destination itself or not. To thwart this, we can use message batching and reordering. As a result, AdvII is no longer able to follow sequences of route proposals. However, what we can not prevent are timing analysis. For a proxy at, say, 1 or 2 hops from D, thanks to random delays, AdvII will have difficulties distinguishing the two cases using differences in timings, as they will be small. However, the time required to go from X to D and come back is much more important in the case X is at 4 or more hops from D than in the case X is a direct neighbor. Thus, AdvII can not know if a proposition emanates from a destination or a proxy, up to a certain number of hops.

Property 6 If local identifiers are secure, route initialization is oblivious for AdvI. Indeed, S never makes the link between D and its value LocalID S D , and V never learns that the destination is D. In addition, the blinding factor r hides dstD and if the discrete logarithm problem is hard, srcX is concealed.

In the same way as for the local identifiers, we formalize the security requirements for route initialization. We say route initialization is secure if the following properties hold:

-Obliviousness for S : S must not be able to link IDD with LocalID S D . -Obliviousness for X : X must not learn the destination that S considers.

-Secrecy: each party N should keep its values srcN , dstN , IDN and all the local identifiers in its DRT secret to himself. D should keep its value dstD secret.

The two first properties are necessary for DMU to hold, while the third one ensures the assumptions on the secret values src, dst and ID holds, and that the Secrecy of local identifiers is conserved. We now prove that our route initialization fulfills these properties.

Proof sketch for Obliviousness for S. We assume that the local identifiers are secure, in the sense of property 3. Thus S can not a priori link IDD (or simply D) with LocalID S D because of the Indistinguishability property of local identifiers. Then, the route initialization procedure do not give S any new element towards linking IDD. Indeed, if the THE scheme is semantically secure, S does not learn anything from the values C = THEnc(pk * , dstD) and THDec(shS, C). And if Elgamal is semantically secure, S does not learn anything from HEnc(pkX , g r.dst D .src X ). At last, because we assumed that every node has a route towards every other node in the network, the fact that X knows a route towards D does not leak information.

For a formal proof, it would be necessary to simulate S's view during the route initialization.

Proof sketch for Obliviousness for X. We assume that the local identifiers are secure, in the sense of property 3. Thus X can not a priori know that its value LocalID X D links to D. Then, thanks to the blinding factor r that acts as a one-time pad, X does not learn anything from the decryption of C = THEnc(pk * , r.dstD). Then, if the re-randomization yields random-looking ciphertexts, X can not extract information (in particular on r) from ReRand(pkX, ScMult(IDD, ScExp(C , r -1 mod (p -1)))). X eventually learns LocalID X D , but nothing else, and compared to the a priori case, X has no more information on link between IDD and LocalID X D . Finally, although it is not relevant in this proof, it is worth noting that if the secret share shS is not publicly linked to S, even if the value THDec(shS, C) leaks information on shS, X can not infer that the source is S.

For a formal proof, it would be necessary to simulate X's view during the route initialization.

Proof sketch for Secrecy. During the protocol, S keeps its values srcS, dstS and IDS, and its local identifiers secret simply because it does not use them. The same goes for X's values dstX and IDX , and all local identifiers of X (except LocalID X D ). Then, the values srcX , g src X and LocalID X D are not disclosed assuming Elgamal is semantically secure. Finally, as we consider honest-but-curious adversaries, S and X do not collude and S indeed applies a scalar multiplication by a blinding factor r on THEnc(pk * , dstD) (and a re-randomization). Therefore, dstD is ensured to stay secret to D.

For a formal proof, it would be necessary to simulate the view of S and X during the route initialization. This property is quite trivial. Messages exchanged between S and X in the route initialization are encrypted with link keys and addressed via link identifiers, just as in a regular communication. Therefore, if the link identifiers are secure in the sense of property 2, an external observer is unable to see the difference between route initialization and regular communication. The only possibility for the observer is to fingerprint the route initialization protocol by simulating runs of this protocol and measuring average timings between messages or other metrics. Then, the observer could possibly identify routes initialization in the network, because the sequence of messages exchanged is different from standard communication in general. We introduce MIXing techniques in the route initialization, so that obtaining a precise fingerprint is difficult for the adversary.

B.3 Privacy goals

This section shows that our protocol achieves our actual privacy goals. From now on, we assume that the seven properties from the previous section are ensured. Also, as a general remark, note that AdvII has very little power thanks to the link identifier structure (assuming they are secure). Indeed, all messages are encrypted and locally addressed with link identifiers in an anonymous way. Furthermore, for a given message, its appearance changes at each hop, and for a given link, the symmetric encryption key changes at each message. And also, because we assume messages are of fixed size, AdvII can not learn anything on the contents of messages and can not trace them.

SMU against AdvI

This property is quite simply verified. Locally, when a node receives a message on some link, it can not know if the node at the other end of the link acts as source or relay (notably because all nodes may be source or relay). Furthermore, the contents of the messages do not give any information on the source, either directly (e.g. its identity) or indirectly (e.g. the number of hops from the source).

SMU against AdvII If property 7 holds, AdvII can not detect a route initialization, and she can not know which nodes initiate communications by this mean. However, it is not sufficient. Indeed, using the simple heuristic that a node emitting a message without prior solicitation is a AdvII can locate sources (but not learn their identities). Even though the chances of locating sources are reduced when traffic is dense and when MIXing techniques are employed, if AdvII notices that a node receives k messages in some time frame and emits k + 1 messages afterwards, she will infer that the node is a source. The feasibility of this attack is however uncertain. Especially in broadcast networks such as ad-hoc networks (or more generally, wireless networks): if each node locally broadcasts its messages (either as a source or as a relay) and if we make use of secure link identifiers to address neighbors, AdvII can not count the number of messages received by a given node. Therefore, she can not compare the number of incoming and outgoing messages from a node nor locate sources.

DMU against AdvI First, if local identifiers are secure (property 3), they do not reveal the destination they are pointing to. Secondly, if property 4 holds, route propositions do not let the receiver of the proposition know who the actual destination of the proposition is. Then, if property 6 holds, route initialization does not leak information to X about the destination intended by S, and S does not learn that LocalID S D relates to D. At last, it is necessary to assume that the PKE scheme used to encrypt payload messages is receiver-anonymous [START_REF] Kohlweiss | Anonymitypreserving public-key encryption: A constructive approach[END_REF]. Indeed, the permanent public keys are publicly linked to their owners, and in general, ciphertexts of PKE schemes leak information on the encryption key. Thus, forwarding nodes may learn the identity of the destination. In receiver-anonymous PKE schemes, it is ensured that no information is leaked by ciphertexts on the encryption key.

DMU against AdvII Firstly, if property 5 holds, AdvII can not learn the destination of a route proposition by observing the route proposition protocol. Then, if link identifiers are secure, AdvII can not trace messages to their destination. However, in the same way that she locates sources, AdvII can locate destination. To thwart destination localization, destination nodes can simulate a relay upon receiving a message. A possible way to do so, is for a destination to create a fake message containing solely a TTL-like number and padding. The TTL may take a value between 0 and 2 for instance, randomly chosen. The destination sends this value on a random route chosen in its DRT. The addressed neighbor, upon receiving the fake message, if the TTL value is greater than 0, decreases it by 1 and forwards it on a random route as well. When the TTL reaches 0, the message is discarded. As a result, to the knowledge of AdvII, the possible receivers of a given message are the node that received k messages in some time frame but emitted k -1 messages afterwards, along with its 3 hop neighborhood.

SDU against AdvI and AdvII

This property is quite straightforward: if SMU holds against some adversary, then the source of a communication is unknown and SDU holds. The same goes for DMU. Therefore, if either SMU or DMU hold, SDU holds.

MMU against AdvI

This follows from property 1 stating that routes are disjoint. Indeed, in Fig. 4, a locally corrupted Z is actually completely unable to distinguish a message from S1 and a message from S2. Because it only has a local view of the network, given an incoming link identifier, Z does not know if this link is used by one upstream source only or by several ones. Therefore, even though Z may that two messages are meant for the same destination, it does not know if it comes from the same source, and can not infer that those messages belong to the same communication.

However, in the route initialization example from Fig. 3, an adversary of type I who corrupted X is able to break MMU. Indeed, it knows that all messages come from the same source and are for the same destination. This vulnerability is acceptable because X does not know the identity of S and D.

MMU against AdvII For this property to hold, link identifiers must be secure (property 2). A noted above, AdvII is unable to learn any information on the contents of messages, can not trace them, and thus can not relate two messages. The only information AdvII can infer is that two messages going though the same link may belong to the same communication. But she can not be sure of it, thanks to property 1.

B.4 Remark

Our argumentations does not consider the auxiliary information that the adversary may have. For instance, the adversary might know that some node is a privileged destination, maybe because it is the only one routing messages to Internet. As AdvII can detect traffic patterns, she will easily locate this node: it will be the target of a considerable amount of traffic. There are many other examples of the same sort. Taking into account the adversary's auxiliary information is part of future work.

C (Imp)possibilities for route initialization

In Sect. 4.1, we discussed the necessity of universal auxiliary information to enable secure and efficient route initialization. This appendix explicits what we mean by "secure and efficient", and why, in our model, our claim is true. As starting point, we assume the topology is disseminated and consider the local identifiers in their abstract description from property 3 in Appendix B, assuming they are secure. In other words, this section does not consider any particular instantiation for the local identifier structure.

We already addressed the notion of security for route initialization in property 6 from Appendix B. We measure efficiency according to the number of nodes in the network. As we will see in this appendix, there is a (relatively) trivial way for S and X (in our example in Fig. 3) to find the value LocalID X D in X's DRT. The idea is to make a sort of exhaustive search in both S and X's DRTs. The cost of this solution in term of computation and communication is quadratic in the number of nodes n in the network: its complexity is O(n 2 ). We consider reducing this complexity: we are interested in solutions which cost is linear in n or even constant, i.e. in O(n) or O(1) with respect to the number of nodes.

According to our results, there exists solutions with such complexities, under particular assumptions. The below claims and their proof sketches capture our results. Claim 1. A secure solution for route initialization in O(n 2 ) is possible (against a PPT honest but curious adversary).

Proof Sketch. The proof consists in exhibiting a route initialization protocol with cost O(n 2 ), and to show it is secure (according to our definition). A possible, highly inefficient solution is depicted in sub-protocol 2, where "∀ N ∈ DRTX" denotes all the entries of X's DRT for all destinations N. Clearly, cost of this solution is linear in the number of different local identifiers in the DRT of S, and linear in the number those in the DRT of X. That is to say, it is quadratic in n.

The correctness of the protocol is easily checked: the value testN,M is indeed equal to 1 if N = M = D. In every other case, the probability that the plaintext in equation ( 2) is equal to 1 is roughly 1/|G|. Now, we argue that the security properties of route initialization hold for this sub-protocol.

Globally, the obliviousness for S , the obliviousness for X and the secrecy properties rely on the semantic security of the HE scheme used. Indeed, both S and X mainly manipulate ciphertexts. There are however exceptions that might compromise security:

-X sees in the clear the values (LocalID X M ) src S for all M. But it learns nothing new from them if the discrete logarithm is a hard problem.

-S sees in the clear the values textN,M for all N and M. However, because the identities and the src and dst values are randomly distributed, and because X processes the aux2(S, M ) and aux2(X, N ) in random order, the values testN,M are indistinguishable from random for S.

This concludes the argument. Proofs by simulation using standard hybrid arguments (one for S, one for X) are necessary to formally prove our claim. Claim 2. A secure solution for route initialization in O(1), without universal auxiliary information, is impossible (against a PPT honest but curious adversary).

Proof Sketch. By contradiction. Imagine that a secure and correct protocol P exists for a route initialization in O(1), without using universal auxiliary information.

In a solution with complexity O(1) (w.r.t. n), we forbid the scanning of both S and X's DRTs. Therefore, the respective inputs of the protocol can be described as:

-S's input contains x1,S, x2,S, yS. It can contain: dynamically generated values such as cryptographic keys, and auxiliary values related to D (because we assume D communicated information to S prior to network setup). It can not contain: universal auxiliary information on the network. -X's input contains: x1,X , x2,X , yX . It can contain: dynamically generated values such as cryptographic keys. It can not contain: universal auxiliary information on the network, nor any auxiliary information on D (indeed, X does not know a priori which node is S's intended destination).

We denote the union of S and X's inputs by InS ∪ InX . Now, there are two possibilities: either InS ∪ InX contains the necessary material to compute LocalID X D using protocol P, either it does not. In the latter case, we reach a contradiction because we supposed that P was correct. And if InS ∪ InX allows computation of LocalID X D , then we also reach a contradiction: S can compute by itself LocalID S D , thus making the link between D and LocalID S D and breaking the Obliviousness for S property of route initialization (and, ultimately, S breaks DMU as explained in Sect. 4.1). Indeed, if InS ∪ InX can lead to LocalID X D , this means that x1,D, x2,X , yD ∈ InS ∪ InX , because LocalID X D = Comp3(yD, Comp2(x2,X , Comp1(x1,D))). However, X's inputs can not contain information on D. This implies that x1,D and yD come from S's inputs. Therefore, in S's inputs, there is the necessary material to compute LocalID S D = Comp3(yD, Comp2(x2,S, Comp1(x1,D))). Said otherwise, S can run the protocol P playing both roles in order to obtain LocalID S D . This is because X's input, with respect to LocalID X D , does not contain anything more than S's input with respect to LocalID S D .

Claim 3. There exists a secure solution for route initialization in O(1), assuming the existence of universal auxiliary information (against a PPT honest but curious adversary).

Proof To prove this claim, it is sufficient to exhibit a particular solution for route initialization in O( 1) that uses universal auxiliary information and is secure.

We already provided such a solution in the description of our protocol: the route initialization described in Sect 3.3 indeed uses universal auxiliary information (under the form of secret shares of sk * ) and runs in constant time with respect to the number of nodes in the network (indeed, no DRT or any table is used). Therefore, this claim follows directly from the proof sketch of property 6 in Appendix B.

In the above claims, we did not address the case of solutions in O(n), linear in the number of nodes. Actually, it seems that the same claims as for the constant case hold: a solution in O(n) is possible only using universal auxiliary information. Indeed, we reach the same case, where S is able to run the protocol playing both roles in order to obtain LocalID S D . We did not further study solutions in complexity O(n) because their interest is limited. Indeed, they seem to yield less efficient solutions for the same strong assumption as the solutions in complexity O(1).

M

.g src X .dst M .src S ) 3: S → X : ∀M, HEnc(pkX , ID src S M .g src X .dst M .src S ) (in the same order as received) For all M, X decrypts the value received and re-encrypts it under pkS (This step is necessary to perform the following homomorphic operations on ciphertexts).

X computes aux1(X) = ScExp(HEnc(pkS, IDD), srcX ) = HEnc(pkS, ID src X D ) Denote by aux1(S) the value HEnc(pkS, ID src S D ) from message 1 For all N, X computes aux2(X, N ) = ScExp(HEnc(pkS, LocalID S N ), srcX ) = HEnc(pkS, ID src X N .g src S .dst N .src X ) Denote by aux2(S, M ) the values from message 3 4: While X did not receive STOP from S, for all M, in random order, X computes and sends, for all N:

testN,M = aux1(S).aux2(X, N ) aux1(X).aux2(S, M )

Fig. 1 .

 1 Fig. 1. Topology dissemination in a toy network.

Fig. 3 .

 3 Fig. 3. S sends a message to D.

  Comp2 : X × Y → Y is the ideal function computing the second step, on the source side. And Comp3 : Y × Y → Z is the ideal function computing the third step, on the destination side. We write LocalID X D = Comp3(yD, Comp2(xX , Comp1(xD))), where xD ∈ X is the input of X, and xD ∈ X and yD ∈ Y are the inputs of D. For simplicity, we define Comp : X × X × Y → Z as Comp(x1, x2, y) := Comp3(y, Comp2(x2, Comp1(x1)).

-

  Pairness: LocalID X D depends on values generated by X and D only. If LocalIDX D = Comp(x,, x2, y), then x1, x2 and y belong to one of X and D, and are secret to this node.

  A2) has negligible advantage in winning the game Exp ind LocalID described below, that is to say the value |P r[Exp ind LocalID (A O Gen(•) ,O Comb(•,•,•) ) = 1] -1/2| is negligible in the security parameter λ:

Property 7

 7 If we use MIXing techniques, and if link identifiers are secure, route initialization is indistinguishable from standard communication for AdvII.

Protocol 2 S

 2 initiates a connection towards D with help of X in O(n 2 ) 1: S → X : HEnc(pkS, IDD), HEnc(pkS, ID src S D ), ∀N ∈ DRTS, HEnc(pkS, LocalID S N ) 2: X → S : ∀M ∈ DRTX , HEnc(pkX , LocalID X M ) For all M, S computes ScExp(HEnc(pkX , LocalID X M ), srcS) = HEnc(pkX , ID src S

=

  HEnc pkS, ID src X N ID src S M . ID src S D ID src X D .g (dst N -dst M ).src X .src S(2)= 1 if N = M = D, and a random value otherwise(3)X → S : HEnc(pkS, testN,M ) 5: S → X : STOP if testN,M = 1 X infers that LocalID X M is the local identifier sought for.

3

  Large messages are split into several ones, and padding is used if necessary. The local identifiers are secure: for all X and D, LocalID X D is known only to X; if the Computational DH assumption holds, given LocalID X D it is not possible to recover the inputs that formed it; and if the DDH assumption holds, for any X, D 1 , D 2 , LocalID X D1 and LocalID X D2 , X is unable to know which local identifier points to which destination. (4) Route propositions are indistinguishable for AdvI. Because, locally, the messages exchanged are the same in both cases, whether a route proposition emanated from the destination itself or a proxy is indistinguishable for AdvI. (5) If route propositions are indistinguishable for AdvI, if the encryption schemes used are semantically secure, if the link identifiers are secure, and if we use MIXing techniques in the route proposal, then up to a certain point, AdvII can not distinguish whether a proposition emanated from the destination or a proxy 4 . (6) If local identifiers are secure, route initialization is oblivious for AdvI. Indeed, S never makes the link between D and its value LocalID S D , and V never learns that the destination is D. In addition, the blinding factor r hides dst D and if the discrete logarithm problem is hard, src X is concealed. (7) If we use MIXing techniques, and if link identifiers are secure, route initialization is indistinguishable from standard communication for AdvII.

	S1	W
		Y	Z	D
	S2	X
		A	B
		Fig. 4. An example of partially disjoint routes
	(3)

  • AdvII, if we introduce MIXing techniques in the forwarding process and properties 2 and 7 hold. -DMU holds against • AdvI, if properties 3, 4 and 6 hold, and if the encryption schemes are receiver-anonymous [15]. • AdvII, if properties 2 and 5 hold, and if the destination, upon receiving a message, simulates a relay. -SDU holds against AdvI and AdvII if SMU or DMU hold. -MMU holds against

Table 2 .

 2 Comparison of PHP and C++ modular exp. running times for λ = 20.

	C++ (GMP lib) PHP
	0.0008ms	54ms

Up to a certain point, because when the proxy is far from the destination, a basic timing analysis is sufficient to distinguish the two cases.

A list of works is available at http://www.cs.kau.se/philwint/censorbib/ (thanks to Philipp Winter).

Available at https://github.com/aguellier/elgamal-for-private-comm

Acknowledgment

This work is partially funded by the Collège International Doctoral de l'Université Européenne de Bretagne (International Doctoral College of the European University of Brittany, France) and the Regional Council of Brittany, France. The authors would like to thank Simon Boche and Cristina Onete for their insightful suggestions and discussions on various components of the protocol and cryptographic-related topics, as well as for the precious advices brought during the writing of this paper.