Abstract

In this work, we consider private monomial computation (PMC) for replicated noncolluding databases. In PMC, a user wishes to privately retrieve an arbitrary multivariate monomial from a candidate set of monomials in \(f\) messages over a finite field \(\mathbb{F}_q\), where \(q=p^k\) is a power of a prime \(p\) and \(k \ge 1\), replicated over \(n\) databases. We derive the PMC capacity under a technical condition on \(p\) and for asymptotically large \(q\). The condition on \(p\) is satisfied, e.g., for large enough \(p\). Also, we present a novel PMC scheme for arbitrary \(q\) that is capacity-achieving in the asymptotic case above. Moreover, we present formulas for the entropy of a multivariate monomial and for a set of monomials in uniformly distributed random variables over a finite field, which are used in the derivation of the capacity expression.