Real World Crypto 2015: Are you there Bob? It's me, Alice.

Social media are all about the three F's: friends, fans and followers. But what if you want to keep your list of F-buddies private? On the final day of the Real World Crypto workshop Ian Goldberg spoke about how we can advertise our presence online to our friends without revealing our relationship graph.

In the 90s, people would fire up ICQ instant messenger and an ear-splitting foghorn sound effect would announce their presence online to everyone on their street. Friends further away relied on notification from the ICQ server, with the server knowing when users are online and who their friends are. In today's more privacy-sensitive climate this is undesirable, as the service operator may be legally compelled to surrender this data to governments on request.

The Dagstuhl Privacy Preserving Presence Protocol P (DP5 - the extra P is for patter) allows a service operator to provide this online presence information without learning the information itself, and so freely comply with search warrants without compromising user privacy.

The DP5 protocol keeps a friendship database and a presence database, and assumes two parties wishing to communicate already a hold shared key. Time is divided into long-term epochs T over which friendship data can be updated, and short-term epochs t over which status data can be updated.

In each long-term epoch T, Alice evaluates two PRFs at the point T under the key she shares with Bob in order to generate a public identifier ID and an epoch key K. She generates a public key P and encrypts it under the epoch key. This ciphertext C and the ID are stored in the friendship database.

In each short-term epoch t, Alice evaluates a third PRF at the point t under a key derived through hashing her public key P, generating an encryption key k. She then encrypts a status message under key k. This ciphertext c and an identifier derived from P are stored in the presence database.

When Bob wants to know if Alice is online, he evaluates the appropriate PRFs at point T under their shared key to recover the epoch key K and identifier ID. He pulls the corresponding record from the friendship database and decrypts the ciphertext C to recover Alice's public key P. He then computes from P the key k and the identifier for the presence database, pulling the corresponding record and decrypting the ciphertext under k. If decryption is successful then Alice is online and her status message is revealed, otherwise he concludes that Alice is offline.

This is a simplified explanation of the DP5 protocol, which makes use of Private Information Retrieval to ensure the server is unaware of the nature of the database queries. PIR is a beast, so the protocol doesn't scale too well, but it does provide a private way to tell your friends you're online and let them know your status.

***** X_Br1sT0L_B10gGeR_X is offline *****