Mobile devices are increasingly used for social networking applications, which share data between devices belonging to different users. Today, such applications are implemented as centralized services, forcing users to trust corporations with their personal data. Although decentralized designs for such applications can provide privacy, these designs are difficult to achieve on current devices due to constraints on connectivity, energy, and bandwidth. Contrail is a communication platform that allows decentralized social networks to overcome these challenges. In Contrail, users install content filters that express their interests on their friends' devices; they subsequently receive new data generated by their friends that match the filters. Both data and filters are exchanged between devices via cloud-based relays in encrypted form, giving the cloud no visibility into either. In addition to providing privacy, Contrail enables applications that are highly efficient in terms of both energy and bandwidth. © 1997-2012 IEEE.