Computationally Private Information Retrieval with
Polylogarithmic Communication
Christian Cachin∗
Silvio Micali†
Markus Stadler‡
July 12, 1999
A preliminary version of this paper appears in Proceedings of EUROCRYPT ’99 (J. Stern, ed.),
Lecture Notes in Computer Science, Springer, 1999.
Abstract
We present a single-database computationally private information retrieval scheme with poly-
logarithmic communication complexity. Our construction is based on a new, but reasonable
intractability assumption, which we call the Φ-Hiding Assumption (ΦHA): essentially the diffi-
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.
1 Introduction
Private information retrieval. The notion of private information retrieval (PIR for short)
was introduced by Chor, Goldreich, Kushilevitz and Sudan [CGKS95] and has already received a
lot of attention. The study of PIR is motivated by the growing concern about the user’s privacy
when querying a large commercial database. (The problem was independently studied by Cooper
and Birman [CB95] to implement an anonymous messaging service for mobile users.)
Ideally, the PIR problem consists of devising a communication protocol involving just two
parties, the database and the user, each having a secret input. The database’s secret input is called
the data string, an n-bit string B = b1b2 · · · bn. The user’s secret input is an integer i between 1
and n. The protocol should enable the user to learn bi in a communication-efficient way and at
the same time hide i from the database. (The trivial and inefficient solution is having the database
send the entire string B to the user.)
Information-theoretic PIRs (with database replication). Perhaps surprisingly, the orig-
inal paper [CGKS95] shows that the PIR problem is solvable efficiently in an information-theoretic
setting if the database does not consist of a single player, but of multiple