Private Information Retrieval Over Random Linear Networks

Razane Tajeddine, Antonia Wachter-Zeh, Camilla Hollanti

Abstract

In this paper, the problem of providing privacy to users requesting data over a network from a distributed storage system (DSS) is considered. The DSS, which is considered as the multi-terminal destination of the network from the user's perspective, is encoded by a maximum rank distance (MRD) code to store the data on these multiple servers. A private information retrieval (PIR) scheme ensures that a user can request a file without revealing any information on which file is being requested to any of the servers. In this paper, a novel PIR scheme is proposed, allowing the user to recover a file from a storage system with low communication cost, while allowing some servers in the system to collude in the quest of revealing the identity of the requested file. The network is modeled as a random linear network, i.e., all nodes of the network forward random (unknown) linear combinations of incoming packets. Both error-free and erroneous random linear networks are considered.

Introduction

Private Information Retrieval (PIR) is a fundamental cryptographic primitive that allows a user to retrieve a specific file from a set of distributed servers without revealing the identity of the requested file to any individual server. While traditional PIR research assumes direct, point-to-point links between the user and the servers, modern network architectures often employ Random Linear Network Coding (RLNC) to optimize throughput and reliability.

In an RLNC environment, intermediate nodes forward random linear combinations of incoming packets, effectively "scrambling" the communication in a way that is unknown to both the user and the servers. This paper introduces the first PIR scheme specifically designed to operate over such random linear networks, bridging the gap between theoretical PIR and practical, coded network architectures.

The Network Model

The system consists of a user, $l$ storage servers, and a set of intermediate nodes. The data is stored across the servers using Maximum Rank Distance (MRD) codes. The network between the user and the servers is modeled as a random linear network where intermediate nodes perform unknown linear operations on the packets.

Figure 1: System model of a distributed storage system (DSS) over a random linear network.

The challenge in this setting is twofold: ensuring privacy when queries are mixed by the network, and ensuring decodability when the server responses undergo unknown linear transformations before reaching the user.

The Proposed PIR Scheme

The proposed scheme leverages the properties of MRD codes, specifically Gabidulin codes, which are inherently suited for rank-metric environments like RLNC. Since RLNC preserves the subspace spanned by the packets, rank-metric codes allow for efficient recovery despite unknown network transformations.

A key innovation is the "lifting" technique. To handle the unknown network transformation $A$, the user appends an identity matrix to the query matrix. Upon receiving the response, the user can extract the transformation matrix $A$ and use it to decode the data. Furthermore, the scheme utilizes a "star product" of codes to ensure that the product of the query and the stored data remains a codeword in a decodable Gabidulin code.

Figure 3: Matrix encoding and transformation process for the PIR scheme.

For networks prone to erasures, the authors propose a recursive recovery strategy. If a query round fails to provide sufficient rank for decoding due to network deficiency, the user can subdivide the remaining file parts and initiate subsequent query rounds to complete the retrieval.

Key Insights and Results

The research yields several critical insights into the synergy between rank-metric codes and network coding:

  • Rank-Metric Synergy: MRD codes are the "native language" of RLNC because they operate on the rank of matrices, which is invariant under linear network transformations. This makes them significantly more efficient than standard Reed-Solomon codes in this context.
  • Robustness to Collusion and Errors: The scheme is robust against $t$ colluding servers and can correct network errors ($\epsilon$) and erasures ($\tau$) provided $2\epsilon + \tau \leq d - 1$, where $d$ is the code's minimum distance.
  • PIR Rate: In error-free networks, the scheme achieves a PIR rate of $R_{PIR} = 1 - \frac{k + t\rho - 1}{n}$. This rate matches conjectured asymptotic capacities as the field size $q$ increases.

Conclusion and Future Work

This work provides a robust framework for private data retrieval in modern, coded networks. While the scheme is highly effective for "honest-but-curious" servers and dummy relays, future research could explore scenarios involving "curious" intermediate nodes that might collude with storage servers. Additionally, optimizing the computational complexity of Gabidulin decoding for high-speed hardware and exploring performance in small-field regimes remain important open challenges for practical deployment.

Summary updated

Abstract

In this paper, the problem of providing privacy to users requesting data over a network from a distributed storage system (DSS) is considered. The DSS, which is considered as the multi-terminal destination of the network from the user's perspective, is encoded by a maximum rank distance (MRD) code to store the data on these multiple servers. A private information retrieval (PIR) scheme ensures that a user can request a file without revealing any information on which file is being requested to any of the servers. In this paper, a novel PIR scheme is proposed, allowing the user to recover a file from a storage system with low communication cost, while allowing some servers in the system to collude in the quest of revealing the identity of the requested file. The network is modeled as a random linear network, i.e., all nodes of the network forward random (unknown) linear combinations of incoming packets. Both error-free and erroneous random linear networks are considered.
BibTeX
@article{tajeddine2020private,
  author = {Razane Tajeddine and Antonia Wachter-Zeh and Camilla Hollanti},
  title = {{Private Information Retrieval Over Random Linear Networks}},
  journal = {IEEE Trans. Inf. Forensics Secur.},
  year = {2020},
  url = {https://openreview.net/forum?id=o_zbmWvyc9d},
}
Figure