We consider a setup in which confidential i.i.d. samples X 1 , ..., X n from an unknown discrete distribution P X are passed through a discrete memoryless privatization channel (a.k.a. mechanism) which guarantees an ∊-level of local differential privacy. For a given ∊, the channel should be designed such that an estimate of the source distribution based on the channel outputs converges as fast as possible to the exact value P X . For this purpose we consider two metrics of estimation accuracy: the expected mean-square error and the expected Kullback-Leibler divergence. We derive their respective normalized first-order terms (as n → ∞), which for a given target privacy ∊ represent the factor by which the sample size must be augmented so as to achieve the same estimation accuracy as that of an identity (non-privatizing) channel. We formulate the privacy-utility tradeoff problem as being that of minimizing said first-order term under a privacy constraint ∊. A converse bound is stated which bounds the optimal tradeoff away from the origin. Inspired by recent work on the optimality of staircase mechanisms (albeit for objectives different from ours), we derive an achievable tradeoff based on circulant step mechanisms. Within this finite class, we determine the optimal step pattern.