Oblivious Sampling Algorithms for Private Data Analysis
  We study secure and privacy-preserving data analysis based on queries
executed on samples from a dataset. Trusted execution environments (TEEs) can
be used to protect the content of the data during query computation, while
supporting differential-private (DP) queries in TEEs provides record privacy
when query output is revealed. Support for sample-based queries is attractive
due to \emph{privacy amplification} since not all dataset is used to answer a
query but only a small subset. However, extracting data samples with TEEs while
proving strong DP guarantees is not trivial as secrecy of sample indices has to
be preserved. To this end, we design efficient secure variants of common
sampling algorithms. Experimentally we show that accuracy of models trained
with shuffling and sampling is the same for differentially private models for
MNIST and CIFAR-10, while sampling provides stronger privacy guarantees than
shuffling.
