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 \leq f \leq 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.