Paper 2018/607

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

Melissa Chase, Apoorvaa Deshpande, Esha Ghosh, and Harjasleen Malvai


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Verifiable key directoryZero knowledge setsAccumulatorsPKITransparency
Contact author(s)
apoorvaa_deshpande @ brown edu
melissac @ microsoft com
esha ghosh @ microsoft com
hm553 @ cornell edu
2021-10-27: last of 5 revisions
2018-06-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Melissa Chase and Apoorvaa Deshpande and Esha Ghosh and Harjasleen Malvai},
      title = {{SEEMless}: Secure End-to-End Encrypted Messaging with less trust},
      howpublished = {Cryptology ePrint Archive, Paper 2018/607},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.