  Differential privacy (DP) has arisen as the state-of-the-art metric for
quantifying individual privacy when sensitive data are analyzed, and it is
starting to see practical deployment in organizations such as the US Census
Bureau, Apple, Google, etc. There are two popular models for deploying
differential privacy - standard differential privacy (SDP), where a trusted
server aggregates all the data and runs the DP mechanisms, and local
differential privacy (LDP), where each user perturbs their own data and
perturbed data is analyzed. Due to security concerns arising from aggregating
raw data at a single server, several real world deployments in industry have
embraced the LDP model. However, systems based on the LDP model tend to have
poor utility - "a gap" in the utility achieved as compared to systems based on
the SDP model.
  In this work, we survey and synthesize emerging directions of research at the
intersection of differential privacy and cryptography. First, we survey
solutions that combine cryptographic primitives like secure computation and
anonymous communication with differential privacy to give alternatives to the
LDP model that avoid a trusted server as in SDP but close the gap in accuracy.
These primitives introduce performance bottlenecks and necessitate efficient
alternatives. Second, we synthesize work in an area we call "DP-Cryptography" -
cryptographic primitives that are allowed to leak differentially private
outputs. These primitives have orders of magnitude better performance than
standard cryptographic primitives. DP-cryptographic primitives are perfectly
suited for implementing alternatives to LDP, but are also applicable to
scenarios where standard cryptographic primitives do not have practical
implementations. Through this unique lens of research taxonomy, we survey
ongoing research in these directions while also providing novel directions for
future research.
