Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Symmetric Private Information Retrieval from MDS Coded Distributed Storage With Non-Colluding and Colluding Servers
KTH, Skolan för elektroteknik och datavetenskap (EECS), Teknisk informationsvetenskap.ORCID-id: 0000-0001-9471-1409
KTH, Skolan för elektroteknik och datavetenskap (EECS), Teknisk informationsvetenskap.ORCID-id: 0000-0002-7926-5081
2019 (Engelska)Ingår i: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 65, nr 8, s. 5160-5175Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
Institute of Electrical and Electronics Engineers (IEEE), 2019. Vol. 65, nr 8, s. 5160-5175
Nyckelord [en]
Private information retrieval, capacity, colluding servers, distributed storage, MDS codes
Nationell ämneskategori
Kommunikationssystem
Identifikatorer
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
Anmärkning

QC 20190814

Tillgänglig från: 2019-08-14 Skapad: 2019-08-14 Senast uppdaterad: 2019-08-14Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Personposter BETA

Wang, QiwenSkoglund, Mikael

Sök vidare i DiVA

Av författaren/redaktören
Wang, QiwenSkoglund, Mikael
Av organisationen
Teknisk informationsvetenskap
I samma tidskrift
IEEE Transactions on Information Theory
Kommunikationssystem

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 9 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf