Private Message Detection (PMD) as a new cryptographic primitive has been identified lately. A PMD protocol aims to allow users to efficiently and privately detect and retrieve their recipient-anonymous messages from a public bulletin board or an untrusted server. Such protocols have promising applications in anonymous messaging (e.g., Signal, Niwl) and privacy-preserving payment systems (Zcash, Monero, stealth payments for Bitcoin, Ethereum, and other privacy-enhancing overlays). A private but inherently inefficient solution would be downloading all the ciphertexts from the bulletin board or the server. Afterwards, users try to decrypt each ciphertext, and eventually, they’ll find all their pertinent messages. PMD protocols aim to improve the efficiency of this naive approach without sacrificing recipient anonymity. Very recently, three works have been published as pre-prints (Fuzzy Message Detection (FMD) by Beck et al. (CCS'21), Private Signaling by Madathil et al. (under submission), and Oblivious Message Retrieval by Liu and Tromer (under submission)) proposing efficient and private message detection schemes under various privacy and security assumptions.

In this talk, we will briefly introduce and describe the three proposed PMD schemes. We make a comparison of the schemes, highlighting interesting trade-offs between them. Subsequently, we will give a privacy and anonymity analysis of the Fuzzy Message Detection (FMD) scheme proposed by Beck et al. (CCS'21). We will show how FMD fails to provide information-theoretic privacy guarantees (recipient unlinkability and relationship anonymity) and how it achieves weak notions of differential privacy. We describe a game-theoretical analysis of the incentives underlying the FMD scheme. We report our simulation of the FMD scheme on real-world communication networks. Finally, we conclude with open questions and future directions in the PMD field.