Efficient and Secure Group Messaging Encryption
Tyler Weitzman
Department of Computer Science
Department of Mathematics
Stanford University
June 4, 2020
1Introduction
Securely asymmetric encryption schemes like RSA have for many years provided cryptographic security
to settings in which two users, Alice and Bob, must communicate without being able to pre-establish a
shared symmetric encryption key in advance of the communication. Diffie-Hellman in particular provides
a convenient way to establish a symmetric key that can then provide a convenient way to communicate
securely over a channel using a scheme such as ElGamal Encryption.
In ElGamal encryption, as done in most public key cryptography encryption schemes, a symmetric key is established and then proceeding communication can occur using a symmetric-key based algorithm such as AES.
In the last few years and since the Edward Snowden reveal of the NSA's leaked documents, there has been a stronger and stronger desire to provide additional security attributes to encryption schemes intended for sending and receiving messages. Namely, three important features of modern encryption schemes used by applications such as Open Whisper System's Signal application are the features of encryption authentication, break-in recovery and forward secrecy.
Encryption authentication is a straight-forward feature (already existing in all standard encryption schemes) which will not be covered in depth as a topic in this paper: encryption authentication is a feature of an encryption scheme which ensures that the ciphertext has not been tampered with and that the decrypted message is indeed the one that was sent. Authentication is easily achieved with an ElGamal Encryption scheme by choosing a symmetric encryption algorithm that provides the authentication built-in, for example AES_GCM is a variant of AES encryption that provides such authentication. In fact, any semantically secure symmetric algorithm can be made into an authenticated encryption scheme by proper use of an authentication function combined with it.
As for break-in recovery and forward secrecy: This paper will include formal definitions for both. For the introduction, it suffices to understand that break-in recovery refers to the ability of the encryption scheme to recover post being compromised: So even if all of Alice's data is stolen, she should be able to recover and restore the security of the system (assuming that the adversary no longer has access to her new data). Forward-secrecy is a security feature in which discovery of the key data for a cipher from today should not allow the adversary to reveal any information about any information that was encrypted in the past. As we will see, both of these features get introduced at once by a simple concept in the encryption scheme.
While modern applications such as Signal do provide such security features in their double-ratchet encryption algorithm, which shall be briefly explained in this paper, there are still serious inefficiencies in the encryption of group communication. Namely, when you consider the situation in which Alice, Bob, Carol (and any group of ) members wish to communicate securely without letting Eve be able to gleam any information on the transmitted data, the current best practice is pair-wise encryption broadcasting; that is, Alice would encrypt the message separately to Bob's key and to Carol's key, and when Carol responds she would encrypt to Bob and Carol.
1
