Alpenhorn: Bootstrapping Secure Communication Without Leaking Metadata

David Lazar and Nickolai Zeldovich

Alpenhorn is the first system for establishing session keys between pairs of users, that does not require out-of-band communication and that provides strong privacy and forward secrecy guarantees for all metadata (i.e., information about who is talking to whom). This addresses a significant shortcoming in all prior works on private messaging, which assume an out-of-band key distribution mechanism.

Alpenhorn builds on two ideas. When a user adds a friend for the first time, Alpenhorn ensures the adversary does not learn the friend’s identity, by using identity-based encryption in a novel way to privately determine the friend’s public key. When starting a conversation, Alpenhorn ensures forward secrecy of metadata by storing pairwise shared secrets in friends’ address books, and evolving them over time, using a new keywheel construction.

We implemented a prototype of Alpenhorn, and integrated it into the Vuvuzela private messaging system (which did not previously provide privacy or forward secrecy of metadata when initiating conversations). Integrating Alpenhorn into Vuvuzela required changing just 200 lines of code. Experimental results show that Alpenhorn can scale to many users, supporting 10 million users on three Alpenhorn servers with an average dial latency of 150 seconds and a client bandwidth overhead of 3.7 KB/sec.