Recently, this problem has received significant attention in the blockchain/cryptocurrency community as it appears in various applications:

1. Recipient anonymous (instant) messaging.
2. Detecting incoming payments efficiently and privately in stealth address schemes such as Umbra.
3. Light clients for anonymous cryptocurrencies such as Zcash or Monero.

There are 3 main works and approaches to attack this problem.

• Fuzzy Message Detection(ACM CCS 2021) by Gabrielle Back et al. This novel cryptographic scheme employs an untrusted server that coarsely filters the incoming messages for recipients. Each recipient can define a false positive rate $p$ and sends detection keys to the server. The detection keys will match every true positive message for a recipient, and each message not sent to the recipient will also yield a match to the detection keys of the recipient with probability $p$. Note that by construction, given the detection keys, the server can tell the false positive rate of each recipient. The false positive rate $p$ offers a privacy vs. efficiency (bandwidth) tradeoff.

  • If $p=0$, then the recipient only downloads their incoming (true positive messages). This is optimal from an efficiency/bandwidth point of view but does not offer privacy.
  • If $0\leq p \leq 1$, then the user downloads several false positive messages, i.e., in expectation $p(M-TP)$, where $M$ is the number of all messages and $TP$ is the number of true positive messages. This is less efficient than the previous option but provides some levels of anonymity.
  • If $p=1$, then the user downloads all the messages providing maximal recipient anonymity, but this approach is highly inefficient if the server stores numerous messages/transactions.

  For a more thorough anonymity and privacy analysis of this scheme, see this work: The Effect of False Positives: Why Fuzzy Message Detection Leads to Fuzzy Privacy Guarantees? by István A. Seres et al.

• Private Signaling(USENIX 2021) by Varun Madathil et al. This paper observes that any meaningful scheme for this problem should offer full privacy. They propose two approaches:

  • Trusted execution environment (TEE)-based solution. This scheme relies on an untrusted server and a TEE, e.g., Intel SGX. It is an efficient and private solution but relies on the strong assumption of TEE.
  • Garbled circuit-based solution. This scheme assumes two non-colluding servers that execute a garbled circuit. The garbled circuit encodes the detection of the messages. It is a fully private solution and efficient for senders and recipients, but it requires quite some heavy work from the two servers.

• Oblivious Message Retrieval(CRYPTO 2022) by Zeyu Liu and Eran Tromer. This scheme applies FHE to solve this problem. It provides full privacy and is somewhat efficient, but users need to have large detection keys, approximately $1$GB large. For constrained devices, large detection keys might make this scheme impractical. This scheme is currently under development for the Zcash cryptocurrency. See it here.

Recently, this problem has received significant attention in the blockchain/cryptocurrency community as it appears in various applications:

1. Recipient anonymous (instant) messaging.
2. Detecting incoming payments efficiently and privately in stealth address schemes such as Umbra.
3. Light clients for anonymous cryptocurrencies such as Zcash or Monero.

There are 3 main works and approaches to attack this problem.

• Fuzzy Message Detection(ACM CCS 2021) by Gabrielle Back et al. This novel cryptographic scheme employs an untrusted server that coarsely filters the incoming messages for recipients. Each recipient can define a false positive rate $p$ and sends detection keys to the server. The detection keys will match every true positive message for a recipient, and each message not sent to the recipient will also yield a match to the detection keys of the recipient with probability $p$. Note that by construction, given the detection keys, the server can tell the false positive rate of each recipient. The false positive rate $p$ offers a privacy vs. efficiency (bandwidth) tradeoff.

  • If $p=0$, then the recipient only downloads their incoming (true positive messages). This is optimal from an efficiency/bandwidth point of view but does not offer privacy.
  • If $0\leq p \leq 1$, then the user downloads several false positive messages, i.e., in expectation $p(M-TP)$, where $M$ is the number of all messages and $TP$ is the number of true positive messages. This is less efficient than the previous option but provides some levels of anonymity.
  • If $p=1$, then the user downloads all the messages providing maximal recipient anonymity, but this approach is highly inefficient if the server stores numerous messages/transactions.

  For a more thorough anonymity and privacy analysis of this scheme, see this work: The Effect of False Positives: Why Fuzzy Message Detection Leads to Fuzzy Privacy Guarantees? by István A. Seres et al.

• Private Signaling(USENIX 2021) by Varun Madathil et al. This paper observes that any meaningful scheme for this problem should offer full privacy. They propose two approaches:

  • Trusted execution environment (TEE)-based solution. This scheme relies on an untrusted server and a TEE, e.g., Intel SGX. It is an efficient (constant work for both sender and recipient) and private solution but relies on the strong assumption of TEE.
  • Garbled circuit-based solution. This scheme assumes two non-colluding servers that execute a garbled circuit. The garbled circuit encodes the detection of the messages. It is a fully private solution and efficient for senders and recipients (constant work again), but it requires quite some heavy work from the two servers.

• Oblivious Message Retrieval(CRYPTO 2022) by Zeyu Liu and Eran Tromer. This scheme applies FHE to solve this problem. It provides full privacy and is somewhat efficient, but users need to have large detection keys, approximately $1$GB large. For constrained devices, large detection keys might make this scheme impractical. This scheme is currently under development for the Zcash cryptocurrency. See it here.