Private Information Retrieval Schemes With Product-Matrix MBR Codes

Julien Lavauzelle; Razane Tajeddine; Ragnar Freij-Hollanti; Camilla Hollanti

doi:10.1109/TIFS.2020.3003572

Private Information Retrieval Schemes With Product-Matrix MBR Codes

Julien Lavauzelle, Razane Tajeddine^*, Ragnar Freij-Hollanti, Camilla Hollanti

^*Corresponding author for this work

Research output: Contribution to journal › Article › Scientific › peer-review

9 Citations (Scopus)

Abstract

A private information retrieval (PIR) scheme allows a user to retrieve a file from a database without revealing any information on the file being requested. As of now, PIR schemes have been proposed for several kinds of storage systems, including replicated and MDS-coded systems. However, the problem of constructing PIR schemes on regenerating codes has been sparsely considered. A regenerating code is a storage code whose codewords are distributed among nodes, enabling efficient storage of files, as well as low-bandwidth retrieval of files and repair of nodes. Minimum-bandwidth regenerating (MBR) codes define a family of regenerating codes allowing a node repair with optimal bandwidth. Rashmi, Shah, and Kumar obtained a large family of MBR codes using the product-matrix (PM) construction. In this work, a new PIR scheme over PM-MBR codes is designed. The inherent redundancy of the PM structure is used to reduce the download communication complexity of the scheme. A lower bound on the PIR capacity of MBR-coded PIR schemes is derived, showing an interesting storage space vs. PIR rate trade-off compared to existing PIR schemes with the same reconstruction capability. The present scheme also outperforms a recent PM-MBR PIR construction of Dorkson and Ng.

Original language	English
Article number	9122048
Pages (from-to)	441-450
Number of pages	10
Journal	IEEE Transactions on Information Forensics and Security
Volume	16
DOIs	https://doi.org/10.1109/TIFS.2020.3003572
Publication status	Published - 2021
MoE publication type	A1 Journal article-refereed

Funding

The work of Julien Lavauzelle was supported in part by French "Manta" under Grant ANR-15-CE39-0013-01. The work of Razane Tajeddine and Camilla Hollanti were supported in part by the Academy of Finland, under Grant 276031, Grant 282938, and Grant 303819, and in part by the Technical University of Munich - Institute for Advanced Study, funded by the German Excellence Initiative and the EU 7th Framework Programme through the Hans Fischer Fellowship under Agreement 291763. The work of Ragnar Freij-Hollanti was supported by the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG) under Grant WA3907/1-1.

Keywords

Privacy
information retrieval
peer-to-peer computing
distributed databases
DISTRIBUTED STORAGE
CAPACITY

Access to Document

10.1109/TIFS.2020.3003572

https://arxiv.org/abs/1811.02898

Cite this

@article{31a25fc924634a8c9b9ad55d0d2a1ee6,

title = "Private Information Retrieval Schemes With Product-Matrix MBR Codes",

abstract = "A private information retrieval (PIR) scheme allows a user to retrieve a file from a database without revealing any information on the file being requested. As of now, PIR schemes have been proposed for several kinds of storage systems, including replicated and MDS-coded systems. However, the problem of constructing PIR schemes on regenerating codes has been sparsely considered. A regenerating code is a storage code whose codewords are distributed among nodes, enabling efficient storage of files, as well as low-bandwidth retrieval of files and repair of nodes. Minimum-bandwidth regenerating (MBR) codes define a family of regenerating codes allowing a node repair with optimal bandwidth. Rashmi, Shah, and Kumar obtained a large family of MBR codes using the product-matrix (PM) construction. In this work, a new PIR scheme over PM-MBR codes is designed. The inherent redundancy of the PM structure is used to reduce the download communication complexity of the scheme. A lower bound on the PIR capacity of MBR-coded PIR schemes is derived, showing an interesting storage space vs. PIR rate trade-off compared to existing PIR schemes with the same reconstruction capability. The present scheme also outperforms a recent PM-MBR PIR construction of Dorkson and Ng.",

keywords = "Privacy, information retrieval, peer-to-peer computing, distributed databases, DISTRIBUTED STORAGE, CAPACITY",

author = "Julien Lavauzelle and Razane Tajeddine and Ragnar Freij-Hollanti and Camilla Hollanti",

year = "2021",

doi = "10.1109/TIFS.2020.3003572",

language = "English",

volume = "16",

pages = "441--450",

journal = "IEEE Transactions on Information Forensics and Security",

issn = "1556-6013",

publisher = "IEEE",

}

TY - JOUR

T1 - Private Information Retrieval Schemes With Product-Matrix MBR Codes

AU - Lavauzelle, Julien

AU - Tajeddine, Razane

AU - Freij-Hollanti, Ragnar

AU - Hollanti, Camilla

PY - 2021

Y1 - 2021

N2 - A private information retrieval (PIR) scheme allows a user to retrieve a file from a database without revealing any information on the file being requested. As of now, PIR schemes have been proposed for several kinds of storage systems, including replicated and MDS-coded systems. However, the problem of constructing PIR schemes on regenerating codes has been sparsely considered. A regenerating code is a storage code whose codewords are distributed among nodes, enabling efficient storage of files, as well as low-bandwidth retrieval of files and repair of nodes. Minimum-bandwidth regenerating (MBR) codes define a family of regenerating codes allowing a node repair with optimal bandwidth. Rashmi, Shah, and Kumar obtained a large family of MBR codes using the product-matrix (PM) construction. In this work, a new PIR scheme over PM-MBR codes is designed. The inherent redundancy of the PM structure is used to reduce the download communication complexity of the scheme. A lower bound on the PIR capacity of MBR-coded PIR schemes is derived, showing an interesting storage space vs. PIR rate trade-off compared to existing PIR schemes with the same reconstruction capability. The present scheme also outperforms a recent PM-MBR PIR construction of Dorkson and Ng.

AB - A private information retrieval (PIR) scheme allows a user to retrieve a file from a database without revealing any information on the file being requested. As of now, PIR schemes have been proposed for several kinds of storage systems, including replicated and MDS-coded systems. However, the problem of constructing PIR schemes on regenerating codes has been sparsely considered. A regenerating code is a storage code whose codewords are distributed among nodes, enabling efficient storage of files, as well as low-bandwidth retrieval of files and repair of nodes. Minimum-bandwidth regenerating (MBR) codes define a family of regenerating codes allowing a node repair with optimal bandwidth. Rashmi, Shah, and Kumar obtained a large family of MBR codes using the product-matrix (PM) construction. In this work, a new PIR scheme over PM-MBR codes is designed. The inherent redundancy of the PM structure is used to reduce the download communication complexity of the scheme. A lower bound on the PIR capacity of MBR-coded PIR schemes is derived, showing an interesting storage space vs. PIR rate trade-off compared to existing PIR schemes with the same reconstruction capability. The present scheme also outperforms a recent PM-MBR PIR construction of Dorkson and Ng.

KW - Privacy

KW - information retrieval

KW - peer-to-peer computing

KW - distributed databases

KW - DISTRIBUTED STORAGE

KW - CAPACITY

UR - https://www.scopus.com/pages/publications/85091160323

U2 - 10.1109/TIFS.2020.3003572

DO - 10.1109/TIFS.2020.3003572

M3 - Article

SN - 1556-6013

VL - 16

SP - 441

EP - 450

JO - IEEE Transactions on Information Forensics and Security

JF - IEEE Transactions on Information Forensics and Security

M1 - 9122048

ER -

Private Information Retrieval Schemes With Product-Matrix MBR Codes

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this