Private Information Retrieval with Sublinear Online Time

Explore a conference talk on Private Information Retrieval (PIR) with sublinear online time, presented at Eurocrypt 2020. Delve into the innovative protocol proposed by Henry Corrigan-Gibbs and Dmitry Kogan, which aims to improve the efficiency of PIR systems. Examine the background, protocol efficiency, communication and computation complexity, and preprocessing techniques. Understand the model, results, offline and online phases, failure probability, and security proof. Learn about non-collusion sampling, single-server schemes, and homomorphic encryption applications in PIR. Conclude with a summary of the research and potential open problems in the field.

Introduction
Background
Protocol Efficiency
Communication Complexity
Computation Complexity
Preprocessing
Outline
Model
Results
Offline Phase
Online Phase
Failure Probability
Security Proof
NonCollusion Sampling
Efficiency
Summary
Single Server Scheme
Homomorphic Encryption
Summary Open Problems