A lower bound on the release of differentially private integer partitions

- Lower bound on minimax risk for releasing integer partitions under differential privacy.
- For large non-negative integers N, a lower bound of order Ω(N/ε) is provided.
- For small values of N, an optimal lower bound of order Ω(N) is provided.

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).