Paper 2024/107

ELEKTRA: Efficient Lightweight multi-dEvice Key TRAnsparency

Julia Len, Cornell Tech
Melissa Chase, Microsoft Research Redmond
Esha Ghosh, Microsoft Research Redmond
Daniel Jost, New York University
Balachandar Kesavan, Zoom Video Communications
Antonio Marcedone, Zoom Video Communications

Key Transparency (KT) systems enable service providers of end-to-end encrypted communication (E2EE) platforms to maintain a Verifiable Key Directory (VKD) that maps each user's identifier, such as a username or email address, to their identity public key(s). Users periodically monitor the directory to ensure their own identifier maps to the correct keys, thus detecting any attempt to register a fake key on their behalf to Meddler-in-the-Middle (MitM) their communications. We introduce and formalize a new primitive called Multi-Device Verifiable Key Directory (MVKD), which strengthens both the security, privacy, and usability guarantees of VKD by leveraging the multi-device setting. We formalize three properties for a MVKD (completeness, extraction-based soundness, and privacy), striking a non-trivial balance between strong guarantees and the limitations imposed by a truly practical system. We then present a new MVKD system called ELEKTRA. This system combines the core of the Keybase KT system (running in production since 2014) with ideas from SEEMless (Chase et. al., 2019) and RZKS (Chen et. al., 2022). Our construction is the first to achieve the above multi-device guarantees while having formal security and privacy proofs. Finally, we implement ELEKTRA and present benchmarks demonstrating its practicality.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACM CCS 2023
key transparencyverifiable key directory
Contact author(s)
jlen @ cs cornell edu
melissac @ microsoft com
esha ghosh @ microsoft com
daniel jost @ cs nyu edu
surya heronhaye @ zoom us
antonio marcedone @ zoom us
2024-01-26: approved
2024-01-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Julia Len and Melissa Chase and Esha Ghosh and Daniel Jost and Balachandar Kesavan and Antonio Marcedone},
      title = {ELEKTRA: Efficient Lightweight multi-dEvice Key TRAnsparency},
      howpublished = {Cryptology ePrint Archive, Paper 2024/107},
      year = {2024},
      doi = {10.1145/3576915.3623161},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.