Iris: Dynamic Privacy Preserving Search in Authenticated Chord Peer-to-Peer Networks

Iris: Dynamic Privacy Preserving Search in Authenticated Chord Peer-to-Peer Networks

Speakers: Angeliki Aktypi (University of Oxford)

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=W6eE7rouoWQ

Overview

In the realm of decentralized systems, Chord peer-to-peer (P2P) networks have long been lauded for their efficiency and simplicity in managing distributed key-value stores. They form the backbone of various real-world applications, from decentralized search engines like Sik to blockchain protocols such as NKN, and even serve as a lookup service for Tor onion services. However, a fundamental challenge persists: the inherent transparency of search queries. When a node initiates a search for a specific key, the standard Chord routing protocol necessitates revealing the target key at every hop along the path to the responsible node. This critical vulnerability allows malicious actors, by merely participating in the network and observing traffic, to profile users, infer popular data, or gain insights into network usage patterns.

Angeliki Aktypi from the University of Oxford, in a joint work with Professor Casper Assam, presented "Iris," an innovative algorithm designed to address this privacy deficit. Iris enables nodes within authenticated Chord networks to perform private queries, crucially focusing on obscuring what is being searched for, rather than the identity of who is searching. This distinction is vital, as it permits nodes to maintain long-term identities within the network, fostering stability and accountability, while still preserving the confidentiality of their search intentions.

The significance of Iris lies in its ability to retrofit privacy into an established and widely adopted network architecture without demanding fundamental changes to the underlying Chord protocol or its participating nodes. By introducing a novel privacy metric and allowing requesters to dynamically tune their privacy-efficiency trade-off, Iris offers a practical and theoretically sound solution to a persistent privacy challenge in decentralized systems, enhancing the security posture of applications reliant on Chord for key-value lookups.

Background

▶ Watch: Introduction to Iris: Privacy in Chord networks (0:00)

Chord networks operate on a principle of distributed responsibility for data keys. In a Chord ring, both nodes and data keys are assigned addresses within a common, circular address space. The fundamental rule is that a node is responsible for storing the value associated with a key if its address is the closest successor to that key's address in the ring. This distributed ownership model is efficient and scalable, making Chord a popular choice for decentralized services. Nodes maintain local routing tables (often called "finger tables") which contain a limited view of the network, typically pointers to other nodes at exponentially increasing distances around the ring.

When a node, say Alice, wants to retrieve a value associated with a specific key, it initiates a query. Since Alice doesn't have a global view of the entire network, she consults her routing table. She then forwards the query to the node in her routing table that is closest to the target key's address. This intermediate node, upon receiving the query, performs the same lookup process, forwarding the query to a node in its routing table that is even closer to the target key. This iterative process continues until the query reaches the node directly responsible for the key, which then retrieves and returns the associated value.

The core privacy problem stems directly from this iterative routing mechanism. As exemplified in the talk, if Alice (address 8) searches for key 62, she might first query node 42, then node 61, and so on, until the node responsible for 62 is reached. At every single step of this process, the queried node is explicitly told that the request is for key 62. An attacker, operating even a few nodes within the network, can intercept these queries. By observing the sequence of requests and the target keys, an attacker can construct detailed profiles of users' interests, identify popular data items being accessed, or even infer sensitive information based on the types of keys being queried. This form of traffic analysis undermines the privacy expectations users might have in a decentralized environment.

The design of Iris operates under specific assumptions regarding the network and the adversary. It presumes that participating nodes possess long-term identities, which is often desirable for network stability and accountability. Furthermore, it assumes that communication between nodes occurs over secure communication channels, guaranteeing both integrity (messages are not tampered with) and confidentiality (message content is not exposed to eavesdroppers). The adversary model is robust: the attacker is assumed to be an active participant in the network, controlling a subset of the nodes, and possessing full knowledge of all the protocols being executed. This strong adversary model underscores the challenge Iris aims to overcome, as merely encrypting communications is insufficient if the target key itself is revealed in plaintext at each hop.

Key Findings

▶ Watch: Introducing Iris: The privacy-preserving search algorithm (4:00)

Iris introduces a paradigm shift in how privacy is approached within Chord networks, delivering several significant findings:

Firstly, the core contribution is the Iris algorithm itself, which successfully enables privacy-preserving searches in Chord P2P networks. Unlike conventional methods that might obscure the requester's identity, Iris specifically targets the content of the query, ensuring that what is being searched for remains secret from intermediate nodes. This allows for long-term node identities, promoting network stability without sacrificing query confidentiality.

Secondly, the talk highlights the inadequacy of existing privacy metrics, such as k-anonymity, for the specific challenges of iterative queries in a P2P network with potential collusion. To address this, Iris introduces a novel privacy metric called alpha-delta privacy. This metric is tailored to capture the iterative nature of Chord routing and the accumulating knowledge of colluding adversaries, providing a more accurate and dynamic assessment of privacy guarantees at each step of a query. It defines two ranges—a prior range based on initial knowledge and a posterior range accumulating knowledge from the ongoing request—and uses their ratio to quantify privacy.

Thirdly, the research provides theoretical proofs demonstrating that Iris is both correct (meaning it will always successfully locate the target key) and private (adhering to the alpha-delta privacy guarantees). These theoretical underpinnings are crucial for establishing the reliability and security of the algorithm.

Finally, through an evaluation performed in MATLAB, the researchers gained critical insights into the practical behavior of Iris. The evaluation revealed that the alpha parameter has a dominant effect on the algorithm's convergence rate: higher alpha values (indicating greater privacy) necessitate more iterations to reach the target key. Conversely, the delta parameter was found to have less influence on convergence. Importantly, the evaluation showed that the actual privacy achieved by Iris often surpasses the minimum alpha threshold, particularly in scenarios with varying fractions of colluding adversaries, indicating robust performance. A key practical finding is Iris's compatibility with vanilla Chord, meaning it requires no modifications to existing Chord network protocols or the nodes themselves; only the requester needs to implement the Iris algorithm. This significantly lowers the barrier to adoption for enhancing privacy in deployed Chord-based systems.

Technical Deep Dive

▶ Watch: Iris's privacy guarantees and new metric (6:00)

The technical ingenuity of Iris lies in its ability to subtly alter the Chord routing mechanism to obscure the target key without breaking the underlying distributed lookup functionality.

At its core, Chord assigns both nodes and keys to a common m-bit identifier space, typically represented as a circular ring from 0 to 2^m - 1. Each node n maintains a finger table with m entries. The i-th entry in node n's finger table stores the identifier of the first node s that succeeds n + 2^(i-1) (modulo 2^m). When a node n wants to find the successor of a key k, it checks if k falls between n and its immediate successor. If not, it forwards the query to the node in its finger table that most immediately precedes k. This iterative process, where each hop gets "closer" to the target key, eventually leads to the node responsible for k.

Iris modifies this process by introducing two key privacy parameters, alpha (α) and delta (δ), which the initiator of the request defines:

1. Delta (δ) – Controlling "Who to Ask First": In a standard Chord query, the initiator immediately asks the node in its routing table that is closest to the actual target key. Iris introduces delta to create an initial layer of obfuscation. Instead of directly querying the node closest to the target, the initiator first "steps back" delta addresses in the address space from its current position (or from a calculated "starting point"). It then selects the first node among those it knows (from its routing table) that falls within this delta-adjusted range. For example, if Alice is searching for key 62, a standard Chord query might immediately direct her to node 42. With Iris, she might use delta to instead query node 30, which is further away from 62 but within a delta-defined initial range, thereby not immediately revealing her strong interest in 62. This initial indirection broadens the set of potential first-hop nodes, making it harder for an attacker to infer the target based on the initial query.

1. Alpha (α) – Controlling "What to Ask For": This is the more intricate component, designed to prevent the direct revelation of the target key at any intermediate hop. Instead of asking for the true target T, the initiator calculates a pseudotarget P based on alpha, a randomly selected point, and the address of the node currently being queried. The algorithm ensures that P is always "in between" the current querying node and the true target T. The crucial part is that P is dynamically calculated at each step of the iterative process. For instance, if Alice is searching for 62, she might generate a random point 58, and based on her alpha parameter, calculate a pseudotarget of 47 to query an intermediate node. The intermediate node then processes this pseudotarget 47 as if it were the actual key. The Iris algorithm guarantees that by iteratively querying these pseudotargets, the process will eventually converge on the true target 62. This creates a "fuzzy" path towards the target, where no single intermediate node knows the exact key being sought, only a progressively refined pseudotarget that leads closer to it.

The privacy guarantees provided by Iris are quantified by the alpha-delta privacy metric. The motivation for this new metric stems from the limitations of traditional metrics like k-anonymity in this context. K-anonymity typically defines a set of k indistinguishable items, but in an iterative search, the set of possible targets shrinks with each hop, especially if attackers collude. Alpha-delta privacy addresses this by considering the cumulative knowledge of colluding attackers across multiple query steps.

The metric defines two critical ranges:

• The prior range is the set of possible target keys an attacker could infer before the current query, based on the delta parameter and any knowledge gained from previous colluding queries.
• The posterior range is the set of possible target keys an attacker could infer after observing the current query, accumulating the new information.

For an algorithm to be considered alpha-delta private, two conditions must be met:

1. The size of the prior range for the first queried node must always be greater than or equal to delta. This ensures a minimum level of initial uncertainty.
2. The ratio between the size of the posterior range and the prior range must always be greater than or equal to alpha for every queried node. This guarantees that each query step reveals only a limited amount of information, ensuring that the attacker's knowledge does not shrink too rapidly. A higher alpha value implies that the ratio of uncertainty before and after a query remains high, thus providing stronger privacy.

The theoretical proofs presented in the paper confirm that Iris correctly converges to the target key while upholding these alpha-delta privacy guarantees. The algorithm’s design ensures that while the queried values are obfuscated, the underlying Chord logic for finding the responsible node remains intact, albeit with an increased number of iterations proportional to the desired privacy level.

Demo / Proof of Concept

▶ Watch: Formal definition of Alpha-Delta privacy metric (7:00)

While the talk did not feature a live demonstration or a typical proof-of-concept exploit in the traditional sense, the speakers presented a comprehensive evaluation framework and its results to validate Iris's effectiveness and privacy guarantees. This evaluation served as the practical demonstration of the algorithm's behavior and performance.

The evaluation was conducted using MATLAB, a powerful numerical computing environment, simulating a Chord network in a steady state. The simulated network consisted of 2^23 possible addresses, with 1,000 participating nodes. For each experiment run, a random address was chosen for the initiator of the request and another random address for the target object, ensuring a diverse set of test cases. The source code for this implementation and the experiments is open source and available on GitHub, allowing other researchers to reproduce and extend the work.

The evaluation specifically focused on understanding the influence of the alpha and delta parameters on two key aspects:

1. Convergence: How quickly Iris successfully locates the target key (measured by the number of iterations required).
2. Privacy Ratios: The distribution of the (posterior range / prior range) ratio, which directly reflects the alpha-delta privacy metric, under various conditions, particularly with different fractions of colluding adversaries.

Results clearly indicated that the alpha parameter has a dominant effect on convergence. As alpha approaches 1 (signifying higher privacy), the number of iterations required for the query to converge to the target key increases. This establishes a direct trade-off: greater privacy comes at the cost of increased latency due to more routing steps. In contrast, the delta parameter was shown to have a less significant influence on convergence, primarily affecting the initial steps of the query.

Regarding privacy, the evaluation demonstrated that Iris consistently maintains the (posterior range / prior range) ratio above the chosen alpha value. In many scenarios, the actual ratio was significantly higher than alpha, indicating that Iris often provides stronger privacy than the minimum guarantee specified by the parameter. Furthermore, there was a correlation observed between the number of higher ratio values obtained and the fraction of colluding adversaries in the system, suggesting robustness even in the presence of more powerful attackers. This robust performance, combined with the theoretical proofs, effectively serves as the practical validation of Iris's design and its privacy-preserving capabilities.

Defensive Implications

▶ Watch: Evaluation results: Alpha's dominant effect on convergence (9:00)

The introduction of Iris carries significant implications for defenders, particularly those operating or designing systems that leverage Chord P2P networks. The primary defensive advantage is the ability to mitigate query profiling and data popularity inference attacks. By obscuring the actual target key at each hop, Iris prevents an adversary from directly observing what a user is searching for, thereby protecting user privacy and preventing the compilation of sensitive interest profiles.

Crucially, Iris's design as an overlay algorithm makes its adoption straightforward. It is compatible with vanilla Chord, meaning it does not require any modifications to the core Chord protocol or the existing network infrastructure. This is a powerful defensive advantage because it allows for incremental deployment. System administrators or developers of Chord-based applications (such as those building decentralized search engines, blockchain protocols, or Tor-like services) do not need to overhaul their entire network. Instead, the privacy enhancement can be implemented solely on the requester's side. This significantly lowers the barrier to entry for integrating stronger privacy protections.

Defenders can empower their users with control over their privacy. The alpha and delta parameters give requesters the ability to tune their desired privacy-efficiency trade-off. A user who prioritizes strong privacy might opt for a higher alpha value, understanding that their queries will take more iterations (and thus potentially longer) to resolve. Conversely, a user with less stringent privacy requirements or in a time-sensitive scenario might choose a lower alpha for faster convergence. This flexibility allows applications to cater to a diverse range of user needs and operational contexts.

For applications like the decentralized lookup service for Tor onion services, integrating Iris could enhance the privacy of users accessing hidden services by preventing passive observation of their service discovery queries. Similarly, in decentralized search engines, it would protect search queries from being logged or profiled by intermediate nodes.

However, it is important to note what Iris does not defend against. The algorithm is specifically designed to protect "what is searched for," not "who is searching." Nodes maintain long-term identities, and Iris does not aim to anonymize the source of the query. Therefore, if an attacker's goal is to identify the source IP address of a query, Iris alone would not be the solution (though it would still protect the content of that query). Defenders should consider Iris as a critical component for query confidentiality, to be integrated alongside other privacy-enhancing technologies if full anonymity is required. In summary, Iris provides a practical, deployable, and configurable mechanism for enhancing query privacy in widely used Chord P2P networks, offering a significant layer of defense against sophisticated traffic analysis attacks.

Key Takeaways

• Privacy for Query Content: Iris is an algorithm that enables privacy-preserving searches in authenticated Chord P2P networks, specifically designed to keep what is searched for secret, rather than the identity of the requester.
• New Privacy Metric: It introduces alpha-delta privacy, a novel metric tailored for iterative query processes and colluding adversaries, providing a more robust measure of privacy guarantees compared to traditional metrics like k-anonymity.
• Tunable Privacy-Efficiency Trade-off: Requesters can dynamically adjust their privacy level and search efficiency using two parameters: alpha (α), which strongly influences the number of iterations and privacy strength, and delta (δ), which provides initial query obfuscation.
• Vanilla Chord Compatibility: A significant advantage of Iris is its compatibility with existing Chord networks. It requires no changes to the underlying Chord protocol or the participating nodes; only the requester needs to implement the Iris algorithm.
• Mitigation of Profiling Attacks: By preventing the direct revelation of target keys at each hop, Iris effectively mitigates attacks where adversaries profile users or infer popular data based on observed search queries.
• Theoretical Soundness and Practical Validation: Iris is theoretically proven to be both correct and private, with MATLAB-based evaluations confirming its behavior and the influence of its parameters on convergence and privacy ratios.

About the Speaker(s)

The primary speaker for this presentation was Angeliki Aktypi, a researcher from the University of Oxford. Her work, including the development of the Iris algorithm, was a joint effort with her supervisor, Professor Casper Assam. The research presented at the NDSS Symposium highlights her contributions to enhancing privacy in decentralized peer-to-peer networks, particularly in the context of Chord-based systems.