A lower bound on the release of differentially private integer partitions

We consider the problem of privately releasing integer partitions. This problem is of high practical interest, being related to the publication of password frequency lists or the degree distribution of social networks. In this work, we show that any epsilon-differentially private mechanism releasing a partition of a sufficiently large non-negative integer N must incur a minimax risk of order Omega(root N/epsilon). Moreover, for small values of N, we provide an optithal lower bound of order Omega(N). (C) 2017 Elsevier B.V. All rights reserved.