  We consider a problem where mutually untrusting curators possess portions of
a vertically partitioned database containing information about a set of
individuals. The goal is to enable an authorized party to obtain aggregate
(statistical) information from the database while protecting the privacy of the
individuals, which we formalize using Differential Privacy. This process can be
facilitated by an untrusted server that provides storage and processing
services but should not learn anything about the database. This work describes
a data release mechanism that employs Post Randomization (PRAM), encryption and
random sampling to maintain privacy, while allowing the authorized party to
conduct an accurate statistical analysis of the data. Encryption ensures that
the storage server obtains no information about the database, while PRAM and
sampling ensures individual privacy is maintained against the authorized party.
We characterize how much the composition of random sampling with PRAM increases
the differential privacy of system compared to using PRAM alone. We also
analyze the statistical utility of our system, by bounding the estimation error
- the expected l2-norm error between the true empirical distribution and the
estimated distribution - as a function of the number of samples, PRAM noise,
and other system parameters. Our analysis shows a tradeoff between increasing
PRAM noise versus decreasing the number of samples to maintain a desired level
of privacy, and we determine the optimal number of samples that balances this
tradeoff and maximizes the utility. In experimental simulations with the UCI
"Adult Data Set" and with synthetically generated data, we confirm that the
theoretically predicted optimal number of samples indeed achieves close to the
minimal empirical error, and that our analytical error bounds match well with
the empirical results.
