Computationally private information retrieval with polylogarithmic communication. (English) Zbl 0932.68042

Cachin, Christian; Micali, Silvio; Stadler, Markus

Stern, Jacques (ed.), Advances in cryptology - EUROCRYPT ’99. 17th annual Eurocrypt conference, international conference on The theory and application of cryptographic techniques, Prague, Czech Republic, May 2–6, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1592, 402-414 (1999).

Summary: 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 \(\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.
For the entire collection see [Zbl 0912.00038].

MSC:

68P20

Information storage and retrieval of data

Keywords:

\(\Phi\)-hiding assumption; information retrieval