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