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
Secure Symmetric Private Information Retrieval from Colluding Databases with Adversaries
KTH, School of Electrical Engineering and Computer Science (EECS), Information Science and Engineering.
KTH, School of Electrical Engineering (EES).ORCID iD: 0000-0002-7926-5081
2017 (English)In: 2017 55TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON), IEEE , 2017, p. 1083-1090Conference paper, Published paper (Refereed)
Abstract [en]

The problem of symmetric private information retrieval (SPIR) from replicated databases with colluding servers and adversaries is studied. Specifically, the database comprises K files, which are replicatively stored among N servers. A user wants to retrieve one file from the database by communicating with the N servers, without revealing the identity of the desired file to any server. Furthermore, the user shall learn nothing about the other K - 1 files in the database. 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. An adversary in the system can tap in on or even try to corrupt the communication. 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. The capacity of the problem is defined as the maximum number of information bits of the desired file retrieved per downloaded bit. We show that the information-theoretical capacity of the T-BSPIR problem equals 1-2B+T/N, if the servers share common randomness (unavailable at the user) with amount at least 2B+T/N-2B-T times the file size. Otherwise, the capacity equals zero. The information-theoretical capacity of the T-ESPIR problem is proved to equal 1 - max(T, E)/N, if the servers share common randomness with amount at least max(T, E)/N-max(T, E) times the file size. Finally, for the problem of T-BESPIR, the capacity is proved to be 1 - 2B+max(T, E)/N, where the common randomness shared by the servers should be at least 2B+max(T, E)/N-2B-max(T, E) times the file size. The results resemble those of secure network coding problems with adversaries and eavesdroppers.

Place, publisher, year, edition, pages
IEEE , 2017. p. 1083-1090
Series
Annual Allerton Conference on Communication Control and Computing, ISSN 2474-0195
National Category
Telecommunications
Identifiers
URN: urn:nbn:se:kth:diva-226278ISI: 000428047800148ISBN: 978-1-5386-3266-6 OAI: oai:DiVA.org:kth-226278DiVA, id: diva2:1198955
Conference
55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), OCT 03-06, 2017, Monticello, IL
Note

QC 20180419

Available from: 2018-04-19 Created: 2018-04-19 Last updated: 2018-05-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Authority records BETA

Skoglund, Mikael

Search in DiVA

By author/editor
Wang, QiwenSkoglund, Mikael
By organisation
Information Science and EngineeringSchool of Electrical Engineering (EES)
Telecommunications

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 7 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