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 ε -differentially private mechanism releasing a partition of a sufficiently large non-negative integer N must incur a minimax risk of order N/ε. Moreover, for small values of N, we provide an optimal lower bound of order N.