Random Differential Privacy
  We propose a relaxed privacy definition called {\em random differential
privacy} (RDP). Differential privacy requires that adding any new observation
to a database will have small effect on the output of the data-release
procedure. Random differential privacy requires that adding a {\em randomly
drawn new observation} to a database will have small effect on the output. We
show an analog of the composition property of differentially private procedures
which applies to our new definition. We show how to release an RDP histogram
and we show that RDP histograms are much more accurate than histograms obtained
using ordinary differential privacy. We finally show an analog of the global
sensitivity framework for the release of functions under our privacy
definition.
