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

Abstract

Encryption alone is not enough for secure end-toend 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 outof-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.