Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
On PIR and Symmetric PIR From Colluding Databases With Adversaries and Eavesdroppers
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Information Science and Engineering.ORCID iD: 0000-0001-9471-1409
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, 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 5, p. 3183-3197Article in journal (Refereed) Published
Abstract [en]

We consider the problem of private information retrieval (PIR) and symmetric private information retrieval (SPIR) from replicated databases with colluding servers, in the presence of Byzantine adversaries and eavesdroppers. Specifically, there are K messages replicatively stored at N databases. A user wants to retrieve one message by communicating with the databases, without revealing the identity of the message retrieved. For T-colluding databases, any T out of N databases may communicate their interactions with the user to guess the identity of the requested message. We consider the situation where the communication system can be vulnerable to attachers, namely, there is an adversary in the system that can tap in on or even try to corrupt the communication. The capacity is defined as the maximum number of information bits of the desired message retrieved per downloaded bit. For SPIR, it is further required that the user learns nothing about the other K - 1 messages in the database. Three types of adversaries are considered: a Byzantine adversary who can overwrite the transmission of any B servers to the user; a passive eavesdropper who can tap in on the incoming and outgoing transmissions of any E servers; and a combination of both - an adversary who can tap in on a set of any E nodes, and overwrite the transmission of a set of any B nodes. The problems of SPIR with colluding servers and the three types of adversaries are named T-BSPIR, T-ESPIR and T-BESPIR, respectively. We derive the capacities of the three secure SPIR problems. The results resemble those of secure network coding problems with adversaries and eavesdroppers. The capacity of T-colluding PIR with Byzantine adversaries is characterized in [1]. In this work, we consider T-colluding PIR with an eavedropper (named T-EPIR). We derive the T-EPIR capacity when E >= T; for the case where E <= T, we find an outer bound (converse bound) and an inner bound (achievability) on the optimal achievable rate.

Place, publisher, year, edition, pages
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC , 2019. Vol. 65, no 5, p. 3183-3197
Keywords [en]
Private information retrieval, colluding servers, eavesdropper, Byzantine adversary
National Category
Telecommunications
Identifiers
URN: urn:nbn:se:kth:diva-270653DOI: 10.1109/TIT.2018.2878034ISI: 000466029900033Scopus ID: 2-s2.0-85055708549OAI: oai:DiVA.org:kth-270653DiVA, id: diva2:1417284
Conference
55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), OCT 03-06, 2017, Monticello, IL
Note

QC 20200327

Available from: 2020-03-27 Created: 2020-03-27 Last updated: 2020-03-27Bibliographically 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
Telecommunications

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • 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