SYSTEMS AND METHODS FOR ANONYMOUS, LOW-LATENCY, TRACKING- RESISTANT COMMUNICATIONS IN A NETWORKED ENVIRONMENT

CROSS REFERENCE TO RELATED APPLICATIONS

[0001] This application claims the benefit of priority to U.S. Provisional Application No. 62/411,334, filed on October 21, 2017, the entirety of which is incorporated by reference herein.

GOVERNMENT RIGHTS

[0002] This invention was made with government support under FA8750- 16-2-0034 awarded by Department of Homeland Security (DHS). The government has certain rights in the invention.

BACKGROUND

[0003] Anonymous communication networks attempt to allow people to share information while being indistinguishable from their peers, and hence untraceable by an eavesdropping entity. While certain forms of encryption may reduce an eavesdroppers ability to ascertain the content of the communications, contextual information (e.g., metadata) associated with the communications may still allow eavesdroppers to efficiently spy and track people on a large scale.

[0004] In conventional anonymous networks there has been tension between providing low- latency communication, bandwidth usage, and traffic- analysis resistance. As one example, some anonymous networks, such as Tor, focus on the first two, leaving the door open for a global eavesdropper to track people via traffic-analysis resistance, while other conventional anonymous networks may utilize traffic-analysis resistant techniques that sacrifice network latency. Thus, conventional anonymous networks typical do not provide a suitable environment for anonymity of users.

[0005] In traffic analysis attacks, eavesdroppers can de-anonymize users through traffic- analysis attacks (e.g., global surveillance). Local-Area Networks (LANs) may be more susceptible to such attacks due to their size and geographic areas. Because LANs are usually relatively small and geographically- local, an eavesdropper can monitor the entire or a large portion of a LAN with a small resource cost. For example, in the well-known parking lot attack, an adversary can install low-cost equipment, such as rogue access points, near a company's building to eavesdrop on (encrypted) wired or wireless LAN communications and to infer information about specific devices. Such attacks are concrete threats to sensitive workplaces, such as banks and defense organizations. As a result at least some sensitive workplaces choose to have a "no-wireless" policy prohibiting wireless deployments of any kind inside their buildings.

SUMMARY

[0006] Exemplary embodiments of the present disclosure advantageously address problems associated with trade-offs between anonymity and latency in anonymous networks, which arises from a tension between communication latency, bandwidth usage, and traffic-analysis resistance in such anonymous networks. In addressing the problems associated with anonymity and latency in anonymous networks, exemplary embodiments can provide cryptographically- strong tracking protection with unnoticeable "single-hop" network latencies by leveraging a client-relay- server architecture, in which the clients, relays (trusted or untrusted), and trustee devices are configured to implement an anonymity protocol where the trustee devices add little to no latency to the network.

[0007] In exemplary embodiments, even if the trustee devices are geographically dispersed around the world, the end-to-end latency of connections between clients and local or remote sites is dominated purely by "single-hop" communication via the relay. Thus, the trustee devices add security to the anonymity of clients, but not to the latency of the network, because the trustee devices are not on the latency-critical path.

[0008] In exemplary embodiments, a group of clients connect to a relay (e.g., a router), and synchronously transmit to the relay, ciphertexts (or cipher streams), where one of the ciphertexts from one of the clients contains a data message to be sent to an external network, such as the Internet, and the remaining ciphertexts include random data. Subsequently, the relay participates with a group of trustee devices in a distributed protocol to facilitate decryption of the data message without understanding which of the clients sent the data message (sender anonymity).

[0009] The trustee devices can precompute ciphertexts that may otherwise cause a major latency bottleneck in the anonymization process when computed on the fly. These ciphertexts do not depend on the actual communicated content from the clients to the relay. Therefore, the trustee devices can compute the ciphertexts before the ciphertexts are needed by the relay to decrypt the ciphertexts received from the clients to extract the data message from one of the clients. Upon receiving a response/message from the external network, the relay can broadcast the response/message to clients in the group providing receiver anonymity. [0010] Exemplary embodiments of the present disclosure can prevent equivocation attacks by an untrusted relay without adding extra latency. For example, an untrusted relay can equivocate by sending different (inconsistent) downstream messages to the clients to attempt de-anonymize the clients. In an example equivocation attack, in a non-SSL-encrypted communication, the untrusted relay can slightly modify the downstream message for each client to send each client a unique message. Then, in the next round, the untrusted relay checks to see what is being requested by one of the clients, and depending on the content requested, the untrusted relay can identify the client requesting the content. Exemplary embodiments of the present disclosure can prevent equivocation attacks without adding extra latency by encrypting clients' upstream messages in such a way that the ciphertext depends on previous downstream message(s). Therefore, the untrusted relay can only decrypt each upstream message if all clients agree on what they received in the past downstream message(s). This advantageously allows the clients to ensure they are each receiving the same message from the untrusted relay without imposing expensive overhead (e.g., in the form of a consensus protocol).

[0011] Exemplary embodiments of the present disclosure advantageously provide for quantifiable and formally provable anonymous communication system; security against traffic-analysis attacks; security against malicious attacks; small latency overhead suitable for everyday commercial and personal use; and direct deployability as extensions to open mobile platforms (e.g., Android) and WiFi infrastructures.

[0012] Any combination and/or permutation of embodiments is envisioned. Other objects and features will become apparent from the following detailed description considered in conjunction with the accompanying drawings. It is to be understood, however, that the drawings are designed as an illustration only and not as a definition of the limits of the present disclosure.

BRIEF DESCRIPTION OF THE DRAWINGS

[0013] In the drawings, like reference numerals refer to like parts throughout the various views of the non-limiting and non-exhaustive embodiments.

[0014] FIG. 1 is an exemplary networked environment in accordance with embodiments of the present disclosure.

[0015] FIG. 2 illustrates a relationship between shared secrets, pads, and ciphertexts.

[0016] FIG. 3 is an exemplary networked environment including multiple relays in accordance with embodiments of the present disclosure.

[0017] FIG. 4 is a block diagram of an exemplary client in accordance with embodiments of the present disclosure.

[0018] FIG. 5 is a block diagram of an exemplary relay in accordance with embodiments of the present disclosure.

[0019] FIG. 6 is a block diagram of an exemplary trustee device in accordance with embodiments of the present disclosure.

[0020] FIG. 7 is a graph showing anonymization of traffic and an associated latency in accordance with embodiments of the present disclosure. [0021] FIGS. 8A-B show graphs corresponding to a time-to-resynchronization a naive embodiment of the anonymity protocol and an optimized embodiment of the anonymity protocol, respectively, in accordance with embodiments of the present disclosure.

[0022] FIG. 9 shows a graph illustrating effects of cell size on upstream bandwidth and system latency in accordance with embodiments of the present disclosure.

[0023] FIGS. 10A and 10B show graphs illustrating effects of windowing on downstream communication speeds and system latency, respectively, in accordance with embodiments of the present disclosure.

[0024] FIG. 11 is a graph that illustrates network downtime as a result of an abrupt disconnection.

[0025] FIG. 12 is a graph that illustrates a size of the anonymity set versus time, when using embodiments of the present disclosure in an experimental environment.

[0026] FIGS. 13A-B are graphs that illustrate an end-to-end latency of experienced by one client and added latency when replaying a dataset with Skype packets, respectively.

[0027] FIGS. 14A-B are graphs that illustrate round duration.

[0028] FIG. 15 is a graph that illustrates an effect of pipelining on latency.

DETAILED DESCRIPTION

[0029] Exemplary embodiments of the present disclosure are related to systems, methods, and non-transitory computer-readable media for anonymous, low-latency, tracking-resistant communications in a networked environment. [0030] In exemplary embodiments, a group of clients connect to a relay (e.g., a router), and synchronously transmit to the relay, ciphertexts (or cipher streams), where one of the ciphertexts from one of the clients contains a data message to be sent to an external network, such as the Internet, and the remaining ciphertexts include random data. Subsequently, the relay participates with a group of trustee devices in a distributed protocol to facilitate decryption of the data message without understanding which of the clients sent the data message (sender anonymity).

[0031] The trustee devices can precompute ciphertexts that may otherwise cause a major latency bottleneck in the anonymization process when computed on the fly. These ciphertexts do not depend on the actual communicated content from the clients to the relay. Therefore, the trustee devices can compute the ciphertexts before the ciphertexts are needed by the relay to decrypt the ciphertexts received from the clients to extract the data message from one of the clients. Upon receiving a response/message from the external network, the relay can broadcast the response/message to clients in the group providing receiver anonymity.

[0032] Exemplary embodiments of the present disclosure can prevent equivocation attacks by an untrusted relay without adding extra latency. For example, an untrusted relay can equivocate by sending different (inconsistent) downstream messages to the clients to attempt de-anonymize the clients. In an example equivocation attack, in a non-SSL-encrypted communication, the untrusted relay can slightly modify the downstream message for each client to send each client a unique message. Then, in the next round, the untrusted relay checks to see what is being requested by one of the clients, and depending on the content requested, the untrusted relay can identify the client requesting the content. Exemplary embodiments of the present disclosure can prevent equivocation attacks without adding extra latency by encrypting clients' upstream messages in such a way that the ciphertext depends on previous downstream message(s). Therefore, the untrusted relay can only decrypt each upstream message if all clients agree on what they received in the past downstream message(s). This advantageously allows the clients to ensure they are each receiving the same message from the untrusted relay without imposing expensive overhead (e.g., in the form of a consensus protocol).

[0033] Exemplary embodiments of the present disclosure advantageously provide for quantifiable and formally provable anonymous communication system; security against traffic-analysis attacks; security against malicious attacks; small latency overhead suitable for everyday commercial and personal use; and direct deployability as extensions to open mobile platforms (e.g., Android) and WiFi infrastructures.

[0034] As used herein, "downstream communication" refers to data transmitted from local devices or remote devices (e.g., from the Internet) to a client via a relay device.

[0035] As used herein, "upstream communication" refers to data transmitted from one of the clients to other local devices or remote devices (e.g., to the Internet) via a relay device.

[0036] FIG. 1 is an exemplary networked environment 100 in accordance with embodiments of the present disclosure. The network environment 100 can include a set of clients 110, a relay 120, and trustee devices 130 (e.g., servers). Each of the clients 110, relay 120, and trustee devices 130 can be configured with an anonymity protocol, or portions thereof, that can be implemented to facilitate anonymous, low-latency, tracking-resistant communications in the networked environment 100, which forms an anonymous network. For example, the clients 110 can be programmed to implement a client component of the anonymity protocol, the relay can be programmed to implement a relay component of the anonymity component, and the trustee devices 130 can be programmed to implement a trustee component of the anonymity protocol. In exemplary embodiments, the clients 110, relay 120, and trustee devices 130 can communicate using non-private but authenticated channels, which may be observable by an adversary such that an adversary can observe messages when they are sent by the clients 110, relays 120, and/or servers 130.

[0037] The clients 110 can be computing devices that are configured with embodiments of the client component of the anonymity protocol of the present disclosure and that are configured to communicate with the relay 120 via wired and/or wireless communication. For example, the clients 110 can include personal computers, workstations, tablets, mobile phones, laptops, and/or servers that are configured with the client component of the anonymity protocol and that communicate with the relay to access a network 140. The trustee devices 130 can be part of or accessible via the network 140.

[0038] The relay 120 can form an access point (e.g., the access point to a local area network, a wide area network, etc.) that connects the clients 110 (either directly or indirectly) to a network (the local area network or the wide area network) to facilitate communication with other local or remote sites 140 (e.g., to the Internet) via the network. For example, the relay 120 can be a router, a server, a hub, or other device through which other (client) devices connect to a network. The relay 120 can process TCP/IP traffic in addition to implementing embodiments of the relay component of the anonymity protocol of the present disclosure. The relay 120 can be a trusted or untrusted relay. A trusted relay refers to a relay that is generally known as a relay that does not actively attempt to defeat the anonymity of the clients. An untrusted relay refers to a relay for which it is generally unknown whether the relay actively attempts to defeat the anonymity of the clients or which is known to actively attempt to defeat the anonymity of the clients. [0039] The trustee devices 130 can be distributed around the world to maximize trustworthiness and can assist the relay in the anonymization process via implementation of embodiments of the anonymity protocol of the present disclosure. In exemplary embodiments, the trustee devices 130 are assumed to satisfy requirements of an anytrust model in which at least one of the trustee device 130 is honest, and each of the trustee device are assumed to be available at all times, but the clients 110 need not know which server to trust. That is, exemplary embodiments of the present disclosure are configured to preserve the anonymity of the clients 110 even when all but one of the trustee devices has been compromised by an adversary.

[0040] In some embodiments, the role of the trustees can be played either by dedicated, separate devices (e.g., dedicated trustee devices) or by the client devices themselves (e.g., the operation and function of the trustee can be incorporated in the clients such that there are no separate trustee devices). This choice represents a tradeoff between performance, scalability, and deployment simplicity concerns. In an embodiment with a large number of client devices, having a separate, small set of trustee devices increases the system's scalability and minimizes computation load on the client devices (which may often be low-power mobile devices). This is because in each round of communication, each client device computes only one ciphertext for each of a few separate dedicated trustee devices, rather than one ciphertext for each of the many other clients (e.g., for embodiments where client act as trustees as well). Embodiments in which the clients play a dual role of client and trustee (e.g., a client acts as the trustee as well) are feasible and equally secure. In such embodiments, there can be exactly as many trustees as clients, and no separate (dedicated) trustee devices are needed. Such an embodiment can be advantageous in terms of making deployment simpler and less costly. For example, in situations in which there are not too many client devices in one group or "channel" (and hence scalability is less of an issue), dedicated trustee devices may not be needed and the resources on the clients may not be substantially effected (e.g., where the number of clients does not greatly exceed the number of trustee devices that would be implemented in the system anyway). When each client plays the role of one trustee, the system remains secure because, from the viewpoint of any client, the trustee that the client itself implements is always "trustworthy" with respect to that client, so the "anytrust" assumption that at least one trustee (its own) is trustworthy is always satisfied from the perspective of any client.

[0041] Users, via their client 110, can perceive embodiments of the anonymity protocol as a low-latency VPN service in that it facilitates receipt of data from, and transmission of data to, the applications running on the clients 110. The relay 120 can act as the other end of the VPN, sending data to other local devices, remote devices (e.g., the Internet), or to the clients 110. However, unlike traditional VPN services, the relay 120 may not be trusted and may maliciously (possibly by colluding with other untrusted entities) attempt to de-anonymize the clients 110. The anytrust group of the trustee device 130 can collectively facilitate the protection of the clients 110 from de-anonymization by the VPN service, without adding latency into the critical communication path.

[0042] The component of the anonymity protocol can be executed jointly by the clients 110, the relay 120, and the trustee devices 130 to anonymize messages sent by the clients to, e.g., the Internet. The components of the anonymity protocol can be executed by the clients 110, the relay 120, and the trustee device 130 in rounds, where one of the clients sends a data message anonymously to another device via the relay in each round. The anonymity protocol facilitate sender anonymity of upstream communications from the clients 110 based on ciphertexts received from the clients 110 and trustee devices 130 for each round and facilitates receiver anonymity of downstream communication by broadcasting the downstream communications from the relay 120 to each of the clients 110 for each round.

[0043] Before the anonymity protocol starts, each of the clients 110 and each of the trustee devices 130 can go through a setup process to establish pairs of public/private keys. The relay 120 stores a roster of all the public keys, which allows the relay 120 to verify the membership of the clients 110 to the relay 120 (as an access node to the network) and verify the authenticity of communications flowing through the relay 120.

[0044] In an exemplary operation, an anonymization process implemented in response to execution of embodiments of the anonymity protocol of the present disclosure can include three phases: a setup phase, a scheduling phase, and an anonymization phase. In the setup phase, the clients 110 are authenticated by the relay using their public keys. Then, each of the clients 110 executing the client component of the anonymity protocol agree on a shared secret with each of the trustee devices 130 executing the trustee component of the anonymity protocol. The shared secret between a client and a trustee device is known to both of them, but is secret to other clients and trustee device and is secret to the relays. In exemplary embodiments, a client shares a different secret with each of the trustee devices 130 such no trustee device share the same secret with another trustee device for a particular client 110. The secrets are used later to seed a cryptographic pseudo-random generator (PRNG) to obtain a stream of pseudo-random bits, the pads, from which the clients 110 and the trustee devices 130 compute their ciphertexts.

[0045] FIG 2 illustrates a relationship between shared secrets, pads, and ciphertexts. As described herein, each client ci runs a key exchange protocol with each server sj to agree on a shared secret, rij £ {0, 1 }P, which is only known to both of them. Each shared secret 202 is used to seed a pseudorandom generator (PRNG) 204 to obtain a stream of pseudorandom bits, the pads 206, from which the clients and the servers will compute their ciphertexts 208. In exemplary embodiments, the pads 206 and ciphertexts 208 can depend on the round t, which can be input to the PRNG 204. Using this approach, clients and servers do not need to generate a shared secret for every slot.

[0046] Referring again to FIG. 1, In the scheduling phase, the relay 120 executes the relay component of the anonymity protocol to determine which of the clients 110 gets to transmit a message in which round of communication. The anonymity protocol proceeds in time slots such that only one client - the slot owner - is allowed to send an /-bit anonymous message to the network 140 (e.g., the Internet) in each time slot. A schedule consists of n ordered time slots (one for each client). An epoch is the timespan where the configuration (i.e., share secrets and schedule) of the anonymous network does not change. At the beginning of each epoch, a new schedule is established. Epochs expire after a predetermined period of time (e.g., 10 minutes) to prevent clients from using the same slot for an extended period, thus reducing the chances of adversary linking upstream messages to a particular slot. Epochs can also expire due to network churn, e.g., clients connecting or disconnecting from the system. A round corresponds to one exchange between the clients 110 and the relay (n ciphertexts upstream yielding one upstream message, and one downstream message).

[0047] In the scheduling phase, to achieve forward secrecy, each of the clients 110 generates an ephemeral pair of public/private keys that are used instead of his long-term keys in the anonymization phase. The ephemeral keys are transmitted to the trustee devices 130 and are only used for a small number of rounds or an epoch, and they are refreshed by the clients 110 in response to execution of the client component of the anonymity protocol whenever the relay 120 requests to repeat the scheduling phase. The scheduling information (e.g., which client gets to send a message in which round) remains secret to all entities, as otherwise it can completely break the anonymity of the clients. In exemplary embodiments, the trustee devices 130 execute the trustee component of the anonymity protocol to randomly and verifiably shuffle a sequence of ephemeral public keys corresponding to the clients 110. The secret permutation of ephemeral public keys is then sent to the clients 110. Each of the clients 110 are only able to recognize their own public key in the sequence of ephemeral public keys, while the other keys look unrelated to any of the other clients without the associated private key. The sequence of public keys defines in which of the rounds a client get to transmit a message.

[0048] In the anonymization phase, each of the trustee devices 130 continuously computes random ciphertexts for each of the clients 110. Each ciphertext consists of random /-bits, the pads, generated using a PRNG seeded with the secret that a respective one of the trustee devices 130 shares with one of the clients. That is, the shared secret from each of the clients 110 is used by each of the trustee device 130 to generate ciphertexts to be used for each round. Each trustee device combines its set of ciphertexts for a given round (the individual ciphertexts generated by the trustee device for each client) into a trustee combined ciphertext before sending the combined ciphertext to the relay 120. After combining the ciphertexts, the trustee devices can send the trustee combined ciphertext to the relay for a round. The individual ciphertexts can be combined using one or more techniques. As one non-limiting example, a trustee device can combine the individual ciphertexts using an exclusive-or (XOR) operation. To illustrate this approach, if there are ten clients, each trustee produces a set of ten separate ciphertexts - one based on its shared secret with each client, and then XORs all ten of the ciphertexts together to produce only a single trustee combined ciphertext, which it then sends to the relay. This saves bandwidth from trustee devices to the relay and even more importantly, provides security to the system, because the cryptographic entanglement of the ten ciphertexts into a single trustee combined ciphertext from the [honest] trustee (in the anytrust model) prevents a malicious relay from learning anything about which client sent an anonymous message in that round. The individual ciphertexts and trustee combined ciphertexts can be generated after the secrets are shared with the trustee devices 130 and before the rounds begin.

[0049] The ciphertexts generated by the trustee devices do not depend on actual communicated content. Therefore, the trustee device 130 can compute their ciphertexts ahead of the time before the ciphertexts are needed by the clients 110 and/or the relay 120 where there is actual communications being sent. This advantageously eliminates an important latency bottleneck from the critical latency path of the anonymity protocol. The trustee devices 130 can continuously transmit freshly-produced ciphertexts to the relay 120 throughout the rounds. For trustee devices 130 with a high throughput link to the relay 120, the arrival of their ciphertexts can outpace the rate of exchanges being performed by the clients 110 and the relay 120, reducing protocol latency.

[0050] In exemplary embodiments, even if the trustee devices 130 are geographically dispersed around the world, the end-to-end latency of connections between clients and local or remote sites is dominated purely by "single-hop" communication via the relay. Thus, the trustee devices add security to the anonymity of clients, but not to the latency of the network, because the trustee devices are not on the critical latency path of the anonymity process.

[0051] In every round, each of clients 110 computes a client combined ciphertext and sends the client combined ciphertext to the relay 120, where one of the clients 110 can send a client combined ciphertext that contains an upstream message to be sent to, e.g., the Internet, and the remaining clients send client combined ciphertexts including an empty message that does not include an upstream message. To convert a message into a client combined ciphertext, the client first computes trustee ciphertexts locally using a cryptographic PRNG seeded with the secrets that the client shares with each of the trustee device 130. Then, the client computes a client ciphertext that includes the upstream message. The trustee ciphertexts and the client ciphertext are combined to form the client combined ciphertext. As a non-limiting example, the trustee ciphertexts and the client ciphertext can be combined using an exclusive OR operation that receives each of the trustee ciphertexts and the client ciphertext and outputs an exclusive OR of the inputs which forms the client combined ciphertexts. If the client is not scheduled to transmit an upstream message during a current transmission slot/round, or if the client is scheduled to transmit an upstream message, but has no upstream message to send in the current round, the sends a client combined ciphertext that is formed by combining the trustee ciphertexts alone (i.e., as if the message consisted of all 0 bits).

[0052] The anonymization phase is repeated several times and the clients 110 take turns sending their upstream messages in a round-robin fashion based on the shuffling information computed in the scheduling phase. If the current round number modulo n points to a client's public key in the shuffled sequence of all public keys, then the round belongs to the client and the client sends an upstream message in a client combined ciphertext to the relay 120 for the round. Otherwise, the client sends a client combined ciphertext representing an empty message to the relay for the round. Each of the trustee devices 130 also sends their trustee combined ciphertext to the relay 120 for the round. The relay 120 then participates in the distributed anonymity protocol jointly with the trustee devices 130 to obtain the upstream message from the collected ciphertexts. Each round can be given a round identifier (ID) such that an upstream message transmitted during a round can be associated with a round ID. When the relay receives a downstream message in response to an upstream message, the relay 120 can transmit the downstream message and the associated round ID to each of the clients 110 (i.e. as a broadcast message), and the client that sent the upstream message can use the round ID to determine that the downstream message was intended for the client device (which can allow the client to render the content of the downstream message on a display, store the content of the downstream message in memory, etc.). The remaining clients can ignore the downstream message if the round ID does not correspond to the round in which they sent their upstream message.

[0053] In the case of churn, e.g., if any of the clients 110 or the server 130 disconnect from the relay 120, or a new client requests to join the anonymous network, the relay 120 broadcasts a set-up request to all nodes (e.g., servers and clients connecting to the relay 120). Upon receipt of the set-up request, each node finishes the current anonymization round, and re-runs both the set-up and scheduling phases. Hence, a resynchronization signals the start of a new epoch. Churn can significantly affect network performance. For example, the disconnection of a single client invalidates all the ciphertexts in the current round. Two types of client churn can be defined: (1) graceful churn, where a client gracefully announces to the relay their intent to connect or disconnect from relay; and (2) abrupt disconnections, where a client abruptly disconnects from the relay without sending any warning to the relay.

[0054] To mitigate the effect of churn in the anonymous network, the anonymity protocol includes a delay-and-reconfiguration approach to handle graceful churn without communication disruption. When a client notifies the relay 120 that it intends to connect or disconnect from the relay 120, a resynchronization phase can be triggered at the relay 120, in parallel to the current anonymization phase, thus maintaining the communications in a current round. The joining or disconnecting client sends a request to the relay 120, which starts new setup and scheduling phases with the new set of clients, as a background process, while maintaining the current anonymization phase with the old set of clients. Once each client in the new set of clients starts the new anonymization phase (hence, clients in both set run two concurrent anonymization protocols), the relay 120 terminates the anonymization phase associated with the old set of clients. This approach enables interruption-less handling of graceful client churn, by temporarily processing two anonymization phases concurrently until the new set of clients has established anonymous communications and until the old set of clients has completed its round. Using this approach, the relay 120 does only one additional signature check, each server has to run an additional verifiable shuffle protocol, and each client has to generate two new pairs of keys, which can be generated in advance, so that the keys are available in case a churn occurs. All the nodes then have to exchange this information over the network, resulting in a total communication of only 0(m + n), where m is the number of servers and n is the number of clients.

[0055] In the case of abrupt disconnections, where a client disconnects unexpectedly from the relay 120, the current anonymization round is disrupted, and the upstream message x is lost. In response to the abrupt all nodes cease their current involvement in the anonymous network, and perform new set-up and scheduling phases.

[0056] When the relay 120 is an untrusted relay, the relay 120 can attempt to perform equivocation attacks on the clients 110 by sending different (inconsistent) downstream messages to the clients 110 to de-anonymize them. For example, in an unencrypted communication, the relay 120 can slightly modify the downstream message for each of the clients 110, and therefore can send a unique message to each of the clients. Then, in the next round, the relay 120 can check to see what is being requested by the clients 110, and depending on the content requested, the relay 120 may be able to identify some of the clients 110. However, exemplary embodiments of the present disclosure can prevent such equivocation attacks without adding extra latency to the communication by encrypting each of the clients' messages to the relay 120 in the next round in such a way that the ciphertext generated by the clients 110 according to the client component of the anonymity protocol can depend on previous downstream messages received by the clients 110 from the relay 120. Therefore, the relay 120 can only decrypt each upstream message if each of the clients agree on what they received in one or more past downstream rounds. This allows the clients 110 to ensure they are receiving the same message without imposing the expensive overhead of, e.g., a consensus protocol.

[0057] Even if an adversary cannot directly link a client to a set of actions, the adversary can attempt to run intersection attacks by guessing based upon online clients; especially since members of an organization must identify themselves. However, exemplary embodiments of the present disclosure can address such attacks through pseudonymity provided by anonymous authentication mechanisms that allow members of an organization prove their membership to the network without divulging their identity.

[0058] To support different quality-of-service (QoS) levels, the anonymity protocol can be executed by the clients 110, relay 120, and servers 130 to enable clients to subscribe to one or more channels supported by the relay 120 such that the relay can maintain several anonymous phases concurrently (e.g., one or more for each channel). As one example, each channel can support a different bitrate. Each channel can be an isolated instance of the anonymity protocol, but can run with different transmission rates and payload sizes. In this way, constrained devices (e.g., suitable IoT devices, battery-powered devices) that require little computation can join channels with lower bitrates ("slow" channels) and more powerful devices can join channels with high or low bitrates. In some embodiments, the channels can correspond to categories of traffic, for instance "e-mails", "web browsing", "VoIP" and "video conferencing". With this approach, a client device that has no VoIP capabilities can save resources by joining a channel that does not support or require VoIP capabilities.

[0059] Client devices can connect to several channels and can participate in the anonymity set of those channels, even if the connected device choose only to communicate using one of channels (e.g., send messages carrying actual requests/data as opposed to dummy messages). This approach can increase the anonymity set of slower channel. Assuming an order of magnitude difference in terms of latency between channels (e.g., web browsing at 100ms, VoIP at 10ms latency), joining an additional slower channel can add 1 message every 10 messages on the fast channel.

[0060] Exemplary embodiments of the present disclosure can utilize an accountability mechanism configured to be compatible with embodiments of the anonymity protocol to retain low-latency communications via the relay 120. For example, rather than allowing clients to freely subscribe to various channels, the relay 120 and/or client executing the anonymity protocol can determine which channels the client can use. As an example, some client devices may be low-bandwidth, unreliable, and/or have high- latency connections to the relay (remote clients using the relay as a VPN server will be the quintessential examples of this), and putting those "bad" clients in the same channel as "good" (high-bandwidth, reliable, low-latency) clients can limit the performance seen by all clients in the group to the least-common denominator. Thus, "bucket" clients into channels so that high-powered clients can get good performance (though anonymity only within the smaller group of similarly high-powered clients), while lower-powered clients can still access the system (and get anonymity within a larger anonymity set including more clients). Additionally, grouping clients into different channels can also combat a malicious client attempting to render a channel useless by continuously transmitting upstream messages in every round to try to cause an untraceable denial-of-service attack. Some non-limiting examples of potential channels include a channel for web browsing, voice-over-IP, video conferencing, or web streaming. Furthermore, as described herein, clients that have sufficient bandwidth and low enough latency can participate in as many communication channels as possible, but embodiments of the anonymity protocol can be implemented by the clients 110, relay 120, and/or trustee devices 130 to permit the clients 110 to only transmit their cleartext in the appropriate channels. This allows embodiments of the anonymity protocol to provide a strong level of anonymity while supporting clients with different constraints (e.g., battery- powered devices).

[0061] The following provides a formal definition of the anonymization process implemented by the clients 110, relay 120, and trustee device 130 upon execution of their respective components of embodiments of the anonymity protocol of the present disclosure.

[0062] Notation: Let CI , .., Cn denote the clients, R denote the relay, SI , S _m denote the trustee devices, £ denote the bit-length of ciphertexts sent by clients and trustee devices to the relay in each round, and M denote a message sent to the relay from a client.

Setup

(1) R authenticates Cl-Cn using the public keys associated with Cl-Cn;

(2) Cl-Cn each run a key exchange algorithm with each of Sl-Sm to agree on a shared secret.

Scheduling (1) Each client Q generates an ephemeral pair of public/private keys (Z , z ), sends Z to R, and sets the round number r <— 0;

(2) R collects all Z 's as a sequence A and sends it to SI ;

(3) Sl-Sm each take turns shuffling A and Sl-Sm each send results of the shuffle and proof to other Sl-Sm via R;

(4) Sl-Sm each verify the shuffles, signs them with their respective private keys, and sends the signature to Cl-Cn via R for verification.

Anonymization

(1) Sl-Sm each generate an £-bit random ciphertext for each of Cl-Cn using a PRNG seeded with the secret shared with the each Cl-Cn and sends the ciphertext to R;

(2) Each client Ci performs the following: a. For each of Sl-Sm, generate an £-bit random ciphertext using a PRNG seeded with the secret shared with each of Sl-Sm;

b. Let π be the permutation generated by the scheduling phase. If r mod n = π(ί), then

M <— Client's next £ bits of data. Otherwise, M <— £ zero bits; c. Xor M with all server random ciphertexts and send the result to R;

d. r <— r + 1 ;

(3) R collects one ciphertext from each of Sl-Sm and each of Cl-Cn, Xors them together to obtain a plaintext (upstream message), and sends the plaintext to the Internet;

(4) Upon receiving a response from the Internet, R broadcasts the downstream message to all clients; (5) If any client or trustee device disconnects, R broadcasts a Reschedule request to Cl-Cn and Sl-Sm;

(6) If any client or server receives a Reschedule request from R, the receiver repeats the Scheduling phase.

[0063] Exemplary embodiments of the anonymity protocol can implement a disruption- protection protocol that can be executed to prevent or mitigate disruption attacks from the clients 110 and/or the servers 130. In one example of a disruption attack, a malicious client or server can transmit arbitrary bits to the relay - instead of the XORed ciphertext defined by the anonymity protocol - as an attempt to corrupt the upstream messages of other clients without leaving a trace. While affected client(s) can be configured to detect such an attack and switch to a different relay, a moderately powerful adversary can feasibly infiltrate groups of clients at a large portion of relays in a given region such that affected client(s) can be forced to use weaker communication channels.

[0064] To prevent or mitigate disruption attacks in exemplary embodiments of the anonymous network, the disruption-protection protocol can be executed by the relay 120 to detect a disruption attack. As described herein, during the scheduling phase, the relay 120 establishes a shared secret, ¾, with each of the clients. For instance, the relay can generate a unique shared secret for each client and can encrypt the shared secret with the public key of each corresponding client (i.e., the pseudonym used in the schedule). The server broadcasts the encrypted shared secrets and the clients decrypt them with their corresponding private keys. The client owning the current slot uses this shared secret to compute the keyed-hash message authentication code (HMAC) of the upstream message, HMAC(riR, x). Next, the client sends the upstream message and its HMAC to the relay 120. The relay 120 validates the HMAC to find evidence of a disruption attack. If the validation fails, the relay 120 indicates, via a downstream message to the clients 110, that a disruption has been detected and that, in the same slot of the next schedule, a verifiable network, such as a variable DC- net, should be used to prevent further message corruption (for performance reasons, the relay 120 can wait for a few schedules before requesting the use of a verifiable DC-net). By configuring the relay 120 to detect disruption attacks, the work and responsibility of detecting disruption attacks is removed from the clients 110; thereby decreasing operational complexity and resource utilization of the clients 110, which can be particularly beneficial for resource constrained clients (e.g., battery powered, mobile devices). Configuring the relay 120 in this manner is possible because the relay 120 is trusted for availability, i.e., the relay does not perform attacks or collude with other parties to reduce availability of the network (while the relay may be untrusted with respect to de-anonymizing a client).

[0065] Once a disruption attack has been detected, the relay 120 only needs to find one flipped bit to identify and exclude the malicious client or server launching the attack. In exemplary embodiments, the relay 120 finds a bit in the pads or ciphertexts that was '0' in an original message, but has been flipped to T (using a bit that was 1 and has been flipped to 0 leaks information about the slot owner). After the relay 120 finds a flipped bit, the relay 120 compares the original and corrupted upstream messages to find the position p of a flipped 0- bit (i.e. flipped from 0 to 1) in the corrupted messages. Once such a bit is found, the relay 120 stops communications (i.e., ceases the anonymous protocol) and sends a signed request to the clients 110 and servers 130 to reveal the individual bits from their different pseudorandom pads at position p for the disrupted round. In response, the clients 110 reveal one bit per server and the servers 130 reveal one bit per client corresponding to the position p in their pseudorandom pads. If no flipped 0-bit is found, the relay 120 stops the disruption protection protocol of the anonymity protocol and communications are not interrupted, i.e., the attack is detected, but the disruptor cannot be traced without breaking anonymity guarantees. To reduce the chances of a disruptor flipping only 1-bits (e.g., the adversary could guess parts of the content in the upstream message), the client can XOR the upstream message with the shared secret ¾. Therefore, the adversary only has a fifty percent chance of flipping a 1-bit (i.e. flipped from 1 to 0).

[0066] Upon receiving the bit-revealing messages from the clients 110 and servers 130, the relay 120 proceeds to check whether a client or server revealed values in their respective messages that do not match with the value sent in the bit position p during the disrupted round. If the values do not match, the corresponding client or server is identified by the relay 120 as the disruptor and is excluded from the anonymous network. If no mismatch is found, the relay 120 proceeds to compare the bits revealed by the clients 110 with the bits revealed by the servers 130. There must be, without loss of generality, a difference among one of the bits that one of the clients 110 and one of the servers 130 revealed (otherwise, the round was not disrupted). After the relay 120 identifies a mismatch between a client and server, the relay 120 requests that the client and server reveal their shared secret, ry, along with a zero- knowledge proof showing that it was computed correctly. The relay 120 verifies the proofs and seeds the PRNG with the secrets to generate the pad for the disrupted round. At this point, the relay 120 can determine which one, the client or the server, disrupted the round and can exclude the disruptor from the anonymous network. Since at least one of the client or the server is the disruptor, revealing the shared secrets to the relay 120 does not compromise anonymity, as such revelation never happens between two honest parties.

[0067] As described herein, an untrusted relay can equivocate by sending different downstream messages to different clients to de-anonymize them. For example, in an unencrypted communication (e.g., a DNS request), the relay 120 can slightly modify the downstream message for each client. These unique messages might affect the messages sent in subsequent rounds (e.g., the contacted IP in the case of a DNS request), so the relay 120 may be able to determine which client sent the request, based on their subsequent behavior.

[0068] As a non-limiting example of an equivocation attack that can be launched to de- anonymize a client, clients CI and C2, both honest, can connected to a malicious relay, and they collectively run an embodiment of the anonymous communication protocol. In the first round, the relay 120 decodes a DNS request for a given domain. As the request was sent using the anonymous communication protocol, the sender of the request is anonymous, such that the relay 120 does not know whether client CI or C2 sent the request. Instead of broadcasting the same DNS answer to client CI and C2, the relay 120 can send two different answers to client CI and C2, containing IP1 and IP2, respectively. Subsequently, the relay 120 can decode a request to IP2 and can guess that client C2 made the request (along with the original DNS request), as it is unlikely that client CI has knowledge of IP2.

[0069] Exemplary embodiments of the anonymity protocol can be implemented to include an equivocation-protection protocol to protect against equivocation attacks launched by a malicious relay without adding extra latency to the network. This is achieved by encrypting clients' upstream messages in such a way that the resulting ciphertexts depend on the history of downstream messages in a epoch. As a result, the relay 120 can only decrypt an upstream message if all clients agree on the downstream messages they have received in the current epoch. If the clients disagree, the relay 120 is unable to decrypt the upstream message from the current and future rounds. In such a case, the relay 120 is required to issue a special command to reset the history of all clients and restore the communications. Such a command should be issued rarely by the relay 120 and, the clients 110 should be suspicious of it. Hence, the relay 120 has no incentive to try an equivocation attack, which would be detected by clients and would affect the availability of the service.

[0070] As a non- limiting example of the equivocation protocol, in each round, the client-slot owner encrypts its upstream message with a fresh random key and includes a blinded version of this key in its upstream message. The key is blinded with a value computed by raising the downstream history value to a secret exponent derived from the client' s pads. The downstream history consists of the cryptographic hash of the previous downstream history concatenated with the most recent downstream message, hence, it depends on all past downstream messages. Moreover, the downstream history is "bound" to the client's pads via exponentiation in a cyclic group, where the Discrete Logarithm Problem (DLP) and the Decisional Diffie-Hellman assumption (DDH) hold. Other clients also send contributions and, if all clients have similar downstream history, the relay 120 is unable to unblind the key and decrypt the upstream message. When new clients join the system, the relay 120 provides them with the current downstream history value during the setup phase. The downstream history can only be reset by the relay 120 via a reset-history command broadcasted to the clients; thus, the downstream history is kept across epochs.

[0071] The following provides a formal definition of the equivocation-protection protocol executed by the clients 110, relay 120, and trustee devices/servers 130 upon execution of their respective components of embodiments of the anonymity protocol of the present disclosure.

[0072] Let F _q denote a finite field of prime order q, and let G denote a multiplicative group of order q with generator g such that the DLP and the DDH assumptions hold in G. Also, let Mi denote the message that a client i sends to the relay. Let H : {0, 1 }* -> {0, 1 } 1 be a cryptographic hash function, and Fl : {0, 1 }1 -> G and F2 : {0, 1 } 1 -> F _q be publicly-known one-to-one functions that are efficiently computable and invertible.

[0073] The portion of the equivocation protocol implemented by the client can be defined as follows. Consider m servers, n clients and a client Q with a plaintext x _; and an empty downstream history t¾.

aflii sends ( ¾ _» .fei) ϊ ΐίϊβ i¾lay .

[0074] Using the above protocol, the client Ci encrypts x _; (i.e., the upstream message) as x' _i5 and blinds ¾ with its downstream history. The blinding also uses the hash of the pads (unknown to the relay), so the relay is unable to unblind the key without the contribution (and agreement) of all clients.

[0075] In the portion of the equivocation protocol implemented by the server, the server sends an additional value O _j to the relay 120, used to unblind ¾. The portion of the equivocation protocol implemented by the server can be defined as follows. Each server S _j sends (oj, Sj) to the relay 120, where: n

[0076] In the portion of the equivocation protocol implemented by the relay 120, the relay 120 unblinds the key and decrypts the upstream message. The portion of the equivocation protocol implemented by the relay 120 can be defined as follows. The relay 120 starts with an empty downstream history denoted by h.

( 1 ) Upon receiving a downstream message a! for the clients, the

relay sets h <-~ H(h \d).

(2) Upon receiving ( i^ ciJ's from all clients and. ¾ 's from all

servers, ^' the relay decrypts the owner's message from:

y *- It Φ t ¹ (k) .

(3) The relay sends to the corresponding Internet address.

[0077] In some instances, a malicious client or relay might try to falsely accuse the other in an attempt to defeat the anonymity of the network. For example, to frame the relay 120, a malicious client can pretend to have received a downstream message different from other clients (i.e., may implicate that the relay 120 has launched an equivocation attack). Similarly, a malicious relay may pretend that an honest client is sending wrongly-computed ]¾ to cause a denial-of-service (DoS) attack. Exemplary embodiments of the present disclosure solves these problems by requiring that both the clients 110 and the servers 130 sign every message they send using their public key. When a problem occurs, honest nodes (clients, relay, servers) are protected from incorrect blaming (assuming that no node can forge signatures).

[0078] A malicious client or server may also send a wrongly computed ki to cause an anonymous denial-of-service (DoS) attack. The requirement that each message be signed by the sender cannot prevent such an attack because the relay is unable to validate the correctness of the ki values. Assume that the blinding key has a recognizable structure, e.g., a header. To detect this anonymous DoS attack and trace the disruptor, the relay 120 can execute the equivocation-protection protocol to detect the DoS attack by checking the structure of the blinding key k obtained. If the blinding key' s structure is incorrect, the relay 120 determines that an attack is in place and follows a procedure similar to the disruption protection protocol described herein. That is, the relay 120 stops the communications and sends a signed request to the clients 110 and servers 130 requesting that the clients 110 and servers 130 reveal the hash of the pads H(pi _j ) used to compute their current ¾ values. If the relay 120 determines that there is a mismatch between a k, and the H(p _y ) values sent by a client or server, the relay 120 considers this client or server to be the disruptor. Otherwise, the relay 120 compares the H(pi _j ) values revealed by the clients 110 with those revealed by the servers 130. There must be a difference, WLOG, among one of the H(pi _j ) values revealed by one client and one server. After the relay 120 identifies a mismatch between a client and a server, the relay 120 requests that the client and server associated with the mismatch reveal their shared secret ry, along with a zero -knowledge proof showing ry was computed correctly. To generate the pads for the disrupted round, the relay 120 seeds the PRG with these secrets. At this point, the relay 120 can determine which one, the client or the server, disrupted the round and can exclude the disruptor from the anonymous network.

[0079] Even if an adversary cannot directly link messages to a client (de-anonymize a client), it can attempt to run intersection attacks by monitoring the set of online clients (usually public information), and correlating the set of online clients with the anonymous message sent. This scenario is especially plausible in the case of members of an organization identifying themselves to access the network. To solve this problem, the anonymity protocol can use an anonymous authentication mechanism, such as the Deniable Anonymous Group Authentication (DAGA) protocol. Using an embodiment of the anonymous authentication mechanism, during authentication, client/members prove that they own a private key that corresponds to one of the group public keys, without revealing which one. With anonymous authentication, an adversary is unable to easily tell whether a client is online; thereby enhancing the tracking-resistance of the anonymous network form using the anonymity protocol.

[0080] Exemplary embodiments of the anonymity protocol executed by the clients 110, relay 120, and servers 130 can advantageously address the problems associated with trade-offs between anonymity and latency in anonymous networks by providing cryptographically- strong tracking protection for sender anonymity with unnoticeable "single-hop" network latencies by leveraging a client-relay-server architecture, in which the clients 110 execute a client component of embodiments of the anonymity protocol described herein, the relay 120 (trusted or untrusted) executes a relay component of embodiments of the anonymity protocol described herein, and trustee devices 130 execute a trustee component of embodiments of the anonymity protocol described herein. Embodiments of the anonymity protocol are advantageously configured such that trustee device add little to no latency to the network. Exemplary embodiments of the anonymity protocol executed by the clients can also provide for strong receiver anonymity to protect against equivocation attacks.

[0081] FIG. 3 is an exemplary networked environment 100' including multiple relays in accordance with embodiments of the present disclosure, where each relay can implement embodiments of the anonymity protocol to form separate anonymous networks. The network environment 100 can include the clients 110, relays 120A and 120B, and the trustee devices 130 (e.g., trustee devices). Each of the clients 110, relays 120A-B, and trustee devices 130 can be configured with an embodiment of the anonymity protocol or portions thereof that can be implemented to facilitate anonymous, low-latency, tracking-resistant communications in the networked environment 100 as described herein. The relays 120A and B can be implemented in a wireless access point that has a certain number of radio interfaces that can support a finite number of clients.

[0082] The relays 120 A and B can be disposed in proximity to one another such that the clients 110 can be within range of the relays 120A and 120B and can connect to the network through either of the relays 120A or 120B. The relays 120A and 120B can use the same trustee devices 130 (e.g., servers) and/or can use different sets of trustee devices. Adding relays in this manner can introduce several issues. As one example, if the two honest clients are connected to different relays (i.e., anonymity sets), they would have no anonymity at all (e.g., each relay is connected to only one honest client). As another example, the relay ability to evict clients can be used to deny service or slow down honest clients to affect the client's anonymity. To illustrate this, suppose that at a given physical location, a client can choose between two relays, R and R'. R is malicious and it has two honest clients connected (i.e., other clients are malicious and colluding with the relay). R evicts one of the honest clients, e.g., claiming that the client is slowing down the network, leaving only one honest client with no anonymity. In a single-relay scenario, this attack would be detected (the evicted client is likely to complain), whereas in a multiple-relay scenario, the evicted client is likely to automatically connect to R'.

[0083] To solve these and other problems associated with multi-relay embodiments of the present disclosure, a set of management servers can be utilized to control to which of the relays a client connects. The management servers can be one or more of the trustee devices 130 andor can be a separate set of servers. The management servers can utilize the anytrust model (i.e., at least one of the servers is honest). The management servers can perform an anonymous authentication mechanism, such as the Deniable Anonymous Group Authentication (DAGA) protocol, to assign freshly-authenticated clients to one of the relays. The assignment process can provide each client with a ticket, signed by the management server(s), specifying the relay to which the client can connect. In some embodiments, the management servers can use the a distributed randomness in the anytrust model, such as the RandHound protocol, to randomly and securely assign new clients to relays.

[0084] Using the management servers, a relay evicting a client becomes visible, as the client will have to request a new ticket to the management servers. Hence, there will be a trace of which relay evicted an anonymous client. Clients have administrative solutions (e.g., complaining to the IT services) and proofs (i.e., the issued tokens and the signed eviction request from the relay) of the abnormal behavior. Finally, the management servers can maintain logs that can be automatically analyzed for abnormal behaviors (e.g., several clients suddenly leaving a relay) and trigger the appropriate administrative responses.

[0085] FIG. 4 is a block diagram of an exemplary client 400 in accordance with embodiments of the present disclosure. The computing device 400 includes one or more non- transitory computer-readable media for storing one or more computer-executable instructions or software for implementing a client component 405 of the anonymity protocol. The non- transitory computer-readable media may include, but are not limited to, one or more types of hardware memory, non-transitory tangible media (for example, one or more magnetic storage disks, one or more optical disks, one or more flash drives), and the like. For example, memory 406 included in the computing device 400 may store computer-readable and computer-executable instructions or software for implementing exemplary embodiments. The computing device 400 also includes processor 402 and associated core 404, and optionally, one or more additional processor(s) 402' and associated core(s) 404' (for example, in the case of computer systems having multiple processors/cores), for executing computer- readable and computer-executable instructions or software stored in the memory 406 and other programs for controlling system hardware. Processor 402 and processor(s) 402' may each be a single core processor or multiple core (404 and 404') processor.

[0086] Virtualization may be employed in the computing device 400 so that infrastructure and resources in the computing device may be shared dynamically. A virtual machine 414 may be provided to handle a process running on multiple processors so that the process appears to be using only one computing resource rather than multiple computing resources. Multiple virtual machines may also be used with one processor.

[0087] Memory 406 may include a computer system memory or random access memory, such as DRAM, SRAM, EDO RAM, and the like. Memory 1306 may include other types of memory as well, or combinations thereof.

[0088] A user may interact with the computing device 400 through a visual display device 418, such as a computer monitor, which may display one or more user interfaces 420 that may be provided in accordance with exemplary embodiments. The computing device 400 may include other I/O devices for receiving input from a user, for example, a keyboard or any suitable multi-point touch interface 408, a pointing device 410 (e.g., a mouse). The keyboard 408 and the pointing device 410 may be coupled to the visual display device 418. The computing device 400 may include other suitable conventional I/O peripherals.

[0089] The computing device 400 may also include one or more storage devices 424, such as a hard-drive, CD-ROM, or other computer readable media, for storing data and computer- readable instructions and/or software that implement exemplary embodiments of the client component of the anonymity protocol described herein. Exemplary storage device 424 may also store any suitable information required to implement exemplary embodiments. For example, exemplary storage device 424 can store public keys, private keys, previous downstream messages, shared secrets, ciphertexts, round IDs, and/or any other information to be used by embodiments of the client component of the anonymity protocol.

[0090] The computing device 400 can include a network interface 412 configured to interface via one or more network devices 422 with one or more networks, for example, Local Area Network (LAN), Wide Area Network (WAN) or the Internet through a variety of connections including, but not limited to, standard telephone lines, LAN or WAN links (for example, 802.11, Tl, T3, 56kb, X.25), broadband connections (for example, ISDN, Frame Relay, ATM), wireless connections, controller area network (CAN), or some combination of any or all of the above. The network interface 412 may include a built-in network adapter, network interface card, PCMCIA network card, card bus network adapter, wireless network adapter, USB network adapter, modem or any other device suitable for interfacing the computing device 400 to any type of network capable of communication and performing the operations described herein. Moreover, the computing device 400 may be any computer system, such as a workstation, desktop computer, server, laptop, handheld computer, tablet computer (e.g., the iPadTM tablet computer), mobile computing or communication device (e.g., the iPhoneTM communication device), or other form of computing or telecommunications device that is capable of communication and that has sufficient processor power and memory capacity to perform the operations described herein.

[0091] The computing device 400 may run any operating system 416, such as any of the versions of the Microsoft® Windows® operating systems, the different releases of the Unix and Linux operating systems, any version of the Android operating systems, any version of the MacOS® for Macintosh computers, any embedded operating system, any real-time operating system, any open source operating system, any proprietary operating system, or any other operating system capable of running on the computing device and performing the operations described herein. In exemplary embodiments, the operating system 416 may be run in native mode or emulated mode. In an exemplary embodiment, the operating system 416 may be run on one or more cloud machine instances.

[0092] FIG. 5 is a block diagram of an exemplary relay 500 in accordance with embodiments of the present disclosure. The relay 500 forms an access point to a network through which other devices can connect to the network. In some embodiments, the relay 500 can operate as a wireless and/or wired access point, a multi-port network switch, and an IP router. The relay 500 includes one or more non-transitory computer-readable media for storing one or more computer-executable instructions or software for implementing lower levels of communications protocol for receiving and transmitting data between devices including, for example, one or more layers of the TCP/IP protocol, and/or for implementing a relay component 505 of the anonymity protocol. The non-transitory computer-readable media may include, but are not limited to, one or more types of hardware memory, non- transitory tangible media (for example, one or more magnetic storage disks, one or more optical disks, one or more flash drives), and the like. For example, memory 506 included in the relay 500 may store computer-readable and computer-executable instructions or software for implementing exemplary embodiments.

[0093] While an example embodiment of the relay 500 is illustrated as a dedicated access point in FIG. 5, exemplary embodiments of the relay can be implemented by and/or embodied in any suitable device. For example, in an example embodiment, the relay can be a network appliance that is operatively coupled to an existing, conventional switch or router, where the network appliance can be programmed to implement the client component of the anonymity protocol to add anonymization capability (for compatible client devices) without modifying or upgrading a network's existing access points, switches, or routers. In such embodiments, the anonymization appliance may include a single port (or multiple ports) to connect to an existing switch/router, in the same way as a conventional server or other network appliances are often attached to networks. Such an embodiment may be less optimal from a performance perspective, but advantageous from a cost and ease-of-deployment perspective.

[0094] The relay 500 can include ports/channels 508 to facilitate wired and/or wireless communication between clients of the relay 500. For example, the one or more ports 508 can operate as local area network ports through which the clients connect to the local area network to which the relay 500 belongs. The relay 500 can also include port(s) 510 for connecting the relay to another network (e.g., a wide area network, the Internet, etc.) to facilitate communication between the clients of the local area network and remote computing devices (e.g., webservers) on the wide area network, the Internet, etc. The ports 508 and 510 can been associated with transceivers 512 that with transmitters configured to transmit data and receivers configured to receive data. The transceivers 512 can be realized as radiofrequency transceivers having antennas, optical transceivers, and/or electrical transceivers.

[0095] The relay 500 can also include switches 514 routing the data between the ports 508 and 510 and devices connected to the ports 508 and 510. A processor/controller 502 and associated core 504, and optionally, one or more additional processor(s) 502' and associated core(s) 504' can execute computer-readable and computer-executable instructions or software stored in the memory 506 and other programs for controlling relay hardware including the ports 508, 510, transceivers 512, and switches 514 based on the communication protocols and the relay component 505 of the anonymity protocol. Processor 502 and processor(s) 502' may each be a single core processor or multiple core (504 and 504') processor.

[0096] Memory 506 may include a computer system memory or random access memory, such as DRAM, SRAM, EDO RAM, and the like. Memory 406 may include other types of memory as well, or combinations thereof.

[0097] The relay device 500 may also include one or more storage devices 524, such as a hard-drive, CD-ROM, mass storage flash drive, or other computer readable media, for storing data and computer-readable instructions and/or software that can be executed by the processing device 502 to implement exemplary embodiments of the relay component 505 described herein. For example, the storage 524 can store public keys associated with clients, ciphertexts received from clients and/or trustee devices, upstream messages, downstream messages, and/or any other suitable information for implementing the relay component of the anonymity protocol.

[0098] FIG. 6 is a block diagram of an exemplary trustee device 600 in accordance with embodiments of the present disclosure. In the present embodiment, the computing device 600 is configured as a server that is programmed and/or configured to execute a trustee component 605 of the anonymity protocol. The computing device 600 includes one or more non-transitory computer-readable media for storing one or more computer-executable instructions or software for implementing exemplary embodiments. The non-transitory computer-readable media may include, but are not limited to, one or more types of hardware memory, non-transitory tangible media (for example, one or more magnetic storage disks, one or more optical disks, one or more flash drives), and the like. For example, memory 606 included in the computing device 600 may store computer-readable and computer-executable instructions or software for implementing exemplary embodiments of the trustee component 605 or portions thereof.

[0099] The computing device 600 also includes configurable and/or programmable processor 602 and associated core 604, and optionally, one or more additional configurable and/or programmable processor(s) 602' and associated core(s) 604' (for example, in the case of computer systems having multiple processors/cores), for executing computer-readable and computer-executable instructions or software stored in the memory 606 and other programs for controlling system hardware. Processor 602 and processor(s) 602' may each be a single core processor or multiple core (604 and 604') processor.

[00100] Virtualization may be employed in the computing device 600 so that infrastructure and resources in the computing device may be shared dynamically. A virtual machine 614 may be provided to handle a process running on multiple processors so that the process appears to be using only one computing resource rather than multiple computing resources, to provide an environment that emulates clients, and/or to perform functions and operations for and/or on-behalf of clients. Multiple virtual machines may also be used with one processor.

[00101] Memory 606 may include a computer system memory or random access memory, such as DRAM, SRAM, EDO RAM, and the like. Memory 606 may include other types of memory as well, or combinations thereof.

[00102] The computing device 600 may also include one or more storage devices 624, such as a hard-drive, CD-ROM, mass storage flash drive, or other computer readable media, for storing data and computer-readable instructions and/or software that can be executed by the processing device 602 to implement exemplary embodiments of the trustee component 605 described herein.

[00103] The computing device 600 can include a network interface 612 configured to interface via one or more network devices 622 with one or more networks, for example, Local Area Network (LAN), Wide Area Network (WAN) or the Internet through a variety of connections including, but not limited to, standard telephone lines, LAN or WAN links (for example, 802.11, Tl, T3, 56kb, X.25), broadband connections (for example, ISDN, Frame Relay, ATM), wireless connections (including via cellular base stations), controller area network (CAN), or some combination of any or all of the above. The network interface 612 may include a built-in network adapter, network interface card, PCMCIA network card, card bus network adapter, wireless network adapter, USB network adapter, modem or any other device suitable for interfacing the computing device 600 to any type of network capable of communication and performing the operations described herein. While the computing device 600 depicted in FIG. 6 is implemented as a server, exemplary embodiments of the computing device 600 can be any computer system, such as a workstation, desktop computer or other form of computing or telecommunications device that is capable of communication with other devices either by wireless communication or wired communication and that has sufficient processor power and memory capacity to perform the operations described herein.

[00104] The computing device 600 may run any server application 616, such as any of the versions of server applications including any Unix-based server applications, Linux-based server application, any proprietary server applications, or any other server applications capable of running on the computing device 600 and performing the operations described herein. An example of a server application that can run on the computing device includes the Apache server application. [00105] An experimental embodiment implementing the anonymity prototype was set up. The experimental embodiments relied on NIST P-256 elliptic curve for asymmetric cryptographic versus cell size operations, along with AES 128 bits for symmetric cryptography and SHA-256 as a hash function. An embodiment of the anonymity protocol was deployed to a lab environment infrastructure with all nodes (clients, relay, trustee devices) running on different machines with the same specifications: 2.4 GHz Intel Xeon X3 processor with 16 GB of RAM. The machines were deployed in two LANs, one for the trustee devices, with a latency of 100 ms, and one for the clients, with a latency of 10 ms. The measured latencies are 106 ±0.5 ms and 16 ±1 ms both over 10 samples, respectively. The relay belongs to both LANs. All network links were 100 Mbps full duplex.

[00106] The total anonymized upstream throughput was evaluated when varying the upstream cell size corresponding to the number of bytes sent to the relay per round and per client. To test the system capacity, one client and three servers were run and the upstream speed at which the client transmits was measure. In addition, the latency was measure as the round-trip time from the client to the relay, and back to the client. As shown in FIG. 7, the anonymity protocol can be executed by the clients, relay, and trustee devices to anonymize up to about 20 Mbps of traffic with a latency of 40 ms. In another experiment, a standard network pipelining was used to reach the maximal throughput of 100 Mbps with almost the same latency.

[00107] The time when no upstream traffic can be processed, which happens when one client abruptly disconnects or times out, was also evaluated (e.g., the time to reset/resynchronize). In some embodiments, the time to resynchronize can be managed by leveraging more computational resources, e.g., the anonymity protocol can continue to run, and a new instance can be ran in parallel to facilitate a resynchronization, where the pre-existing protocol can stopped when the new instance has been synchronized and is ready to communicate.

[00108] To measure the time-to-resync, the number of clients and trustees can be varied, and measuring can begin when the upstream traffic stops being processed and can stop when the traffic restarts. Measurements can start with two clients, and more clients can be progressively added; this also handles the case of client disconnection, as the resync protocol depends on the final number of clients (e.g. adding 1 client to a setup with n clients result in the same time-to-resync than 1 disconnection in a setup of n + 2 clients). Results are visible in FIG. 8A, which shows that the time-to-resync increases both with the number of clients and trustees. For a given number of clients, FIG. 8A shows the number of trustees that have a noticeable impact: this is because the oblivious shuffle used in round scheduling is inherently sequential; that is, each trustee does an operation in turn. For a given number of trustees, an increasing number of clients has only a moderate impact on the time-to-resync, meaning that this part of the protocol scales well with the number of clients.

[00109] Exemplary embodiments of the anonymity protocol can be executed in parallel, for example, by connecting to any relay (and exchanging public parameters such as: the cell size, the number of clients, etc.), and collecting the public keys from the clients in parallel. Results are shown in FIG. 8B. In the optimized embodiments, the time is mostly spent on the network communication with the trustees, and is close to the theoretic minimum

[00110] The total upstream anonymized throughput of the anonymity protocol was measured when varying the upstream cell size, or the number of bytes sent per round and per client. To test the system capacity, one client and three trustees were run, and the upstream speed that the client got was measured. In addition, the latency (defined as the round-trip time from the client, to the relay, and back to the client) was measured.

[00111] FIG. 9 shows that more throughput with bigger upstream cell sizes are obtained; reaching about 21 Mbps of throughput, along with the latency of about 40ms. After a cellsize of 110 KB, not only does the throughput stop increasing, but the latency increases drastically, as do the variance of the latency; this may a point of saturation of the experimental embodiment of the anonymity protocol.

[00112] To improve throughput, exemplary embodiments of the present disclosure can utilize windowing. Upstream and downstream traffic are not independent: clients need to make sure that a malicious relay is not trying to distinguish them by sending different pieces of information to different clients. For that purpose, clients usually share a hash of the history of the received messages. This means that the default way to send up and down cells is usually in lock-step: one cell upstream, one cell downstream, and so on. In a network where the bandwidth available is high, and the latency is moderate or high such a lock step approach can be modified to using windowing. The window mechanism can be akin to TCP, where a quantity of cells can be going upstream for each downstream cell. For example, a window W = 2, can allow two cells to be going upstream for one going downstream. When the first upstream cell is acknowledged, the third one is sent, and so on.

[00113] The trade-off between bandwidth and latency can be dynamically tuned by the relay based on the windowing, e.g., by controlling the value of W, without interrupting the protocol, thus allowing users' of the clients to adjust the bandwidth and latency following their needs. [00114] Furthermore, FIGS. 10A and 10B show that by introducing a window mechanism downstream traffic can be processed at around 85 Mbps, close to the network limit of 100 Mbps; hence, given the appropriate parameters, execution of the anonymity protocol is not the bottleneck on the global downstream (e.g. a video stream from a web server).

[00115] For characterizing node mobility, a well-known dataset from CRAWDAD was used. The dataset contains four hours of wireless traffic, recorded in a university cafeteria. Those traces contain the Data Link layer, and show the devices' association and disassociation requests. This dataset represents a pessimistic scenario, since node mobility is likely higher in a cafe than in an office or classroom The dataset contains 254 occurrences of churn over 240 minutes, in which there are 222 associations (33 unique devices) and 32 disassociations (12 unique devices).

[00116] Each device (dis)connection induces a re-synchronization (i.e Setup + Schedule) time of D milliseconds, where D depends on the number of servers M and clients N, and the latency needed to contact them We use the following approximation: 10ms for the clients (i.e. emulating a busy LAN), and 100ms for servers (located outside the LAN). FIG. 11 show typical values for D, which is in the order of seconds. Depending on the strategy, this time D is either direct downtime, or not if the re-synchronization happens in background. Three strategies are considered: the naive approach kills the communication for every churn, and devices experience a downtime of D; the abrupt disconnections approach uses the graceful approach presented above for connections (which can be enforced by the relay), yielding 0 downtime for connections, but assumes a worse-case scenario where all nodes disconnect abruptly (e.g they do not cooperate, or they experience some network failure), yielding a downtime of D; and the graceful only assumes no abrupt disconnections. It is an ideal scenario that cannot be guaranteed (e.g in case of a device running out of battery), especially since users have incentive to cooperate to maintain a good QoS for everybody.

[00117] Table 1 provides three metrics for each of these strategies: the first metric is the raw number of communication interruptions, which directly comes from the node mobility in the dataset. The second metric is the network availability percentage, computed as 1 - downtime divided by total time. The last metric is the maximum continuous downtime, the longest network interruption if the anonymity protocol is used with the aforementioned dataset. This last metric has direct impact on usability.

Interruptions Availability [%] MCD [s]

Naive 254 98.72792 1 .55147

Abrupt Disconnections 32 99.81778 0.82

Graceful only 0 100 0

Table 1

[00118] Using the anonymity protocol in an environment similar to the environment corresponding to the dataset would slightly decrease network availability, as churn induces global downtime. However, over four hours, between 0 and 32 global loss of communication occur, and the network availability ranges between 99.82% and 100%, depending on the disconnection types. Assuming the clients have incentives to disconnect gracefully (which improves the situation for everyone at a minimal cost), only network failures and other hardware problem yield global downtime. The longest disconnection period was 0.82 seconds in the worst case, which is noticeable by the users using time-sensitive applications (e.g., VoIP), but hopefully is a bearable cost for anonymity.

[00119] FIG. 12 is a graph that shows the size of the anonymity set versus the time, i.e., among how many participants a user is anonymous at any point in time. This is an essential anonymity metric that quantifies anonymity. [00120] In particular, the variations are interesting, as they show user mobility. A high variance means that while connected, a user risks being less anonymous if unlucky (and many people disconnect suddenly); should the size of the anonymity set drop to 1, anonymity would be lost.

[00121] In the analyzed scenario, the uninteresting linear component of the dataset is removed, which indicated that over the duration of the experiment more people joined the cafe than left. Then, the difference, in percentage, between the actual anonymity set size and the baseline tendency is shown. It can be seen that size of the anonymity set does not vary more than ±8%; The mean number of users is 50, hence, the worst-case of "anonymity loss" in that scenario is of four users, which is tolerable in an anonymity set of 50 users.

[00122] A prototype using an embodiment of the anonymity protocol was implemented in the Go programming language from Google, Inc. The performance of the prototype was evaluated on the Deterlab infrastructure (Deterlab: Cyber-defense technology experHmental research laboratory, 2016. URL www.isi. deterlab.net).

[00123] FIG. 13A shows the latency of the system using an embodiment of the anonymity protocol, i.e., the time needed for an anonymized packet to be sent by the client, decoded by the relay, and sent back to this same client. In this experiment, one random user is responsible for measuring those "pings", while others only participate in the protocol without sending data (i.e., the number of active user is 1, anonymous among all users). The latency increase linearly, from 40ms for 30 users (e.g., a small company) to 120ms for 100 users, and scales well with the number of clients.

[00124] A major component of the latency is the buffering of messages by the clients; having only one slot per schedule, clients must wait this slot before transmitting data. This waiting time is depicted by the lower curve in FIG 13(a). To reduce the time spent waiting on the slot, the scheduling mechanism was altered to allows slots to be closed. A periodic reservation map allowed clients to anonymously specify if they want to send data; if not, the round is defined as closed. The relay skips the closed rounds, which allows for shorter, more frequent schedules. For instance, if only one user wants to transmit, the relay alternates between reservation map and 1-slot schedules.

[00125] This reservation mechanism improves the situation where many users are idle. It induces additional delay in some cases, as the client needs to wait for the next reservation to open his slot, and wait again for his slot. Other scheduling mechanisms (e.g., embedded in each packet, or removing the schedule and allowing collisions) would yield different tradeoffs between latency and number of users; finding the best way to divide the anonymous channel depends on many factors, and is out-of-scope of this project.

[00126] Real traces were also replayed through the system with an embodiment of the anonymity protocol. To validate the VoIP scenario, a dataset containing Skype traces from

CRAWDAD was used. One client replayed those traces, while others were not transmitting data, and the relay recorded the time-difference between the received packets and the original traces (i.e., the latency does not include the communication to the Skype servers, but only the added latency by anonymity protocol). The evaluation results are displayed in Figure 13(b); in which it can be seen that the median value increases linearly from 25 ms for 20 clients, to

75ms for 100 clients, below the one-way 150ms recommended threshold (International

Telecommunication Union. Itu-t g.114 - amendment 2: New appendix iii delay variation on unshared access lines, 2009. URL www.itu.int/ rec/T-REC-G.114-200911-I!Amd2/en) and below the 250ms threshold where callers start noticing delay (VoIP Info. Voip qos requirements, 2017. URL www.voip-info.org/wiki/view/QoS). [00127] FIG 13(a) shows slightly higher latencies (upper line in graph) than Figure 13(b), because in the first scenario, the client has to reserve a slot and wait for it for each packet. In the Skype dataset, once a slot has been reserved for one packet, the anonymity protocol packs as many buffered packets as possible, using more efficiently the upstream payload.

[00128] FIGS. 14A-B shows the benefits of using UDP Broadcast instead of unicasting to provide receiver anonymity. It can be seen that time spent sending data increasing linearly with the number of clients in FIG. 14A, while remaining negligible in FIG. 14B. Shorter round durations translate directly into lower latency for the clients. This experiment depicts how WLANs, which achieve broadcast naturally, compose well with anonymous communication systems providing receiver anonymity.

[00129] FIG. 15 is a graph that illustrates how pipelining can be used to reduce latency in systems where nodes wait on each other (e.g., DC-nets). For embodiments of the anonymity protocol, increasing the pipelining factor allows for decreases in the experienced latency by 2.25 at no other cost.

[00130] Exemplary flowcharts are provided herein for illustrative purposes and are non- limiting examples of methods. One of ordinary skill in the art will recognize that exemplary methods may include more or fewer steps than those illustrated in the exemplary flowcharts, and that the steps in the exemplary flowcharts may be performed in a different order than the order shown in the illustrative flowcharts.

[00131] The foregoing description of the specific embodiments of the subject matter disclosed herein has been presented for purposes of illustration and description and is not intended to limit the scope of the subject matter set forth herein. It is fully contemplated that other various embodiments, modifications and applications will become apparent to those of ordinary skill in the art from the foregoing description and accompanying drawings. Thus, such other embodiments, modifications, and applications are intended to fall within the scope of the following appended claims. Further, those of ordinary skill in the art will appreciate that the embodiments, modifications, and applications that have been described herein are in the context of particular environment, and the subject matter set forth herein is not limited thereto, but can be beneficially applied in any number of other manners, environments and purposes. Accordingly, the claims set forth below should be construed in view of the full breadth and spirit of the novel features and techniques as disclosed herein.