Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Converse for Multi-Server Single-Message PIR with Side Information
 
Loading...
Thumbnail Image
conference paper

Converse for Multi-Server Single-Message PIR with Side Information

Li, Su  
•
Gastpar, Michael C.  
2020
2020 54th Annual Conference on Information Sciences and Systems (CISS)
54th Annual Conference on Information Sciences and Systems (CISS)

Multi-server single-message private information retrieval is studied in the presence of side information. In this problem, K independent messages are replicatively stored at N non-colluding servers. The user wants to privately download one message from the servers without revealing the index of the message to any of the servers, leveraging its M side information messages. We assume that the servers only know the number of the side information messages available at the user but not their indices. We prove a converse bound on the maximum download rates, which coincides with the known achievability scheme proposed by Kadhe et. al.. Hence, we characterize the capacity for this problem, which is (1 +1/N+ 1/N 2 + · · · + N⌈1K/M+1⌉ -1 ) -1 . The proof leverages a novel concept that we call virtual side information, which, for a fixed query and any message, identifies the side information that would be needed in order to recover that message.

  • Details
  • Metrics
Type
conference paper
DOI
10.1109/CISS48834.2020.1570612786
Author(s)
Li, Su  
•
Gastpar, Michael C.  
Date Issued

2020

Published in
2020 54th Annual Conference on Information Sciences and Systems (CISS)
ISBN of the book

978-1-728188-31-7

Start page

1

End page

6

URL

View record in ArXiv

https://arxiv.org/abs/1809.09861
Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LINX  
Event nameEvent placeEvent date
54th Annual Conference on Information Sciences and Systems (CISS)

Princeton, NJ, USA

March 18-20, 2020

Available on Infoscience
May 27, 2021
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/178384
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés