  We consider a discrete distribution estimation problem under a local
differential privacy (LDP) constraint in the presence of shared randomness. By
exploiting the shared randomness, we suggest a new method for constructing LDP
schemes which achieve the exactly optimal privacy-utility trade-off (PUT) with
the communication cost of less than or equal to the input data size for any
privacy regime. The main idea is to decompose a block design scheme by Park et
al. (2023), based on the combinatorial concept called resolution. The LDP
scheme decomposed from a block design scheme is called a resolution of the
block design scheme, and it achieves the same PUT as the original block design
scheme while requiring a less communication cost. We provide two resolutions of
an exactly PUT-optimal block design scheme, called the Baranyai's resolution
and the cyclic shift resolution, both requiring the communication cost of less
than or equal to the input data size. In particular, we show that the
Baranyai's resolution achieves the minimum communication cost among all the
PUT-optimal resolutions of block design schemes. One drawback of the Baranyai's
resolution is that it can be obtained through a recursive algorithm in general.
In contrast, the cyclic shift resolution has an explicit structure, but its
communication cost can be larger than that of Baranyai's resolution. To
complement this, we also suggest resolutions of other block design schemes
achieving the optimal PUT for some privacy budgets, which require the minimum
communication cost as the Baranyai's resolution and have explicit structures as
the cyclic shift resolution.
