# 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].

##### MSC:
 68P20 Information storage and retrieval of data
##### Keywords:
$$\Phi$$-hiding assumption; information retrieval