Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Symmetric Private Information Retrieval from MDS Coded Distributed Storage With Non-Colluding and Colluding Servers
KTH, School of Electrical Engineering and Computer Science (EECS), Information Science and Engineering.ORCID iD: 0000-0001-9471-1409
KTH, School of Electrical Engineering and Computer Science (EECS), Information Science and Engineering.ORCID iD: 0000-0002-7926-5081
2019 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 65, no 8, p. 5160-5175Article in journal (Refereed) Published
Abstract [en]

A user wants to retrieve a file from a database without revealing the identity of the file retrieved to the operator of the database (server), which is known as the problem of private information retrieval (PIR). If it is further required that the user obtains no information about the other files in the database, the concept of symmetric PIR (SPIR) is introduced to guarantee privacy for both parties. For SPIR, the server(s) need to access some randomness independent of the database, to protect the content of undesired files from the user. The information-theoretic capacity of SPIR is defined as the maximum number of information bits of the desired file retrieved per downloaded bit. In this paper, the problem of SPIR is studied for a distributed storage system with N servers (nodes), where all data (including the files and the randomness) are stored in a distributed way. Specifically, the files are stored by an (N, K-C)-MDS storage code. The randomness is distributedly stored such that any K-C servers store independent randomness information. We consider two scenarios regarding to the ability of the storage nodes to cooperate. In the first scenario considered, the storage nodes do not communicate or collude. It is shown that the SPIR capacity for MDS-coded storage (hence called MDS-SPIR) is 1 - K-C/N, when the amount of the total randomness of distributed nodes (unavailable at the user) is at least K-C/N-K-C times the file size. Otherwise, the MDS-SPIR capacity equals zero. The second scenario considered is the T-colluding SPIR problem (hence called TSPIR). Specifically, any T out of N servers may collude, that is, they may communicate their interactions with the user to guess the identity of the requested file. In the special case with K-C = 1, i.e., the database is replicated at each node, the capacity of TSPIR is shown to be 1 - T/N, with the ratio of the total randomness size relative to the file size be at least T/N-T. For TSPIR with MDS-coded storage (called MDS-TSPIR for short), when restricted to schemes with additive randomness where the servers add the randomness to the answers regardless of the queries received, the capacity is proved to equal 1 - K-C+T-1/N, with total randomness at least K-C+T-1/N-K-C-T+1 times the file size. The MDS-TSPIR capacity for general schemes remains an open problem.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2019. Vol. 65, no 8, p. 5160-5175
Keywords [en]
Private information retrieval, capacity, colluding servers, distributed storage, MDS codes
National Category
Communication Systems
Identifiers
URN: urn:nbn:se:kth:diva-255728DOI: 10.1109/TIT.2019.2903206ISI: 000476740600035Scopus ID: 2-s2.0-85069527144OAI: oai:DiVA.org:kth-255728DiVA, id: diva2:1342786
Note

QC 20190814

Available from: 2019-08-14 Created: 2019-08-14 Last updated: 2019-08-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Wang, QiwenSkoglund, Mikael

Search in DiVA

By author/editor
Wang, QiwenSkoglund, Mikael
By organisation
Information Science and Engineering
In the same journal
IEEE Transactions on Information Theory
Communication Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 9 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf