  We introduce cryptographic protocols for securely and efficiently computing
the cardinality of set union and set intersection. Our private set-cardinality
protocols (PSC) are designed for the setting in which a large set of parties in
a distributed system makes observations, and a small set of parties with more
resources and higher reliability aggregates the observations. PSC allows for
secure and useful statistics gathering in privacy-preserving distributed
systems. For example, it allows operators of anonymity networks such as Tor to
securely answer the questions: "How many unique users are using the network?"
and "How many hidden services are being accessed?".
  We prove the correctness and security of PSC in the Universal Composability
framework against an active adversary that compromises all but one of the
aggregating parties. Although successful output cannot be guaranteed in this
setting, PSC either succeeds or terminates with an abort, and we furthermore
make the adversary accountable for causing an abort by blaming at least one
malicious party. We also show that PSC prevents adaptive corruption of the data
parties from revealing past observations, which prevents them from being
victims of targeted compromise, and we ensure safe measurements by making
outputs differentially private.
  We present a proof-of-concept implementation of PSC and use it to demonstrate
that PSC operates with low computational overhead and reasonable bandwidth. It
can count tens of thousands of unique observations from tens to hundreds of
data-collecting parties while completing within hours. PSC is thus suitable for
daily measurements in a distributed system.
