Minimax randomized response methods for protecting respondent’s privacy

Randomized response (RR) is a common privacy protection tool. It perturbs each true response using a probabilistic mechanism. Local differential privacy (LDP) is a rigorous privacy protection criterion that demands a guarantee that no intruder will get much new information about any respondent’s true value from its perturbed value. Considering linear unbiased estimation of multinomial probabilities under LDP and squared error loss, we derive minimax RR methods. We address optimal choices for both the RR mechanism (or design) and the estimator. Our minimax design has a particular structure, which is used to define t-subset designs. We describe and study properties of t-subset designs including their practical implementation. We also study mixtures of t-subset designs and examine the RAPPOR method, which is used notably by Google and Apple. We note inadmissibility of the RAPPOR design and offer some suggestions for improving both the design and the customary estimator.