  We initiate a study of the composition properties of interactive
differentially private mechanisms. An interactive differentially private
mechanism is an algorithm that allows an analyst to adaptively ask queries
about a sensitive dataset, with the property that an adversarial analyst's view
of the interaction is approximately the same regardless of whether or not any
individual's data is in the dataset. Previous studies of composition of
differential privacy have focused on non-interactive algorithms, but
interactive mechanisms are needed to capture many of the intended applications
of differential privacy and a number of the important differentially private
primitives.
  We focus on concurrent composition, where an adversary can arbitrarily
interleave its queries to several differentially private mechanisms, which may
be feasible when differentially private query systems are deployed in practice.
We prove that when the interactive mechanisms being composed are pure
differentially private, their concurrent composition achieves privacy
parameters (with respect to pure or approximate differential privacy) that
match the (optimal) composition theorem for noninteractive differential
privacy. We also prove a composition theorem for interactive mechanisms that
satisfy approximate differential privacy. That bound is weaker than even the
basic (suboptimal) composition theorem for noninteractive differential privacy,
and we leave closing the gap as a direction for future research, along with
understanding concurrent composition for other variants of differential
privacy.
