Communication privacy is constantly under threat from Nation State Adversaries (NSA). This has led many platforms, such as Facebook and Apple, to implement secure conversation cryptographic protocols in their messaging applications. However, many of the protocols do not provide provable security and do not provide other security guarantees about the conversation. One example of a missing security property is message order consistency between all participants. In this dissertation I demonstrate practical attacks against a popular private messaging protocol and application (Signal). I propose two private group messaging protocols with provable privacy properties for two networking models; online instant messaging, and mobile messaging. I show the performance of these models is practical for mutually authenticated groups ≤ 50 participants. Finally, I propose an improvement to the DP5 private presence protocol that reduces the message size from quadratic to logarithmic.