Cryptology ePrint Archive: Report 2018/607

SEEMless: Secure End-to-End Encrypted Messaging with less trust

Melissa Chase and Apoorvaa Deshpande and Esha Ghosh and Harjasleen Malvai

Abstract: End-to-end encrypted messaging (E2E) is only secure if participants have a way to retrieve the correct public key for the desired recipient. However, to make these systems usable, users must be able to replace their keys (e.g. when they lose or reset their devices, or reinstall their app), and we cannot assume any cryptographic means of authenticating the new keys. In the current E2E systems, the service provider manages the directory of public keys of its registered users; this allows a compromised or coerced service provider to introduce their own keys and execute a man in the middle attack.

Building on the approach of CONIKS (Melara et al, USENIX Security `15), we formalize the notion of a Privacy-Preserving Verifiable Key Directory (VKD): a system which allows users to monitor the keys that the service is distributing on their behalf. We then propose a new VKD scheme which we call SEEMless, which improves on prior work in terms of privacy and scalability. In particular, our new approach allows key changes to take effect almost immediately; we show experimentally that our scheme easily supports delays less than a minute, in contrast to previous work which proposes a delay of one hour.

Category / Keywords: cryptographic protocols / Verifiable key directory; Zero knowledge sets; Accumulators; PKI; Transparency

Date: received 16 Jun 2018, last revised 27 Oct 2021

Contact author: apoorvaa_deshpande at brown edu, melissac at microsoft com, esha ghosh at microsoft com, hm553 at cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20211027:144741 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]