  Contact tracing is an essential tool in containing infectious diseases such
as COVID-19. Many countries and research groups have launched or announced
mobile apps to facilitate contact tracing by recording contacts between users
with some privacy considerations. Most of the focus has been on using random
tokens, which are exchanged during encounters and stored locally on users'
phones. Prior systems allow users to search over released tokens in order to
learn if they have recently been in the proximity of a user that has since been
diagnosed with the disease. However, prior approaches do not provide end-to-end
privacy in the collection and querying of tokens. In particular, these
approaches are vulnerable to either linkage attacks by users using token
metadata, linkage attacks by the server, or false reporting by users.
  In this work, we introduce Epione, a lightweight system for contact tracing
with strong privacy protections. Epione alerts users directly if any of their
contacts have been diagnosed with the disease, while protecting the privacy of
users' contacts from both central services and other users, and provides
protection against false reporting. As a key building block, we present a new
cryptographic tool for secure two-party private set intersection cardinality
(PSI-CA), which allows two parties, each holding a set of items, to learn the
intersection size of two private sets without revealing intersection items. We
specifically tailor it to the case of large-scale contact tracing where clients
have small input sets and the server's database of tokens is much larger.
