Improved Capacity Outer Bound for Private Quadratic Monomial Computation

Abstract

In private computation, a user wishes to retrieve a function evaluation of messages stored on a set of databases without revealing the function’s identity to the databases. Obead et al. introduced a capacity outer bound for private nonlinear computation, dependent on the order of the candidate functions. Focusing on private quadratic monomial computation, we propose three methods for ordering candidate functions: a graph edge coloring method, a graph-distance method, and an entropy-based greedy method. We confirm, via an exhaustive search, that all three methods yield an optimal ordering for f < 6 messages. For 6 ≤ f ≤ 12 messages, we numerically evaluate the performance of the proposed methods compared with a directed random search. For almost all scenarios considered, the entropy-based greedy method gives the smallest gap to the best-found ordering.