Computationally Private Information Retrieval with

Computationally Private Information Retrieval withPolylogarithmic Communication ( cross ref of... Breaking the O(n1=(2k􀀀1)) Barrier forInformation-Theoretic Private Information Retrieval )

 

Abstract

We present a single-database computationally private information retrieval scheme with polylogarithmic communication complexity. Our construction is based on a new, but reasonable intractability assumption, which we call the -Hiding Assumption ( HA): essentially the di -culty of deciding whether a small prime divides

-(m), where m is a composite integer of unknown

factorization.

Keywords:

Integer factorization, Euler's function, -hiding assumption, private information retrieval.