Paper 2023/081

Parakeet: Practical Key Transparency for End-to-End Encrypted Messaging

Harjasleen Malvai, University of Illinois Urbana-Champaign
Lefteris Kokoris-Kogias, IST Austria, Mysten Labs
Alberto Sonnino, Mysten Labs, University College London
Esha Ghosh, Microsoft Research
Ercan Oztürk, Meta
Kevin Lewi, Meta
Sean Lawlor, Meta

Encryption alone is not enough for secure end-to-end encrypted messaging: a server must also honestly serve public keys to users. Key transparency has been presented as an efficient solution for detecting (and hence deterring) a server that attempts to dishonestly serve keys. Key transparency involves two major components: (1) a username to public key mapping, stored and cryptographically committed to by the server, and, (2) an out-of-band consistency protocol for serving short commitments to users. In the setting of real-world deployments and supporting production scale, new challenges must be considered for both of these components. We enumerate these challenges and provide solutions to address them. In particular, we design and implement a memory-optimized and privacy-preserving verifiable data structure for committing to the username to public key store. To make this implementation viable for production, we also integrate support for persistent and distributed storage. We also propose a future-facing solution, termed ''compaction'', as a mechanism for mitigating practical issues that arise from dealing with infinitely growing server data structures. Finally, we implement a consensusless solution that achieves the minimum requirements for a service that consistently distributes commitments for a transparency application, providing a much more efficient protocol for distributing small and consistent commitments to users. This culminates in our production-grade implementation of a key transparency system (Parakeet) which we have open-sourced, along with a demonstration of feasibility through our benchmarks.

Available format(s)
Publication info
Published elsewhere. NDSS
key-transparencyend-to-end encrypted messagingPKIreliable broadcast
Contact author(s)
hmalvai2 @ illinois edu
ekokoris @ ist ac at
alberto @ mystenlabs com
esha ghosh @ microsoft com
eoz @ meta com
klewi @ meta com
seanlawlor @ meta com
2023-03-15: revised
2023-01-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Harjasleen Malvai and Lefteris Kokoris-Kogias and Alberto Sonnino and Esha Ghosh and Ercan Oztürk and Kevin Lewi and Sean Lawlor},
      title = {Parakeet: Practical Key Transparency for End-to-End Encrypted Messaging},
      howpublished = {Cryptology ePrint Archive, Paper 2023/081},
      year = {2023},
      doi = {10.14722/ndss.2023.24545},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.