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 [less than or equal to] 50 participants. Finally, I propose an improvement to the DP5 private presence protocol that reduces the message size from quadratic to logarithmic. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com/en-US/products/dissertations/individuals.shtml.]