Toward efficient, privacy-aware media classification on public databases∗

The ability to search databases by providing multimedia ex-amples of voices, faces, or locations instead of textual de-scriptions can be tremendously useful. At the same time, uploading media for queries—especially media that contains sensitive content—means sharing private information with a potentially untrusted service provider. The growing field of privacy-preserving database searches attempts to resolve this tension. Within this scope of private searches, private media classification and retrieval is particularly challenging due to the inherent inexactness of recognition; to be useful, image or other media classification systems must identify approximate matches rather than just exact ones. This is difficult to reconcile with distortion-intolerant and resource-heavy privacy primitives, especially in web-scale databases. In this paper, we present an architecture for media clas-sification on public databases that preserves client privacy while achieving asymptotic communication and computa-tion costs that are sublinear in the size of the database. We demonstrate the usefulness of this architecture in the con-text of a privacy-preserving face recognition system. We ob-serve order-of-magnitude speedups over state-of-the-art pri-vate face recognition systems