Computationally Private Information Retrieval with Polylogarithmic Communication

摘要

We present a sinle-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 #PHI#-Hiding Assumption (#PHI#HA): essentially the difficulty of deciding whether a small prime divides #PHI#(m), where m is a composite integer of unknown factorization.