zbMATH — the first resource for mathematics

Computationally private information retrieval with polylogarithmic communication. (English) Zbl 0932.68042
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].

68P20 Information storage and retrieval of data