To be useful and widely accepted, automated contact tracing / expo-
sure notification schemes need to solve two problems at the same time:
they need to protect the privacy of users while also protecting the users’
from the behavior of a malicious adversary who may potentially cause a
false alarm. In this paper, we provide, for the first time, an exposure
notification construction that guarantees the same levels of privacy as ex-
isting schemes (notably, the same as CleverParrot of [CKL+20]), which
also provides the following integrity guarantees: no malicious user can
cause exposure warnings in two locations at the same time; and any up-
loaded exposure notifications must be recent, and not previously used.
We provide these integrity guarantees while staying efficient by only re-
quiring a single broadcast message to complete multiple contacts. Also,
a user’s upload remains linear in the number of contacts, similar to other
schemes. Linear upload complexity is achieved with a new primitive: zero
knowledge subset proofs over commitments. Our integrity guarantees are
achieved with a new primitive as well: set commitments on equivalence
classes. Both of which are of independent interest.

Go to Source of this post
Author Of this post: Scott Griffy

By admin