Paper 2021/853

Private Signaling

Varun Madathil, Alessandra Scafuro, István András Seres, Omer Shlomovits, and Denis Varlakov

Abstract

We introduce the problem of private signaling. In this problem, a sender posts a message to a certain location of a public bulletin board, and then computes a signal that allows only the intended recipient (and no one else) to learn that it is the recipient of the posted message. Besides privacy, this problem has the following crucial efficiency requirements. First, the sender and recipient do not participate in any out-of-band communication, and second, the overhead of the recipient should be asymptotically better than scanning the entire board. Existing techniques, such as the server-aided fuzzy message detection (Beck et al., CCS’21), could be employed to solve the private signaling problem. However, this solution requires that the computational effort of the recipient grows with the amount of privacy desired, providing no saving over scanning the entire board if the maximum privacy is required. In this work, we present a server-aided solution to the private signaling problem that guar- antees full privacy for all recipients, while requiring only constant amount of work for both the recipient and the sender. We provide the following contributions. First, we provide a formal definition of private signaling in the Universal Composability (UC) framework and show that it generalizes several real-world settings where recipient anonymity is desired. Second, we present two protocols that UC-realize our definition: one using a single server equipped with a trusted execution environment, and one based on two servers that employs garbled circuits. Third, we provide an open-source implementation of both of our protocols and evaluate their performance and show that they are practical.