A Low-Complexity Scheme for Multi-Message Private Information Retrieval
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929720983027712 |
|---|---|
| author | Wang, Ningze Heidarzadeh, Anoosheh Sprintson, Alex |
| author_facet | Wang, Ningze Heidarzadeh, Anoosheh Sprintson, Alex |
| contents | Private Information Retrieval (PIR) is a fundamental problem in the broader fields of security and privacy. In recent years, the problem has garnered significant attention from the research community, leading to achievability schemes and converse results for many important PIR settings.
This paper focuses on the Multi-message Private Information Retrieval (MPIR) setting, where a user aims to retrieve \(D\) messages from a database of \(K\) messages, with identical copies of the database available on \(N\) remote servers. The user's goal is to maximize the download rate while keeping the identities of the retrieved messages private. Existing approaches to the MPIR problem primarily focus on either scalar-linear solutions or vector-linear solutions, the latter requiring a high degree of subpacketization. Furthermore, prior scalar-linear solutions are restricted to the special case of \(N = D+1\). This limitation hinders the practical adoption of these schemes, as real-world applications demand simple, easily implementable solutions that support a broad range of scenarios.
In this work, we present a solution for the MPIR problem, which applies to a broader range of system parameters and requires a limited degree of subpacketization. In particular, the proposed scheme applies to all values of \(N=DL+1\) for any integer \(L\geq 1\), and requires a degree of subpacketization \(L\). Our scheme achieves capacity when \(D\) divides \(K\), and in all other cases, its performance matches or comes within a small additive margin of the best-known scheme that requires a high degree of subpacketization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_14054 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Low-Complexity Scheme for Multi-Message Private Information Retrieval Wang, Ningze Heidarzadeh, Anoosheh Sprintson, Alex Information Theory Private Information Retrieval (PIR) is a fundamental problem in the broader fields of security and privacy. In recent years, the problem has garnered significant attention from the research community, leading to achievability schemes and converse results for many important PIR settings. This paper focuses on the Multi-message Private Information Retrieval (MPIR) setting, where a user aims to retrieve \(D\) messages from a database of \(K\) messages, with identical copies of the database available on \(N\) remote servers. The user's goal is to maximize the download rate while keeping the identities of the retrieved messages private. Existing approaches to the MPIR problem primarily focus on either scalar-linear solutions or vector-linear solutions, the latter requiring a high degree of subpacketization. Furthermore, prior scalar-linear solutions are restricted to the special case of \(N = D+1\). This limitation hinders the practical adoption of these schemes, as real-world applications demand simple, easily implementable solutions that support a broad range of scenarios. In this work, we present a solution for the MPIR problem, which applies to a broader range of system parameters and requires a limited degree of subpacketization. In particular, the proposed scheme applies to all values of \(N=DL+1\) for any integer \(L\geq 1\), and requires a degree of subpacketization \(L\). Our scheme achieves capacity when \(D\) divides \(K\), and in all other cases, its performance matches or comes within a small additive margin of the best-known scheme that requires a high degree of subpacketization. |
| title | A Low-Complexity Scheme for Multi-Message Private Information Retrieval |
| topic | Information Theory |
| url | https://arxiv.org/abs/2502.14054 |