The growing spread of smartphones and other mobile devices has given rise to a number of health and fitness applications. Users can track their calorie intake, get reminders to take their medication, and track their fitness workouts. Many of these services have social components, allowing users to find like-minded peers, compete with their friends, or participate in open challenges. However, the prevalent service model forces users to disclose all of their data to the service provider. This may include sensitive information, like their current position or medical conditions. In this thesis, we will design, implement and evaluate a privacy-preserving fitness data sharing system. The system provides privacy not only towards other users, but also against the service provider, does not require any Trusted Third Parties (TTPs), and is backed by strong cryptography. Additionally, it hides the communication metadata (i.e. who is sharing data with whom). We evaluate the security of the system with empirical and formal methods, including formal proofs for parts of the system. We also investigate the performance with empirical data and a simulation of a large-scale deployment. Our results show that the system can provide strong privacy guarantees. However, it incurs a significant networking overhead for large deployments.