  Integer data is typically made differentially private by adding noise from a
Discrete Laplace (or Discrete Gaussian) distribution. We study the setting
where differential privacy of a counting query is achieved using bit-wise
randomized response, i.e., independent, random bit flips on the encoding of the
query answer.
  Binary error-correcting codes transmitted through noisy channels with
independent bit flips are well-studied in information theory. However, such
codes are unsuitable for differential privacy since they have (by design) high
sensitivity, i.e., neighbouring integers have encodings with a large Hamming
distance. Gray codes show that it is possible to create an efficient
sensitivity 1 encoding, but are also not suitable for differential privacy due
to lack of noise-robustness.
  Our main result is that it is possible, with a constant rate code, to
simultaneously achieve the sensitivity of Gray codes and the noise-robustness
of error-correcting codes (down to the noise level required for differential
privacy). An application of this new encoding of the integers is an
asymptotically faster, space-optimal differentially private data structure for
histograms.
