SQRT: A Secure Querying Scheme of Routing Table Based on Oblivious Transfer

Yue Zhao, Bo Tian, Ning Hu, Qi Zhao, Yiru Niu, Leyu Lin, Yarang YangSymmetry 2022 · DOI

TL;DR

This paper introduces SQRT, a novel secure querying scheme for routing tables in anonymous networks that leverages oblivious transfer. SQRT aims to protect the privacy of both users and directory servers by ensuring that users only receive the routing information they need without revealing their specific queries, and directory servers don't learn which specific nodes users select.

What Problem Does This Paper Address?

Existing anonymous networks like Tor and I2P face a significant security challenge: the leakage of privacy information about routing nodes. When a user equipment (UE) queries a directory server (DS) for routing information, both parties can inadvertently reveal more than they intend. For instance, the DS might learn the UE's specific routing preferences, and the UE might gain knowledge of routing nodes it didn't request. This asymmetry in information and the potential for privacy breaches are critical issues that SQRT seeks to resolve.

Methods

The core of SQRT is its reliance on oblivious transfer (OT), a cryptographic primitive that allows a receiver to obtain one of several pieces of information from a sender, without the sender knowing which piece was chosen, and without the receiver learning about the other pieces.

Specifically, SQRT employs an Nk+Δ-out-of-Nk oblivious transfer model. Here's a breakdown of the key steps:

  1. UE Query Generation: The UE generates a routing node query request, represented as an m-dimensional vector q. This vector contains constraints like bandwidth requirements or online time. The UE then "blinds" this query using a matrix Bk and generates public keys pkt for the oblivious transfer.
  2. DS Data Storage & Update: The DS maintains a routing table database (DB) containing the state information (dj) of n routing nodes. This information is dynamically updated via network heartbeat mechanisms.
  3. DS Query Calculation: Upon receiving the blinded query from the UE, the DS calculates a distance metric (dist) between the UE's query constraints and the routing node information.
  4. Oblivious Transfer Execution: The DS then uses an Nk+Δ-out-of-Nk oblivious transfer protocol. The DS has access to n potential routing node messages (M1 to Mn), and the UE has a selection input c. Through this protocol, the UE can select Nk routing node messages without the DS knowing which ones were selected, and the DS can provide these Nk messages without knowing the UE's specific selection criteria.
  5. UE Receives Information: The UE, using its private key, decrypts the oblivious transfer output and obtains the address information of Nk routing nodes. Crucially, the UE does not learn about the other Δ routing nodes that were also part of the oblivious transfer.

The paper also details a secure querying algorithm (Algorithm 1) that the DS uses to identify the Nk + Δ routing nodes that best match the UE's query from the total n available nodes.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Oblivious Transfer as a Privacy Enabler: The paper effectively demonstrates how oblivious transfer can be a powerful tool for achieving privacy in network querying scenarios, particularly where information asymmetry is a concern.
  • Bilateral Privacy: SQRT's strength lies in providing privacy for both the user equipment and the directory server. The UE doesn't reveal its exact query preferences, and the DS doesn't learn which specific nodes the UE ultimately selects.
  • Mitigating Information Leakage: By carefully designing the query and utilizing OT, SQRT significantly reduces the leakage of routing node information that plagues existing schemes.
  • Practical Performance: The experimental results suggest that SQRT offers a good balance between security and performance, making it a viable option for real-world anonymous networks.

Key Results

The paper presents experimental results comparing SQRT with existing schemes (The Onion Routing, The Galicia Routing, BLAZE, TRIDENT, CDT, DID) across several metrics:

  • Running Time: For semi-honest models, SQRT reduced running time by 16.9% and 34.5% compared to The Onion Routing and The Galicia Routing, respectively.
  • Communication Traffic: SQRT reduced communication traffic by 19.6% and 46.5% compared to The Onion Routing and The Galicia Routing, respectively.
  • Degree of Anonymity: SQRT demonstrates a significantly lower degree of anonymity (meaning better privacy protection) compared to other schemes, as illustrated in Figure 7. This is attributed to its ability to effectively protect the privacy of both parties.
  • Scalability: Figures 5 and 6 show that while running time and traffic increase with larger Nk (number of selected nodes) and Δ (redundancy in OT), the overall performance remains within acceptable limits (e.g., running time generally under 1 second).

Limitations and Future Work

The authors acknowledge a key limitation:

  • Theoretical Security Analysis: The security analysis is primarily theoretical, based on the assumption of a semi-honest model and the security of the underlying oblivious transfer protocol. They state that there was "no strict mathematical basis to support this security analysis" and that a "provable security method for a more reliable security analysis" could be an area for future research.

Future work could focus on:

  • Developing more rigorous mathematical proofs for the security of the SQRT scheme.
  • Exploring the application of SQRT in more complex network environments or against more sophisticated attack models.
  • Investigating optimizations for the oblivious transfer protocol itself to further enhance performance.

Summary updated

Abstract

The user equipment and directory server stay in the state of asymmetric information in anonymous networks, so that it is hard to coordinate information leakage prevention and information sharing when we explore the routing addressing technology. The severe security risk faced by existing anonymous networks, such as Tor and I2P, is the leakage of privacy information of routing nodes. This paper tries to resolve this problem and proposes a novel secure querying scheme of the routing table (SQRT) based on oblivious transfer, which can effectively ensure that both user equipment and directory server faithfully follow the routing querying protocol and protect the privacy information of both parties to the greatest extent. The SQRT scheme can realize that the directory server cannot only send the required routing nodes to the user equipment, but can also ensure that the directory server cannot know the exact routing nodes received by the user equipment and protect the information of other routing nodes in the directory server from disclosure. Security analysis shows that in the scenario where the directory server and user equipment are semi-honest, respectively, the SQRT scheme can ensure the privacy of both directory server and user equipment. The experimental simulation results show that compared with existing schemes, the SQRT scheme has obvious performance advantages in terms of the degree of anonymity, protocol running time, and communication traffic.
BibTeX
@inproceedings{zhao2022sqrt,
  author = {Yue Zhao and Bo Tian and Ning Hu and Qi Zhao and Yiru Niu and Leyu Lin and Yarang Yang},
  title = {{SQRT: A Secure Querying Scheme of Routing Table Based on Oblivious Transfer}},
  booktitle = {Symmetry},
  year = {2022},
  doi = {10.3390/sym14061245},
}
Figure