# Navigating Prompt Complexity for Zero-Shot Classification: A Study of Large
Language Models in Computational Social Science

Yida Mu, Ben P. Wu, William Thorne, Ambrose Robinson Nikolaos Aletras,
Carolina Scarton, Kalina Bontcheva, Xingyi Song
Department of Computer Science, The University of Sheffield
{y.mu, bpwu1, wthorne1, arobinson10, n.aletras, c.scarton, k.bontcheva,
<EMAIL_ADDRESS>

###### Abstract

Instruction-tuned Large Language Models (LLMs) have exhibited impressive
language understanding and the capacity to generate responses that follow
specific instructions. However, due to the computational demands associated
with training these models, their applications often rely on zero-shot
settings. In this paper, we evaluate the zero-shot performance of two publicly
accessible LLMs, ChatGPT and OpenAssistant, in the context of Computational
Social Science classification tasks, while also investigating the effects of
various prompting strategies. Our experiment considers the impact of prompt
complexity, including the effect of incorporating label definitions into the
prompt, using synonyms for label names, and the influence of integrating past
memories during the foundation model training. The findings indicate that in a
zero-shot setting, the current LLMs are unable to match the performance of
smaller, fine-tuned baseline transformer models (such as BERT). Additionally,
we find that different prompting strategies can significantly affect
classification accuracy, with variations in accuracy and F1 scores exceeding
10%.

##  1 Introduction

Instruction fine-tuning and Reinforcement Learning with Human Feedback (RLHF)
(Christiano et al., 2017) has facilitated transfer learning for Large Language
Models (LLMs) to unseen tasks at scale. To leverage LLMs as versatile natural
language processors, there is an immediate effort to ascertain their zero-shot
performance on challenging tasks. Social media is an active area of research
with a number of complex, domain-specific tasks which can utilised for harm
reduction (Waseem et al., 2017) and preventing the spread of misinformation
(Zubiaga et al., 2018). While LLMs have great potential to assist in this
domain, through applications such as automatic data annotation and social
media analysis, it is important to understand their capabilities.

We focus on modifying prompts in a zero-shot context, since this is a commonly
proposed application of LLMs in academic, commercial and public settings
Kuzman et al. (2023). The large parameter counts of LLMs enable impressive
reasoning ability as well as deep comprehension of their training corpus,
making them attractive for natural language tasks Wei et al. (2022a). However,
the cost of fine-tuning these models on downstream tasks is often infeasible
and closed source models cannot be easily fine-tuned by the end users.

In this paper, we evaluate two popular assistant-oriented LLMs, OpenAssistant
(OA) and GPT-3.5-turbo (ChatGPT), by instructing them with natural language
prompts on six social media-based NLP tasks. We compare against baselines that
use standard techniques such as fine-tuning BERT.

GPT-3.5-turbo is a commercial implementation of Instruct-GPT Ouyang et al.
(2022). It uses RLHF to help align the language model to human preferences,
mitigate toxic outputs and improve response usefulness. This builds on the
original work in NLP by Stiennon et al. (2020) who used RLHF to improve
summarisation performance. The success of GPT-3.5-turbo encouraged rapid
competition from the community.

OpenAssistant (OA) Köpf et al. (2023) is a major open-source competitor to
GPT-3.5-turbo. They released an open-source dataset and framework to fine-tune
LLMs as well a collection of fine-tuned models. In our work we use the fine-
tuned OpenAssistant-SFT-7-LLaMA-30B version. In their paper, the OpenAssistant
authors conducted a preference study of 7042 examples, comparing the outputs
of ChatGPT and a Pythia-12B OA model. The outputs of the OA model were chosen
to be 95.3% as preferable as its competitor.

In this work, we aim to examine the use of different prompting strategies for
the evaluation of zero-shot performance of LLMs in computational social
science. To that end, we conduct a battery of controlled experiments to
investigate the zero-shot performance of using basic and complex prompting
strategies (e.g., including paper information in the prompt) against
supervised approaches. In addition, we explore the possibility of replacing
the original labels with synonyms to investigate the generalizability of LLMs.

Dataset | # of Posts | Class (# of Posts)
---|---|---
Rumour Stance | 5,568 | Support (1,004) / Deny (415) / Query (464) / Comment (3,685)
Vaccine Stance | 2,792 | Pro Vaccine (991) / Anti Vaccine (791) / Neutral (1,010)
Complaint | 3,449 | Complaint (1,232) / Not Complaint (2,217)
Bragging | 6,696 | Bragging (781) / Not Bragging (5,915)
Sarcasm | 4,868 | Sarcasm (1,067) / Not Sarcasm (3,801)
Hate speech | 16,907 | Offensive (5,348) / Non-offensive (11,559)
Table 1: Dataset Specifications.

##  2 Data

In this paper, we evaluate the zero-shot classification performance of LLMs on
six NLP tasks in computational social science. These datasets are in English
with manually annotated class labels. We display dataset specifications and
statistics in Table 1.

  * •

Rumour Stance We first evaluate the RumorEval 2017 dataset which is developed
by Derczynski et al. (2017). Here, we use the dataset for the 4-way stance
classification, i.e., determining the stance of a reply towards a given source
post (i.e. rumour) as either supporting, denying, questioning, or commenting.

  * •

Sarcasm The sarcasm detection task is to identify whether a given tweet is
intended to be sarcastic or not. We evaluate the task on the Semeval-2022 Task
6 dataset (Farha et al., 2022), which contains 4,868 tweets labelled as either
sarcasm or not sarcasm.

  * •

Vaccine Stance This task aims to automatically predict the stance of tweets
towards the COVID-19 vaccination (Cotfas et al., 2021). This dataset provides
2,792 tweets belonging to one of three stance categories: pro vaccine, anti
vaccine, or neutral.

  * •

Complaint This task aims to identify whether a tweet expresses a complaint,
which is defined as ‘a negative mismatch between reality and expectations in a
particular situation’ (e.g., customer complaints on Twitter) (Olshtain and
Weinbach, 1987). We use a dataset developed by Preoţiuc-Pietro et al. (2019)
consisting of 3,449 English tweets annotated with one of two categories, i.e.,
complaints or not complaints.

  * •

Bragging This task aims to classify whether a tweet is bragging or not
bragging. We evaluate on a dataset developed by Jin et al. (2022) which
contains 6,696 tweets labelled as either bragging or not bragging.

  * •

Hate Speech The task of hate speech detection aims to study anti-social
behaviours, e.g., racism and sexism in social media. We evaluate on a dataset
developed by Waseem and Hovy (2016) with a binary classification setup, i.e.,
offensive or non-offensive.

Round 1 | Basic
---|---
Bragging |  | Identify whether or not a tweet includes a bragging statement.
---
\+ Constraints + Text
Vaccine |  | Annotate a tweet into one of three stance categories: pro vaccine, anti vaccine, or neutral.
---
\+ Constraints + Text
Round 2 | Basic + T/L Desc
Bragging |  |  Basic Instruction \+ Bragging is a speech act which explicitly or implicitly attributes credit to the speaker for some
---
‘good’ (possession, accomplishment, skill, etc.) which is positively valued by
the speaker and the potential audience.
As such, bragging includes announcements of accomplishments, and explicit
positive evaluations of some aspect of self.
A bragging statement should clearly express what the author is bragging about
(i.e. the target of bragging).
\+ Constraints + Text
Vaccine |  |  Basic Instruction \+ Tweets that have been assigned to the class ‘pro vaccine’ express a positive opinion regarding the
---
vaccination. Tweets belonging to the ‘anti vaccine’ class express a negative
opinion towards COVID-19
vaccination. The ‘neutral’ class mainly includes news related to the
development of vaccines, tweets that do not express
a clear opinion, such as questions regarding the vaccine, informative tweets
concerning vaccination.
\+ Constraints + Text

Table 2: Prompt Examples.

##  3 Experimental Setup

###  3.1 Large Language Models

Our experiment is conducted based on two publicly accessible large language
models: GPT-3.5-turbo (GPT) and OpenAssistant-LLaMa (OA).

#### GPT-3.5-turbo

We perform experiments with GPT-3.5-turbo
111https://platform.openai.com/docs/models/gpt-3-5 which is an enhanced
version of the GPT-3 language model with instruction fine-tuning. GPT-3.5 can
be employed for a wide range of NLP tasks, including machine translation,
common sense reasoning, and question answering. We call the GPT-3.5 model via
the official OpenAI API.222https://platform.openai.com/docs/api-reference

#### OpenAssistant-LLaMA

We employ the OpenAssistant (OA) model developed by LAIONAI, which fine-tunes
the LLaMA (Touvron et al., 2023) 30B model using the OA dataset. Since LLaMA
is not open-source, LAIONAI could not release the weights for OA on
huggingface but released xor weights333We use the oasst-sft-7-llama-30b
version of the model. The xor weights can be found at:
https://huggingface.co/OpenAssistant/oasst-sft-7-llama-30b-xor are applied to
original LLaMA weights and check sum calculations performed to validate the
conversion. Running experiments locally was restricted due to hardware
constraints and as such 8-bit quantisation was applied via BitsAndBytes
Dettmers et al. (2021) at model load to decrease inference memory
requirements.

###  3.2 Baselines

We compare the zero-shot performance of LLMs with a weak baseline Logistic
Regression and a strong baseline BERT-large:

#### Logistic Regression

We represent the text using TF-IDF and consider tokens that appear more than 5
times.

#### Bert-large

We fine-tune Bert-large444https://huggingface.co/bert-large-uncased (Devlin et
al., 2019) by adding a linear classifier on top of the 24-layer transformer
blocks. The special token ‘[CLS]’ is used as the representation of each text.

###  3.3 Data Splits

For each benchmark, we initially split the dataset into training (80%) and
test (20%) sets using stratified random splits555To generate class-stratified
subsets, we employ a dataset split tool from https://scikit-
learn.org/stable/modules/generated/sklearn.model_selection. The training set
is used for supervised fine-tuning, and it is further divided into two
train/validation set (in a ratio of 3:1) for hyperparameter tuning (e.g.,
early stopping) purposes, respectively. Subsequently, we evaluate the
performance of the fine-tuned baselines and zero-shot LLMs on the test set
(20%).

| Complaint | Vaccine Stance | Bragging
---|---|---|---
Model | Accuracy | F1-macro | Accuracy | F1-macro | Accuracy | F1-macro
Logistic Regression | 81.4 | 79.7 | 72.8 | 73.1 | 88.6 | 58.8
BERT-large | 89.4 | 88.6 | 81.5 | 81.3 | 91.3 | 76.1
GPT Basic | 89.7 | 88.7 | 73.0 | 73.8 | 85.1 | 67.6
GPT T/L Desc | 89.0 | 88.0 | 73.3 | 73.7 | 84.9 | 67.4
GPT Memory Recall | 87.1 | 86.4 | 66.2 | 66.9 | - | -
OA Basic | 72.3 | 72.3 | 61.7 | 60.3 | 89.3 | 57.6
OA T/L Desc | 65.3 | 65.2 | 73.7 | 73.6 | 88.4 | 48.2
OA Memory Recall | 82.6 | 82.1 | 64.2 | 63.8 | - | -
| Rumor Stance | Sarcasm | Hata Speech
Model | Accuracy | F1-macro | Accuracy | F1-macro | Accuracy | F1-macro
Logistic Regression | 68.5 | 40.9 | 76.1 | 53.5 | 83.2 | 79.2
BERT-large | 73.2 | 48.2 | 78.9 | 58.4 | 84.5 | 81.2
GPT Basic | 49.4 | 33.4 | 67.3 | 62.1 | 75.5 | 72.4
GPT T/L Desc | 59.2 | 45.7 | 61.3 | 57.9 | 76.9 | 72.1
GPT Memory Recall | 40.2 | 30.9 | - | - | 71.7 | 69.6
OA Basic | 45.2 | 27.4 | 71.9 | 48.6 | 63.5 | 63.3
OA T/L Desc | 56.2 | 29.0 | 75.9 | 49.9 | 75.5 | 73.3
OA Memory Recall | 52.4 | 34.6 | - | - | 55.4 | 55.4
Table 3: LLMs zero-shot classification results across all prompt settings. All
datasets are evaluated with accuracy and macro-F1 scores. Blue highlighted
cells denote prompt settings where zero-shot LLMs beat the strong supervised
baseline (i.e., Bert-large fine-tuned on the training set). Bold text denotes
the best result per task.

###  3.4 Prompting Strategies

Following the prompting approaches described by Child et al. (2019); Ziems et
al. (2023), we develop prompts by (i) adding instructions after the context
(e.g., task description) and (ii) using constraints (e.g., ’Only reply with
Bragging’ or Not Bragging.’) at the end. We observe that using constraints can
effectively avoid cases of model uncertainty (e.g., ‘As an AI model, I cannot
answer this question.’) and guide models to generate the expected outputs.

For consistency, we use the same prompts for both GPT and OA. Two examples for
Round 1 and Round 2 are displayed in Table 2. To examine the zero-shot
predictive performance of LLMs, we design a battery of experiments using three
different prompting strategies.

#### Basic Instruction (Basic)

We only provide a basic instruction without including detailed task and label
descriptions. For example, for the bragging detection task, our prompt is:
‘Identify whether or not a tweet includes a bragging statement. + Constraints
+ Text’.

#### Task and Label Description (T/L Desc)

Building upon the Basic Instruction Round, we provide additional information
in the prompt by including task and label descriptions. Note that we use the
same label and task descriptions as mentioned in the original paper. The
format of prompt used for the Task and Label Description Round is: ‘Basic
Instruction + Task and Label Descriptions + Constraints + Text’.

#### Memory Recall (Recall)

We observe that both GPT and OA can recall papers published before September
2021 (prompts and responses see Table 5). Since arXiv papers are part of the
training corpus used by LLMs, we also include the title of the source paper in
the prompt when evaluating the zero-shot performance of LLMs. For example, we
include paper information by using this prompt: ‘Recall this paper [Paper
Title] + Basic Instruction + Constraints + Text’. For this round, we only
perform experiments on datasets published before September 2021.

#### Synonyms

LLMs trained with RLHF can generate different outputs when using prompts which
are semantically similar (e.g., synonyms). To test the generalizability of
LLMs, we substitute the names of each class with with words that have the same
or similar meaning. For example, we test the synonyms ’hateful’, ’toxic’, and
’abusive’) to replace the original category ‘offensive’.

| GPT | OA
---|---|---
Synonyms | Accuracy | F1-macro | Accuracy | F1-macro
Task 1 |
Complaint / not Complaint | 89.7 | 88.7 | 72.3 | 72.3
Grievance / not Grievance | 86.2 | 84.6 |  82.0 | 81.6
Criticism / not Criticism | 80.2 | 77.8 | 76.4 | 76.1
Dissatisfaction / no Dissatisfaction | 82.9 | 82.2 | 66.9 | 66.9
Task 2 |
Pro Vaccine / Anti Vaccine / Neutral | 73.0 | 73.8 | 61.7 | 60.3
In Favour of the Vaccine / Against the Vaccine / Neutral | 72.7 | 73.5 |  64.2 | 63.8
Positive Sentiment / Negative Sentiment / Neutral | 68.7 | 68.7 | 59.6 | 53.3
Task 3 |
Bragging / not Bragging | 85.1 | 67.6 | 89.3 | 57.6
Boasting / not Boasting | 82.7 | 65.1 | 68.7 | 55.1
Showing off / not Showing off | 78.7 | 63.0 | 62.9 | 52.6
Task 4 |
Support / Deny / Query / Comment | 49.4 | 33.4 | 45.2 | 27.4
Support / Dismiss / Questioning / Comment | 39.9 | 30.7 | 55.5 | 39.1
Task 5 |
Sarcasm / not Sarcasm | 67.3 | 62.1 | 71.9 | 48.6
Ironic / not Ironic |  74.4 | 66.0 | 55.7 | 52.5
Insincere / Sincere | 72.6 | 63.5 | 66.7 | 41.7
Disingenous / Genuine | 77.1 | 60.5 | 59.5 | 40.6
Satire / not Satire | 74.8 | 59.9 | 76.1 | 54.2
Task 6 |  |  |  |
Offensive / Non-offensive | 75.5 | 72.4 | 63.5 | 63.3
Toxic / not Toxic | 70.0 | 67.6 | 60.1 | 60.1
Abusive / not Abusive | 72.6 | 69.4 | 66.3 | 65.6
Hateful / not Hateful | 73.4 | 70.5 | 63.7 | 63.5
Table 4: LLMs zero-shot classification results using synonyms across all
tasks. Green highlights are the original class names. Blue highlighted cells
denote where synonyms prompt settings beat the original label. Bold text
denotes the best result per model per task.

###  3.5 Evaluation Metrics

We employ two evaluation metrics in this study: 1) Accuracy - this involves a
direct comparison between the model predictions and the ground truth label;
and 2) Macro-F1 scores are reported for situations where accuracy may not
provide an adequate representation of performance, particularly for certain
imbalanced datasets utilised in this paper, such as Bragging and Rumour
Stance.

###  3.6 Hyper-parameters

During initial explorations, we observed that using a higher temperature
(e.g., 0.8 for GPT-3.5 and 2 for OA) results in inadequate classification
performance (introduces more randomness to the model’s output). This suggests
that higher temperature settings cause the model outputs to be non-
reproducible. In this work, we use a low temperature (i.e.,
0.2)666https://platform.openai.com/docs/api-reference/chat/create for GPT-3.5
to make the model more focused and deterministic.

For OA, we follow the ‘precise hyper-parameter setup’777https://open-
assistant.io/dashboard indicated in the OpenAssistant web interface, where the
Temperature is 0.1, Top P is 0.95, Repetition Penalty is 1.2 and Top K is 50.
Our early exploratory studies showed that using low temperatures can stabilise
the output of the model to facilitate the reproducible results.

For Bert-large, we set the learning rate as 2e-5, the batch size as 16, and
the maximum sequence length as 256. We run all baseline models three times
with different random seeds and report average results. We fine-tune Bert-
large on an Nvidia RTX Titan GPU with 24GB memory and run OA on an Nvidia A100
GPU with 40GB memory. The inference rates of OA and GPT are approximately
1,200 and 3,000 samples per hour respectively.

##  4 Results

Table 3 displays the prediction results of all zero-shot LLMs for all rounds.
In general, we observe that supervised baselines still outperform LLMs on the
majority of prompt settings (4 out of 6 tasks). Furthermore, we observe that
GPT consistently outperforms OA across all prompt settings and tasks when
considering only the F1-macro measure. However, our results show that the
accuracy of OA is better than GPT on some imbalanced datasets, such as
’Bragging and Sarcasm.’ This may be due to OA defaulting to the neutral class
(labels without any specific speech act, such as ’Not Bragging and Not
Sarcastic’).

GPT achieves the best predictive performance on two speech act detection
downstream tasks, namely Complaint (89.7 accuracy and 88.7 F1-macro) and
Sarcasm (62.1 F1-macro). This suggests that LLMs can be employed as strong
baseline models for zero-shot classification tasks. When comparing the results
of T/L Desc and Memory Recall against Basic Instruction, it is observed that
using a more complex prompt (e.g., adding label and paper information) does
not necessarily improve model performance and may even introduce additional
noise, leading to a degradation in model performance.

For speech act detection tasks such as Complaint and Bragging, the accuracy of
LLMs exceeds 85%, indicating that LLMs can potentially be used for data
annotation to reduce the cost of human resources. Standard data annotation
tasks typically rely on two annotators in the first round, but one of them can
be replaced by LLMs. According to the annotation
details888https://github.com/sohampoddar26/covid-vax-stance/tree/main/dataset
of the vaccine stance task (Poddar et al., 2022), the agreement rate between
the two annotators is approximately 62%.

Table 4 shows all the zero-shot results of using synonyms across all tasks. We
observe that revising prompts with synonyms can substantially improve the
zero-shot performance of OA, except for the Bragging dataset (where 5 out of 6
tasks improved). It is worth noting that the Sarcasm dataset is the only one
where the prompt using original categories performs worse on both datasets.
This suggests that replacing original labels with synonyms allows the OA model
to better understand the task requirements. This may be due to the diversity
in the distribution of training examples used in the RLHF fine-tuning for both
GPT and OA. For example, OA model might be fine-tuned on corpus like: ‘[Text
including offensive languge] + [Category: Abusive]’. Therefore, we believe
that it is important to test similar words in place of the original labels
when designing instructions.

##  5 Related Work

Ziems et al. (2023) sets a roadmap for employing LLMs as data annotators by
establishing prompting best practices and an evaluation of the zero-shot
performance of 13 language models on 24 tasks in computational social
sciences. Our work is distinct from this piece as we evaluate a different set
of benchmarks and models and experiment with different prompt modifications
such as using synonyms for class labels and adding arXiv paper titles.

To evaluate the zero-shot performance of ChatGPT for text classification,
Kuzman et al. (2023) compares against a fine-tuned XLM-RoBERTa model for the
task of automatic genre classification in English and Slovenian. They show
that ChatGPT outperforms the baseline on unseen datasets and doesn’t drop
performance when provided with Slovenian examples.

Since our focus is primarily on out-of-the-box performance, we experiment with
simple alterations with the prompt. Other research, Arora et al. (2022) looks
at prompt aggregation as well as using LLMs to auto-generate prompts. We also
do not explore advanced methods such as chain-of-thought prompting, which
improves LM performance by encouraging it to output its intermediate reasoning
steps Wei et al. (2022b).

##  6 Conclusion

In this paper, we delve into the exploration of prompting strategies for the
application of Large Language Models (LLMs) in computational social science.
We carry out a range of controlled experiments to gauge the efficacy of
various prompt configurations across six publicly available datasets. Our
conclusions are summarised as follows:

  * •

Task-specific fine-tuned models generally tend to outperform LLMs in zero-shot
settings.

  * •

More detailed and complex prompts do not necessarily enhance classification
performance.

  * •

The selection of specific words or phrases as the class label can considerably
affect classification outcomes.

We argue that developing prompts for zero-shot classification presents a
significant challenge. We recommend testing different prompt configurations
before proceeding with experiments, while keeping in mind the time
constraints999https://platform.openai.com/docs/guides/rate-limits/overview and
financial costs associated with LLMs (see Table 6).

## Ethics Statement

Our work has received ethical approval from the Ethics Committee of our
university (Reference Number: 053640) and complies with the research policies
of Twitter. All datasets are obtained through the links provided in the
related papers or by requesting them directly from the authors. It is
important to note that we do not collect any new data from Twitter for this
work. Furthermore, we can confirm that the data has been fully anonymised
before being fed to the LLMs for model inference.

## References

  * Arora et al. (2022) Simran Arora, Avanika Narayan, Mayee F Chen, Laurel J Orr, Neel Guha, Kush Bhatia, Ines Chami, Frederic Sala, and Christopher Ré. 2022.  Ask me anything: A simple strategy for prompting language models.  _arXiv preprint arXiv:2210.02441_.
  * Child et al. (2019) Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. 2019.  Generating long sequences with sparse transformers.  _arXiv preprint arXiv:1904.10509_.
  * Christiano et al. (2017) Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. 2017.  Deep reinforcement learning from human preferences.  _Advances in neural information processing systems_ , 30.
  * Cotfas et al. (2021) Liviu-Adrian Cotfas, Camelia Delcea, Ioan Roxin, Corina Ioanăş, Dana Simona Gherai, and Federico Tajariol. 2021.  The longest month: analyzing covid-19 vaccination opinions dynamics from tweets in the month following the first vaccine announcement.  _Ieee Access_ , 9:33203–33223.
  * Derczynski et al. (2017) Leon Derczynski, Kalina Bontcheva, Maria Liakata, Rob Procter, Geraldine Wong Sak Hoi, and Arkaitz Zubiaga. 2017.  SemEval-2017 task 8: RumourEval: Determining rumour veracity and support for rumours.  In _Proceedings of the 11th International Workshop on Semantic Evaluation (SemEval-2017)_ , pages 69–76, Vancouver, Canada. Association for Computational Linguistics.
  * Dettmers et al. (2021) Tim Dettmers, Mike Lewis, Sam Shleifer, and Luke Zettlemoyer. 2021.  8-bit optimizers via block-wise quantization.  _arXiv preprint arXiv:2110.02861_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186.
  * Farha et al. (2022) Ibrahim Abu Farha, Silviu Vlad Oprea, Steven Wilson, and Walid Magdy. 2022.  Semeval-2022 task 6: isarcasmeval, intended sarcasm detection in english and arabic.  In _Proceedings of the 16th International Workshop on Semantic Evaluation (SemEval-2022)_ , pages 802–814.
  * Jin et al. (2022) Mali Jin, Daniel Preoţiuc-Pietro, A Doğruöz, and Nikolaos Aletras. 2022.  Automatic identification and classification of bragging in social media.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 3945–3959.
  * Köpf et al. (2023) Andreas Köpf, Yannic Kilcher, Dimitri von Rütte, Sotiris Anagnostidis, Zhi-Rui Tam, Keith Stevens, Abdullah Barhoum, Nguyen Minh Duc, Oliver Stanley, Richárd Nagyfi, et al. 2023.  Openassistant conversations–democratizing large language model alignment.  _arXiv preprint arXiv:2304.07327_.
  * Kuzman et al. (2023) Taja Kuzman, Nikola Ljubešić, and Igor Mozetič. 2023.  Chatgpt: Beginning of an end of manual annotation? use case of automatic genre identification.  _arXiv preprint arXiv:2303.03953_.
  * Olshtain and Weinbach (1987) Elite Olshtain and Liora Weinbach. 1987.  10\. complaints: A study of speech act behavior among native and non-native speakers of hebrew.  In _The pragmatic perspective_ , page 195. John Benjamins.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022\.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744.
  * Poddar et al. (2022) Soham Poddar, Mainack Mondal, Janardan Misra, Niloy Ganguly, and Saptarshi Ghosh. 2022.  Winds of change: Impact of covid-19 on vaccine-related opinions of twitter users.  In _Proceedings of the International AAAI Conference on Web and Social Media_ , volume 16, pages 782–793.
  * Preoţiuc-Pietro et al. (2019) Daniel Preoţiuc-Pietro, Mihaela Gaman, and Nikolaos Aletras. 2019.  Automatically identifying complaints in social media.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 5008–5019.
  * Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. 2020.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems_ , 33:3008–3021.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 2023.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_.
  * Waseem et al. (2017) Zeerak Waseem, Thomas Davidson, Dana Warmsley, and Ingmar Weber. 2017.  Understanding abuse: A typology of abusive language detection subtasks.  In _Proceedings of the First Workshop on Abusive Language Online_ , pages 78–84.
  * Waseem and Hovy (2016) Zeerak Waseem and Dirk Hovy. 2016.  Hateful symbols or hateful people? predictive features for hate speech detection on twitter.  In _Proceedings of the NAACL Student Research Workshop_ , pages 88–93, San Diego, California. Association for Computational Linguistics.
  * Wei et al. (2022a) Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. 2022a.  Emergent abilities of large language models.  _Transactions on Machine Learning Research_.
  * Wei et al. (2022b) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou. 2022b.  Chain of thought prompting elicits reasoning in large language models.  In _Advances in Neural Information Processing Systems_.
  * Ziems et al. (2023) Caleb Ziems, William Held, Omar Shaikh, Jiaao Chen, Zhehao Zhang, and Diyi Yang. 2023.  Can large language models transform computational social science?  _arXiv preprint arXiv:2305.03514_.
  * Zubiaga et al. (2018) Arkaitz Zubiaga, Ahmet Aker, Kalina Bontcheva, Maria Liakata, and Rob Procter. 2018\.  Detection and resolution of rumours in social media: A survey.  _ACM Computing Surveys (CSUR)_ , 51(2):1–36.

##  Appendix A Appendix

Prompt
---
Rumour Stance | Do you know this paper: SemEval-2017 Task 8: RumourEval: Determining rumour veracity and support for rumours?
Sarcasm | Do you know this paper: Semeval-2022 task 6: isarcasmeval, intended sarcasm detection in English and Arabic?
Reply
GPT |  | Yes, I’m familiar with the paper titled SemEval-2017 Task 8: RumourEval: Determining rumour veracity and support
---
for rumours. This paper is related to the SemEval-2017 workshop, specifically
Task 8, which focused on rumour detection
and veracity classification on social media platforms. Participants were
provided with a dataset containing rumours along
with associated tweets that either supported or denied the rumours. The task
involved classifying the veracity of the rumours
as true, false, or unverified, and also identifying the tweets that provided
support or denial for the rumours.
OA |  | Yes, I am aware of the paper titled SemEval-2017 Task 8: RumourEval: Determining rumour veracity and support for
---
rumours. This paper presents the results of the RumourEval task held as part
of the 2017 edition of the SEMEVAL
workshop. The task involved developing algorithms for determining the veracity
of rumors and identifying sources that
supported or refuted them using Twitter data.
GPT |  | I apologise for the confusion, but as an AI language model, my training only goes up until September 2021, and I do not
---
have access to specific details about SemEval-2022 or any subsequent tasks.
The last SemEval workshop I’m aware of is
SemEval-2021.
OA |  | Semeval-2022 Task 6: ISARCASMEVAL is a subtask focusing specifically on the identification of ironic and sarcastic
---
expressions in English and Arabic text. Irony and sarcasm are common forms of
expression found in both written and
spoken communication, but they pose significant challenges for automatic
sentiment analysis due to their subtle nature
and dependence on contextual cues.

Table 5: Ask LLMs if they can recall the original paper. | Round 1 | Round 2
---|---|---
Task | Tokens | USD | Tokens | USD
Rumour Stance | 35k / 51 | <0.1 | 82k / 119 | 0.2
Vaccine Stance | 31k / 127 | <0.1 | 86k / 45 | 0.2
Complaint | 23k / 33 | <0.1 | 62k / 91 | 0.1
Bragging | 52k / 76 | 0.1 | 96k / 140 | 0.2
Hate Speech | 62k / 90 | 0.1 | 94k 137 | 0.2
Sarcasm | 28k / 41 | <0.1 | 50k / 86 | 0.1
Table 6: The cost of running GPT-3.5 for each task.


procedurelinenumbering,codesize=

# Analysis and Improvements of the Sender Keys
Protocol for Group Messaging

David Balbás IMDEA Software Institute,
Universidad Politécnica de Madrid
Spain
<EMAIL_ADDRESS>Daniel Collins EPFL
Switzerland
<EMAIL_ADDRESS>Phillip Gajland Max Planck Institute for Security &
Privacy,
Ruhr-University Bochum
Germany
<EMAIL_ADDRESS>
###### Abstract

Messaging between two parties and in the group setting has enjoyed widespread
attention both in practice, and, more recently, from the cryptographic
community. One of the main challenges in the area is constructing secure (end-
to-end encrypted) and efficient messaging protocols for group conversations.
The popular messaging applications WhatsApp and Signal utilise a protocol in
which, instead of sharing a single group key, members have individual sender
keys, which are shared with all other group members. The Sender Keys protocol
is claimed to offer forward security guarantees. However, despite its broad
adoption in practice, it has never been studied formally in the cryptographic
literature.

In this paper we present the first analysis of the Sender Keys protocol along
with some prospective improvements. To this end, we introduce a new
cryptographic primitive, develop a game-based security model, present a
security analysis in the passive and active settings, and propose several
improvements to the protocol.

###### Index Terms:

Secure Messaging, Group Messaging, Signal, WhatsApp, Sender Keys.

##  I Introduction

Messaging applications such as WhatsApp, Facebook Messenger, Signal and
Telegram have enjoyed widespread adoption and form an integral part of
communications for billions of people. All of the aforementioned applications
rely, to a varying degree, on cryptography to provide diverse forms of
authenticity and secrecy.

Among end-to-end encrypted messaging solutions (this excludes Telegram and
Facebook Messenger by default, among others), there exist diverse
cryptographic solutions. For two-party messaging, Signal’s Double Ratchet
Protocol [1] is the most popular choice in practice, and many solutions also
exist in the cryptographic literature [2, 3, 4, 5, 6]. For group messaging,
the naive solution, as used by Signal Messenger for small groups, of adopting
Double Ratchet sessions among every pair of group members does not scale well.
Thus, recent work such as the Messaging Layer Security (MLS) standardization
effort [7] aims to construct secure group messaging protocols where the
complexity of group operations (adding and removing members, updating key
material) is sublinear in the group size [8, 9, 10, 11, 12].

Nevertheless, the popular messaging applications WhatsApp and Signal (for
large groups) use a protocol for group messaging [13, 14] that does not
involve sharing a unique group key that evolves over time. This differs from
MLS, and from the group key agreement abstraction followed there [9, 10, 11].
This protocol, called Sender Keys, has not been formally studied in the
literature despite its widespread adoption.

###  I-A Secure Group Messaging

Two standard security notions prevail in the literature both for two-party and
group messaging. The first is _forward security_ (FS), which protects the
confidentiality of past messages in the event of a key exposure and can be
achieved using just symmetric cryptography (for example by iteratively hashing
symmetric keys). The second is _post-compromise security_ (PCS), which ensures
that security can be restored after a key exposure in certain adversarial
settings [15], typically when the adversary is passive for some period of
time. FS- and PCS-oriented key evolution mechanisms are commonly known as
_ratcheting_.

Both properties apply to the confidentiality and authenticity of sent messages
and can be captured formally in a security game. There exist different
formalisations of security in the literature, but most of them model an
adversarial Delivery Service (DS), the entity responsible for delivering
messages between participants via the communication channel. The adversary
(modelling the DS) can act as an eavesdropper (with extended yet limited
capabilities) as in [9], as a semi-active adversary which can schedule
messages arbitrarily [10], or as an active adversary that can inject messages
[11, 16]. In many protocols, including Sender Keys and MLS, the DS relies
mainly on some centralized infrastructure (the _central server_ hereafter).

Some messaging protocols also require additional infrastructure to deal with
user authentication or security. This may include Public Key Infrastructure
(PKI), or, in the case of Sender Keys, secure two-party messaging channels
established between each pair of users. Achieving security in multiple groups
simultaneously is outside the scope of this work, and requires additional
precautions detailed in [17].

###  I-B Sender Keys

In a Sender Keys group $\bm{G}$, every user $\pcalgostyle{ID}\in\bm{G}$ owns a
so-called _sender key_ which is shared with all group members. A sender key is
a tuple $\pcalgostyle{send\pcmathhyphen
k}=(\pcalgostyle{spk},\pcalgostyle{ck})$, where $\pcalgostyle{spk}$ is a
public signature key (with a private counterpart $\pcalgostyle{ssk}$), and
$\pcalgostyle{ck}$ is a symmetric _chain key_. Every time a user
$\pcalgostyle{ID}$ sends a message $m$ to the group, $\pcalgostyle{ID}$
encrypts $m$ using a _message key_ $\pcalgostyle{mk}$ that is
deterministically derived from its chain key $\pcalgostyle{ck}$. Upon message
reception, group members also derive $\pcalgostyle{mk}$ to decrypt the
message. Messages are authenticated by appending the sender’s signature.

Forward security is provided by using a fresh message key for every message;
every time a message is sent, the chain key is hashed forward using a key
derivation function. In other words, chain keys are symmetrically ratcheted.

The protocol also requires that there exist confidential and authenticated
two-party communication channels between every pair of users. These are used
for sharing sender keys in the event of parties being added or removed from
the group.

###  I-C Contributions

The main scientific contributions of our paper are the following:

  * •

We introduce a new cryptographic primitive, Group Messenger
($\pcalgostyle{GM}$), which is suitable for messaging protocols like Sender
Keys that are not necessarily based on group key agreement.

  * •

We formally describe Sender Keys, based on a code analysis of Signal’s source
code [14], and WhatsApp’s security white paper [13].

  * •

We present a security model for (single-group) Group Messenger. We do so via a
security game that considers an active adversary who can interact with several
oracles. The game is parametrised by a cleanness predicate that captures
forward-secure group messaging.

  * •

We carry out a security analysis for passive and active adversaries and detail
prospective fixes and improvements to the Sender Keys protocol.

We note that this is a preliminary and shortened version of our work.

##  II Primitive Syntax

Unless otherwise stated, all algorithms are probabilistic, and
$(x_{1},\dots)\mathrel{\vbox{\offinterlineskip\halign{ \hfil#\hfil\cr\hskip
1.00006pt$\scriptscriptstyle\$$\cr$\leftarrow$\cr}}}\adv(y_{1},\dots)$ is used
to denote that $\adv$ returns $(x_{1},\dots)$ when run on input
$(y_{1},\dots)$. Blank values are represented by $\bot$. We denote the
security parameter by $\secpar$ and its unary representation by $\secparam$.
We also define the state $\gamma$ of a user $\pcalgostyle{ID}$ as the data
required by $\pcalgostyle{ID}$ for protocol execution, including message
records, group-related variables, and cryptographic material.

We introduce a cryptographic primitive that we call _Group Messenger_
$\pcalgostyle{GM}\coloneqq(\pcalgostyle{Init},\pcalgostyle{Send},\pcalgostyle{Recv},\pcalgostyle{Exec},\pcalgostyle{Proc})$,
similar to other group messaging abstractions such as Continuous Group Key
Agreement (CGKA) [9]. In contrast to CGKA, our primitive does not model key
agreement (as this does not neatly capture the Sender Keys protocol), but
rather sending and receiving messages. The syntax is as follows.

  * •

$\gamma\mathrel{\vbox{\offinterlineskip\halign{ \hfil#\hfil\cr\hskip
1.00006pt$\scriptscriptstyle\$$\cr$\leftarrow$\cr}}}\pcalgostyle{Init}(\secparam,\pcalgostyle{ID})$:
Given the security parameter $\secparam$ and a user identity
$\pcalgostyle{ID}$, the probabilistic initialisation algorithm returns an
initial state $\gamma$.

  * •

$(C,\gamma^{\prime})\mathrel{\vbox{\offinterlineskip\halign{
\hfil#\hfil\cr\hskip
1.00006pt$\scriptscriptstyle\$$\cr$\leftarrow$\cr}}}\pcalgostyle{Send}(m,\gamma)$:
Given a message $m$, and a state $\gamma$, the probabilistic sending algorithm
returns a ciphertext $C$ and a new state $\gamma^{\prime}$.

  * •

$(m,\gamma^{\prime})\leftarrow\pcalgostyle{Recv}(C,\gamma)$: Given a
ciphertext $C$, and a state $\gamma$, the deterministic receiving algorithm
returns a message $m$ and a new state $\gamma^{\prime}$.

  * •

$(C,\gamma^{\prime})\mathrel{\vbox{\offinterlineskip\halign{
\hfil#\hfil\cr\hskip
1.00006pt$\scriptscriptstyle\$$\cr$\leftarrow$\cr}}}\pcalgostyle{Exec}(\texttt{cmd},\bm{IDs},\gamma)$:
Given a command $\texttt{cmd}\in\\{\texttt{crt},\texttt{add},\texttt{rem}\\}$,
a list of user identities $\bm{IDs}$, and a state $\gamma$, the probabilistic
execution algorithm returns a ciphertext $C$ and a new state
$\gamma^{\prime}$.

  * •

$\gamma^{\prime}\leftarrow\pcalgostyle{Proc}(C,\gamma)$: Given a ciphertext
$C$, and a state $\gamma$, the deterministic processing algorithm returns a
new state $\gamma^{\prime}$.

Note that there are separate algorithms for sending / receiving application
messages and for executing / processing changes to the group. Furthermore,
should two-party protocols be required under the hood to implement the group
primitive (this is not the case for CGKAs such as TreeKEM [9]), then these are
outside the scope of this definition.

##  III Protocol Description

In this section, we introduce a formal description of the Sender Keys protocol
in accordance with our Group Messenger syntax.

###  III-A Protocol Setup

####  III-A1 Central server

The Delivery Service (DS) relies on a central server which provides total
ordering of messages and authenticates users initially (i.e. it acts as a
PKI). In practice, the DS is also responsible for managing two-party channels.

####  III-A2 Two-party channels

The protocol assumes that there exist authenticated and secure two-party
communication channels (for example using Signal’s Double Ratchet protocol [1]
as done in WhatsApp [13]) between every pair of protocol users. This
assumption can be realized via the Delivery Service and asynchronous, PKI-
aided key-exchange mechanisms such as X3DH [18].

####  III-A3 Primitives

The protocol uses standardised [19, 20] underlying cryptographic primitives:

  * •

Two different Key Derivation Functions (KDF)
$H_{1},H_{2}:\bin^{\secpar}\to\bin^{\secpar}$. These are used to derive
message keys $\pcalgostyle{mk}$ and chain keys $\pcalgostyle{ck}$,
respectively.

  * •

A symmetric encryption scheme $(\enc,\dec)$.

  * •

A digital signature scheme $(\pcalgostyle{Gen},\sig,\pcalgostyle{Ver})$.

In Signal’s implementation of Sender Keys [14], the KDFs are instantiated as
$H_{1}(m)\coloneqq\mathsf{HMAC}(\texttt{0x01},m)$ and
$H_{2}(m)\coloneqq\mathsf{HMAC}(\texttt{0x02},m)$. We note that in Signal’s
two-party sessions signatures are not used. Instead, messages are
authenticated by computing a MAC based on a function of the message key.

In WhatsApp [13], the $\mathsf{HMAC}$ used for the KDF is HMAC-SHA256, the
symmetric encryption scheme is AES-256 in CBC mode, and the signature scheme
is ECDSA with Curve25519.

###  III-B State

The state $\gamma$ of a user $\pcalgostyle{ID}$ contains a sender key
$\pcalgostyle{send\pcmathhyphen
k}\coloneqq(\pcalgostyle{spk},\pcalgostyle{ck})$, where $\pcalgostyle{spk}$
denotes the the signature public key and $\pcalgostyle{ck}$ the chain key, as
well as a secret signature key $\pcalgostyle{ssk}$, each belonging to
$\pcalgostyle{ID}$. The state also maintains a list of current group members
$\bm{G}$. Additionally, for each user $\pcalgostyle{ID}\in\bm{G}$ the sender
key $\pcalgostyle{send\pcmathhyphen k}_{\pcalgostyle{ID}}$, a list of skipped
message keys $\\{\pcalgostyle{mk}_{\pcalgostyle{ID}}^{i},\dots\\}$, used for
out-of-order delivery, and the counter $i$ are stored. If $\pcalgostyle{ID}$
leaks its state, we say that it suffered a _state compromise_.

###  III-C Algorithms

We describe the Sender Keys protocol according to our Group Messenger
primitive defined in Section II. The description follows Signal’s reference
implementation [14] regarding sender key ratcheting as well as message
encryption and decryption. The details of the $\pcalgostyle{Exec}$ and
$\pcalgostyle{Recv}$ algorithms are inferred from [13], but we cannot assert
that our interpretation is entirely faithful to WhatsApp’s implementation. A
simplified example of a 3-message conversation is shown in Figure 1.

####  III-C1 State initialization

The $\pcalgostyle{Init}$ algorithm initializes the state variables of users;
in practice this is done at install time.

####  III-C2 Group creation

The creation of a group is carried out via the
$\pcalgostyle{Exec}(\texttt{crt},\bm{G},\gamma)$ algorithm which takes a list
of prospective members
$\bm{G}\coloneqq\\{\pcalgostyle{ID}_{1},\ldots,\pcalgostyle{ID}_{|\bm{G}|}\\}$
as input. All parties are assumed to have pre-established two-party
communication sessions. The group creator $\gamma.\pcalgostyle{ME}$ generates
a chain key $\pcalgostyle{ck}\mathrel{\vbox{\offinterlineskip\halign{
\hfil#\hfil\cr\hskip
1.00006pt$\scriptscriptstyle\$$\cr$\leftarrow$\cr}}}\bin^{\secpar}$ and a
signature key pair
$(\gamma.\pcalgostyle{spk},\gamma.\pcalgostyle{ssk})\mathrel{\vbox{\offinterlineskip\halign{
\hfil#\hfil\cr\hskip
1.00006pt$\scriptscriptstyle\$$\cr$\leftarrow$\cr}}}\pcalgostyle{Gen}(\secparam)$.
Then, it sends its sender key $\gamma.\pcalgostyle{send\pcmathhyphen
k}=(\gamma.\pcalgostyle{spk},\pcalgostyle{ck})$ to each
$\pcalgostyle{ID}\in\bm{G}$ individually via their secure two-party channel.

####  III-C3 Message sending

To send the $i$th message $m_{i}$, a user $\gamma.\pcalgostyle{ME}$ calls the
$\pcalgostyle{Send}(m_{i},\gamma)$ algorithm which does the following:

  * •

Derive a new message key $\pcalgostyle{mk}$ from the symmetric part of its
sender key (i.e. the chain key) as
$\pcalgostyle{mk}^{i}_{\pcalgostyle}{ME}\leftarrow
H_{1}(\pcalgostyle{ck}^{i}_{\pcalgostyle}{ME})$.

  * •

Encrypt the message $m_{i}$ as $c_{i}\mathrel{\vbox{\offinterlineskip\halign{
\hfil#\hfil\cr\hskip
1.00006pt$\scriptscriptstyle\$$\cr$\leftarrow$\cr}}}\enc(\pcalgostyle{mk}^{i}_{\pcalgostyle}{ME},m_{i})$.

  * •

Ratchet the chain key $\pcalgostyle{ck}$111Note that this practice is safer
(better FS) than first evolving the chain key and then deriving a message key,
since it allows for the immediate deletion of the chain key used to derive the
message key. as $\pcalgostyle{ck}_{\pcalgostyle}{ME}^{i+1}\leftarrow
H_{2}(\pcalgostyle{ck}^{i}_{\pcalgostyle}{ME})$.

  * •

Jointly sign the ciphertext $c_{i}$, the message index $i$ and the sender’s
identity $\pcalgostyle{ME}$ as
$\sigma_{i}\mathrel{\vbox{\offinterlineskip\halign{ \hfil#\hfil\cr\hskip
1.00006pt$\scriptscriptstyle\$$\cr$\leftarrow$\cr}}}\sig(\pcalgostyle{ssk},(c_{i},i,\pcalgostyle{ME}))$

  * •

Send $C\coloneqq(c_{i},i,\pcalgostyle{ME},\sigma_{i})$ to all group members
via the DS.

If $\gamma.\pcalgostyle{send\pcmathhyphen k}=\bot$, then
$\gamma.\pcalgostyle{ME}$ must first generate a fresh sender key and
distribute it as in the group creation. This occurs every time a member sends
their first message after entering the group or after a member removal. We
emphasise that ciphertexts are not sent over the preexisting two-party
channels that are used to communicate sender keys, but rather over the network
(i.e., via the Delivery Service) itself.

####  III-C4 Message reception

Upon reception of a message $C=(c_{i},i,\pcalgostyle{ID},\sigma_{i})$, the
receiver calls $\pcalgostyle{Recv}(C,\gamma)$. First, $\pcalgostyle{Recv}$
verifies $\pcalgostyle{ID}$ and the signature as
$\pcalgostyle{Ver}(\pcalgostyle{send\pcmathhyphen
k}[\pcalgostyle{ID}].\pcalgostyle{spk},\sigma_{i},(c_{i},i,\pcalgostyle{ID}))$
(note that if $\pcalgostyle{send\pcmathhyphen k}[\pcalgostyle{ID}]=\bot$, the
receiver must wait until a new sender key is sent by $\pcalgostyle{ID}$). If
the check passes, then the algorithm proceeds as follows:

  * •

If $\pcalgostyle{send\pcmathhyphen k}[\pcalgostyle{ID}].\pcalgostyle{ck}$ is
at iteration $i$:

derive $\pcalgostyle{mk}_{i}\leftarrow H_{1}(\pcalgostyle{send\pcmathhyphen
k}[\pcalgostyle{ID}.\pcalgostyle{ck}])$,

decrypt $c_{i}$ as $m_{i}\leftarrow\dec(\pcalgostyle{mk}_{i},c_{i})$ and erase
$\pcalgostyle{mk}_{i}$,

and refresh $\pcalgostyle{send\pcmathhyphen
k}[\pcalgostyle{ID}.\pcalgostyle{ck}]\leftarrow
H_{2}(\pcalgostyle{send\pcmathhyphen k}[\pcalgostyle{ID}.\pcalgostyle{ck}])$.

  * •

If $\pcalgostyle{send\pcmathhyphen k}[\pcalgostyle{ID}].\pcalgostyle{ck}$ is
at iteration $j<i$, refresh the chain key $i-j$ times as
$\pcalgostyle{send\pcmathhyphen
k}[\pcalgostyle{ID}.\pcalgostyle{ck}]\leftarrow
H_{2}(\pcalgostyle{send\pcmathhyphen k}[\pcalgostyle{ID}.\pcalgostyle{ck}])$
while storing message keys $\pcalgostyle{mk}_{j},\ldots\pcalgostyle{mk}_{i-1}$
(up to $N_{\mathsf{max}}$ keys). Then, obtain $\pcalgostyle{mk}_{i}$, decrypt
$c_{i}$, and erase $\pcalgostyle{mk}_{i}$.

  * •

If $\pcalgostyle{send\pcmathhyphen k}[\pcalgostyle{ID}].\pcalgostyle{ck}$ is
at iteration $j>i$, search for a stored $\pcalgostyle{mk}_{j}$, attempt to
decrypt $c_{i}$, and erase $\pcalgostyle{mk}_{j}$. If unsuccessful, output
$\bot$.

####  III-C5 Membership changes

To add a new user $\pcalgostyle{ID}$ to the group, a member calls
$\pcalgostyle{Exec}(\texttt{add},\\{\pcalgostyle{ID}\\},\gamma)$. This
produces a notification message $T$ sent to all group members including
$\pcalgostyle{ID}$. As mentioned earlier, $\pcalgostyle{ID}$ only generates
and sends its own sender key when they send their first message.
$\pcalgostyle{ID}$ will receive the sender key of every other member
$\pcalgostyle{ID}^{\prime}$ when they speak in the group for the first time
after $\pcalgostyle{ID}$ joins. This is sent over the two-party channel of
$\pcalgostyle{ID}$ and $\pcalgostyle{ID}^{\prime}$.

To remove a user $\pcalgostyle{ID}$ from the group, a member calls
$\pcalgostyle{Exec}(\texttt{rem},\\{\pcalgostyle{ID}\\},\gamma)$ and sends the
notification $T$ to all members.

####  III-C6 Message processing

Group changes are processed via $\pcalgostyle{Proc}(T,\gamma)$. If a user
$\pcalgostyle{ID}$ is added, $\gamma.\pcalgostyle{ME}$ simply updates the list
of group members $\gamma.G$, and sends $\pcalgostyle{ID}$ his own sender key
via the two-party channel when he speaks again in the group. If
$\pcalgostyle{ID}$ is removed, $\gamma.\pcalgostyle{ME}$ deletes all sender
keys, including his own. In this scenario, the group “starts over", namely all
members must generate and send a new sender key (i.e. a new signature key pair
and symmetric key) to the members.

[boxed, space = 0.5em] [codesize=]
A: (ck^i_A,ssk_A,spk_A, B: (ck^j_B,ssk_B,spk_B,
ck_B^j,spk_B) ck_A^i,spk_A)[dotted]A sends $m_{i}$
$\pcalgostyle{mk}^{i}_{A}\leftarrow H_{1}(\pcalgostyle{ck}^{i}_{A})$
c_i  $\scriptscriptstyle\$$ $\leftarrow$ (mk^i_A, m_i) *[1.4cm](c_i, i,A,σ_i)
$\mathbf{assert}$ Ver(spk_A,σ_i)=1
$\pcalgostyle{ck}^{i+1}_{A}\leftarrow H_{2}(\pcalgostyle{ck}^{i}_{A})$
$\pcalgostyle{mk}^{i}_{A}\leftarrow H_{1}(\pcalgostyle{ck}^{i}_{A})$
σ_i  $\scriptscriptstyle\$$ $\leftarrow$ (ssk_A, (c_i, i, A)) m_i ←(mk^i_A,
c_i)
$\pcalgostyle{ck}^{i+1}_{A}\leftarrow H_{2}(\pcalgostyle{ck}^{i}_{A})$
[dotted]A sends $m_{i+1}$ $\pcalgostyle{mk}^{i+1}_{A}\leftarrow
H_{1}(\pcalgostyle{ck}^{i+1}_{A})$
c_i+1  $\scriptscriptstyle\$$ $\leftarrow$ (mk^i+1_A, m_i+1)
*[1.4cm](c_i+1,i+1,
A,σ_i+1) $\mathbf{assert}$ Ver(spk_A,σ_i+1)=1
$\pcalgostyle{ck}^{i+2}_{A}\leftarrow H_{2}(\pcalgostyle{ck}^{i+1}_{A})$
$\pcalgostyle{mk}^{i+1}_{A}\leftarrow H_{1}(\pcalgostyle{ck}_{A})$
σ_i+1  $\scriptscriptstyle\$$ $\leftarrow$ (ssk_A,
(c_i+1,i+1, A)) m_i+1 ←(mk^i+1_A, c_i+1)
$\pcalgostyle{ck}^{i+2}_{A}\leftarrow H_{2}(\pcalgostyle{ck}^{i+1}_{A})$
[dotted]B sends $m_{j}$ $\pcalgostyle{mk}^{j}_{B}\leftarrow
H_{1}(\pcalgostyle{ck}^{j}_{B})$
$\mathbf{assert}$ Ver(spk_B,σ_j)=1 *[1.4cm](c_j, j,B,σ_j) c_j
$\scriptscriptstyle\$$ $\leftarrow$ (mk^j_B, m_j)
$\pcalgostyle{mk}^{j}_{B}\leftarrow H_{1}(\pcalgostyle{ck}^{j}_{B})$
$\pcalgostyle{ck}^{j+1}_{B}\leftarrow H_{2}(\pcalgostyle{ck}^{j}_{B})$
m_j ←(mk^j_B, c_j) σ_j  $\scriptscriptstyle\$$ $\leftarrow$ (ssk_B, (c_j, j,
B))
$\pcalgostyle{ck}^{j+1}_{B}\leftarrow H_{2}(\pcalgostyle{ck}^{j}_{B})$

Figure 1: Sending/receiving messages between two group members for a three-
message (in-order) conversation. Ephemeral message keys $\pcalgostyle{mk}$ are
deleted immediately after use. A’s initial sender key is
$(\pcalgostyle{ck}^{i}_{A},\pcalgostyle{ssk}_{A})$ and B’s initial sender key
is $(\pcalgostyle{ck}^{j}_{B},\pcalgostyle{ssk}_{B})$.

##  IV Security Model

We propose a model of security for our Group Messenger primitive that captures
the security suitable for an authenticated and forward-secure group messaging
scheme. We introduce a game played between a probabilistic polynomial time
($\ppt$) adversary $\adv$ and a challenger.

###  IV-A Game Description

At the beginning of the game, a bit $b$ is uniformly sampled which
parametrises the game. To win, the adversary either has to guess $b$ or carry
out a successful forgery in a _clean_ protocol run. The game is parameterised
by a _cleanness_ predicate (sometimes safety [9] predicate) that captures the
exact security of the protocol, namely the authenticity and confidentiality of
group messages.

In this work, we assume that the two-party communication channels used for
sending sender keys are perfectly secure; i.e., always confidential and
authenticated. This assumption is not easily met in practice, but allows us to
capture the essence of Sender Keys alone.

For simplicity, the game starts with a pre-established group $\bm{G}$ where
every member $\pcalgostyle{ID}\in\bm{G}$ already has everyone’s honestly
generated sender key. Then, $\adv$ can interact with several oracles:

  * •

$\mathcal{O}^{\mathsf{Challenge}}(\pcalgostyle{ID},m_{0},m_{1})$. The
adversary receives a ciphertext $C_{b}$ corresponding to $\pcalgostyle{ID}$
sending $m_{b}$, i.e., the output of
$C_{b}\leftarrow\pcalgostyle{Send}(m_{b},\gamma_{\pcalgostyle}{ID})$.

  * •

$\mathcal{O}^{\mathsf{Send}}(\pcalgostyle{ID},m)$. $\pcalgostyle{ID}$ sends an
application-level message $m$ using the $\pcalgostyle{Send}$ algorithm,
producing a ciphertext $C$.

  * •

$\mathcal{O}^{\mathsf{Receive}}(\pcalgostyle{ID},\pcalgostyle{ID}^{\prime},C)$.
$\pcalgostyle{ID}$ calls $\pcalgostyle{Recv}$ on an application-level
ciphertext $C$ claimed to be from user $\pcalgostyle{ID}^{\prime}$. If $C$ has
not been generated honestly via the
$\mathcal{O}^{\mathsf{Send}}(\pcalgostyle{ID},m)$ oracle and receiving is
successful, $b$ is leaked to $\adv$.

  * •

$\mathcal{O}^{\mathsf{Add}}(\pcalgostyle{ID},\pcalgostyle{ID}^{\prime})$.
$\pcalgostyle{ID}$ adds $\pcalgostyle{ID}^{\prime}$ to the group via
$\pcalgostyle{Exec}$, generating a control message $T$.

  * •

$\mathcal{O}^{\mathsf{Remove}}(\pcalgostyle{ID},\pcalgostyle{ID}^{\prime})$.
$\pcalgostyle{ID}$ removes $\pcalgostyle{ID}^{\prime}$ from the group via
$\pcalgostyle{Exec}$, generating a control message $T$.

  * •

$\mathcal{O}^{\mathsf{Deliver}}(\pcalgostyle{ID},T)$. A control message $T$ is
delivered to $\pcalgostyle{ID}$ who calls $\pcalgostyle{Proc}$.

  * •

$\mathcal{O}^{\mathsf{Expose}}(\pcalgostyle{ID})$. The current state $\gamma$
of $\pcalgostyle{ID}$ leaks to $\adv$.

  * •

$\mathcal{O}^{\mathsf{ExpMK}}(\pcalgostyle{ID},i)$. The $i$-th message key
$\pcalgostyle{mk}$ of $\pcalgostyle{ID}$ leaks to $\adv$. No message encrypted
under this key can be challenged (neither before nor after exposure).

After $q$ oracle queries, the adversary outputs a guess $b^{\prime}$ of $b$.
Note that $\adv$ can win the game either by guessing a challenge correctly or
by injecting a forged message via $\mathcal{O}^{\mathsf{Receive}}$
successfully.

###  IV-B Cleanness

For the particular case of Sender Keys, we describe the cleanness predicate
which defines the following conditions for a valid game:

  * •

We define the event $\mathsf{refresh}(\pcalgostyle{ID})$ that occurs when: 1)
some member has been removed from the group, and 2) member $\pcalgostyle{ID}$
processes this change (note the lack of a PCS update option).

  * •

After exposing _any_ user $\pcalgostyle{ID}$, all adversarial calls to
$\mathcal{O}^{\mathsf{Challenge}}$ on future messages are disallowed until
$\mathsf{refresh}(\pcalgostyle{ID})$ occurs for _every_
$\pcalgostyle{ID}\in\bm{G}$. This extends to all challenges on skipped
messages (out-of-order) that $\pcalgostyle{ID}$ has not received at exposure
time.

  * •

After exposing _a specific_ user $\pcalgostyle{ID}^{\prime}$, $\adv$ cannot
win the game by impersonating $\pcalgostyle{ID}^{\prime}$ via
$\mathcal{O}^{\mathsf{Receive}}(\pcalgostyle{ID},\pcalgostyle{ID}^{\prime},C)$
for a forgery $C$ until a new $\mathsf{refresh}(\pcalgostyle{ID})$ event
occurs.

We remark that our security notion is adaptive insofar as users can adaptively
expose users. Under our cleanness predicate, we consider limited injection
queries, i.e., partially active security. Our modelling further assumes that
the underlying two-party channels are perfectly secure, and thus we leave it
as important future work to examine security where, e.g., state exposures on
the underlying channels are allowed and the consequent security guarantees are
captured.

##  V Security

We claim that Sender Keys, as described in Section III, is secure with respect
to our security model. However, the security captured by our cleanness
predicate is sub-optimal, in the sense that forward security can be
strengthened for authentication, as we introduce in Section V-C. Here we
introduce a security analysis, but leave a security proof and more accurate
modelling for future work.

###  V-A Passive adversaries

For a (semi-)passive adversary which does not attempt to inject messages via
$\mathcal{O}^{\mathsf{Receive}}$ (but can still schedule messages
arbitrarily), we claim that Sender Keys is secure with respect to the
cleanness predicate, given that the symmetric encryption scheme is IND-CPA
secure. Towards proving this:

  * •

If the $\pcalgostyle{KDF}$ is a one-way function, message keys
$\pcalgostyle{mk}_{i}$ can be exposed independently; the compromise of a
message key never affects the confidentiality of other keys or messages.
Hence, giving adversarial access to
$\mathcal{O}^{\mathsf{ExpMK}}(\pcalgostyle{ID},i)$ does not impact the
cleanness predicate.

  * •

Also assuming one-wayness of the $\pcalgostyle{KDF}$, forward secrecy holds
trivially except for out-of-order messages.

  * •

Assuming that the two-party channels are secure, all users recover from state
exposure via $\mathcal{O}^{\mathsf{Expose}}(\pcalgostyle{ID})$ after a removal
is made effective. Note that, outside our model, security of the two-party
channels may also degrade after a state exposure, leaving room for further
attacks.

###  V-B Single- vs multi-key

In a Sender Keys group, each user is associated with a different symmetric key
and thus the state comprises $O(n)$ secret material at all times. Since users
encrypt and then hash forward using their own key when sending each message,
users can safely send messages concurrently and with some inter-member message
reordering.

For large groups, however, this scaling behaviour may represent a bottleneck.
Consequently, one can envision trade-offs between the amount of concurrency
supported and the amount of secret material required to be stored at a given
point a time. The other extreme of the spectrum would be when all users
maintain the _same_ single symmetric chain. In situations where users are not
expected to concurrently send messages this allows the secret state size to
reduce to $O(1)$ without degrading security. To deal with concurrency in this
setting, a central server which rejects all but the first (for example)
message and requests re-transmission for other users could then be employed.

In MLS, a new group secret (chosen by a single user) is established each
epoch, from which point all $O(n)$ application keys are derived for a given
point in time; MLS additionally supports out-of-order message delivery within
a given epoch. In Sender Keys, each user chooses their own key; thus, the
security of ciphertexts in the presence of a passive adversary is contingent
upon users initially sampling their key with enough entropy.

###  V-C Active attacks

In an active adversary scenario, the security of Sender Keys is sub-optimal.
In particular, we note two issues. First, consider a simple group
$\bm{G}=\\{\pcalgostyle{ID}_{1},\pcalgostyle{ID}_{2}\\}$ and the following
sequence of oracle queries:

  * •

$q_{1}=\mathcal{O}^{\mathsf{Send}}(\pcalgostyle{ID}_{1},m)$ which generates
the $i$-th message $C$ encrypted under $\pcalgostyle{mk}$ and signed under
$\pcalgostyle{ssk}_{1}$.

  * •

$q_{2}=\mathcal{O}^{\mathsf{Expose}}(\pcalgostyle{ID}_{1})$, where $\adv$
obtains $\pcalgostyle{ssk}_{1}$, but not $\pcalgostyle{mk}$.

  * •

$q_{3}=\mathcal{O}^{\mathsf{ExpMK}}(\pcalgostyle{ID}_{1},i)$, leaking
$\pcalgostyle{mk}$.

  * •

$\adv$ crafts $c^{\prime}=Enc(m^{\prime},\pcalgostyle{mk})$, signs it under
$\pcalgostyle{ssk}_{1}$ and forges a $C^{\prime}$.

  * •

$q_{4}=\mathcal{O}^{\mathsf{Deliver}}(\pcalgostyle{ID}_{2},C^{\prime})$, as
the $i$-th message.

Note that $q_{4}$ is a forbidden query by our cleanness predicate in Section
IV-B. $q_{4}$ attempts to inject a message that corresponds to key material
utilized _before_ the state exposure, hence one can envision stronger forward
security where queries like $q_{4}$ are allowed. In this case, the Sender Keys
adversary would win the game. We describe how to achieve such stronger
security in Section V-D by strengthening signatures.

Technically, the query $q_{3}$ can be replaced by
$\mathcal{O}^{\mathsf{Expose}}(\pcalgostyle{ID}_{k})$, or even be omitted as
the adversary can still create a valid forgery by altering the metadata in $C$
(such as the sender’s identity) without crafting a new $c^{\prime}$. This
attack can occur naturally if $\pcalgostyle{ID}_{2}$ is offline when $m$ is
first sent.

An attack of a similar nature can also occur if the same signature key is re-
used across groups, and they are refreshed at different times, as pointed out
in [17].

The second issue we note is that the implementation of the
$\pcalgostyle{Exec}$ algorithm can be problematic if messages are not
authenticated correctly. This led to attacks in the past such as the _burgle
into the group_ or the _acknowledgement forgery_ attacks in [21]. Securing
control messages and group membership changes is possible as introduced in
[16].

###  V-D Proposed Modifications and Tweaks

####  V-D1 Ratcheting signature keys

The attack shown in the previous section can be mitigated if signature keys
are also ratcheted. A simple fix is to introduce a _chain_ of signature keys,
where an ephemeral signature key is created every time a message or block of
messages is sent.

Let $(\pcalgostyle{ssk},\pcalgostyle{spk})$ be $\pcalgostyle{ID}$’s signature
key pair, where $\pcalgostyle{spk}$ is part of its Sender Key. Then, before
sending a new message $m$ to the group, $\pcalgostyle{ID}$ can generate a new
key pair
$(\pcalgostyle{ssk}^{\prime},\pcalgostyle{spk}^{\prime})\mathrel{\vbox{\offinterlineskip\halign{
\hfil#\hfil\cr\hskip
1.00006pt$\scriptscriptstyle\$$\cr$\leftarrow$\cr}}}\pcalgostyle{Gen}(\secparam)$.
Then, $\pcalgostyle{ID}$ can do as follows:

  * •

Encrypt the $i$th message $m$ with the corresponding $\pcalgostyle{mk}$,
$c\mathrel{\vbox{\offinterlineskip\halign{ \hfil#\hfil\cr\hskip
1.00006pt$\scriptscriptstyle\$$\cr$\leftarrow$\cr}}}\enc(\pcalgostyle{mk},m)$.

  * •

Sign $C\leftarrow(c,i,\pcalgostyle{ID},\pcalgostyle{spk}^{\prime})$ as
$\sigma\mathrel{\vbox{\offinterlineskip\halign{ \hfil#\hfil\cr\hskip
1.00006pt$\scriptscriptstyle\$$\cr$\leftarrow$\cr}}}\sig(\pcalgostyle{ssk},C)$

  * •

Send the tuple $(\sigma,C)$ to the group.

  * •

Replace $\pcalgostyle{ssk}$ by $\pcalgostyle{ssk}^{\prime}$.

Upon reception of a message, $\pcalgostyle{ID}^{\prime}$ will:

  * •

Verify the signature as $\pcalgostyle{Ver}(\pcalgostyle{spk},\sigma,C)$ and
decrypt the ciphertext $c$.

  * •

Replace $\pcalgostyle{spk}$ by $\pcalgostyle{spk}^{\prime}$ in
$\pcalgostyle{ID}$’s sender key.

Note that this countermeasure involves a notable overhead and entropy
consumption (although only for the sender), so it may not be desirable in all
scenarios, or for all sent messages. Users could also replace their signature
keys on-demand or on a time schedule to trade more post-compromise security
for performance.

####  V-D2 Randomness manipulation

We note that Sender Keys, as described in Section III, is susceptible to
randomness exposure and randomness manipulation attacks. Namely, the adversary
does not need to leak a member’s state, but simply control the randomness used
by the device, inhibiting any form of PCS. Protection against this family of
attacks can be attained at small cost if freshly generated keys are hashed
with the state or with part of the state, as in [2] and the classic NAXOS
trick for authenticated key exchange [22].

####  V-D3 Refresh option for PCS

Post compromise security (PCS) is generally achieved when introducing fresh
randomness by establishing new group secrets. In the case of Sender Keys, it
could be beneficial to establish new sender keys across the group at some
intervals, for instance via an _update_ group operation, as noted in [17].
However, if only Alice updates her sender key, a passive adversary would still
be able to eavesdrop on messages sent by any other group member. Furthermore,
as the sender key is group-specific, any messages sent by Alice in another
group are also susceptible to eavesdropping. We refer the reader to Appendix A
of [17] for a more detailed discussion and conclude that the sender keys is
not a suitable approach towards achieving a PCS-secure group messenger.

##  VI Conclusion and Future Work

The Sender Keys protocol is a convenient protocol for group chats which is
simple to implement, achieves a fair degree of end-to-end forward security,
and deals well with concurrency. Nevertheless, we remark that no security is
gained by employing multiple sender keys with respect to a single group key
given randomness used to generate the keys is honest (i.e., in our model).
Furthermore, forward security is sub-optimal for message authentication, which
can be fixed by ratcheting signature keys.

Our results are under the assumption that two-party channels are secure, which
is clearly not the case in practice. Therefore, more powerful attacks may
arise under a more realistic model where exposure of two-party channels is
possible. We also note that, in the real world, the security of messaging apps
can also be broken in different ways than attacking the protocol. Additional
features such as conversation transcript backups and multi-device support
highly increase the attack surface and should be avoided in applications where
security is critical.

Our analysis leaves multiple directions for future work, such as a rigorous
formalization of the security model with a fine-grained analysis of the two-
party channels and user compromise, more precise cleanness predicates, and
especially concrete security reductions.

## Acknowledgements

This work has received funding from the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation program under
project PICOCRYPT (grant agreement No. 101001283), and by a grant from Nomadic
Labs and the Tezos foundation. The last author was supported by DFG under
Germany’s Excellence Strategy - EXC 2092 CASA - 390781972. We are grateful to
the reviewers of RECSI 2022 for their helpful comments on earlier versions of
this work.

## References

  * [1] M. Marlinspike and T. Perrin, “The double ratchet algorithm,” 2016. [Online]. Available: https://signal.org/docs/specifications/doubleratchet/doubleratchet.pdf
  * [2] J. Jaeger and I. Stepanovs, “Optimal channel security against fine-grained state compromise: The safety of messaging,” in _Advances in Cryptology – CRYPTO 2018, Part I_ , ser. Lecture Notes in Computer Science, H. Shacham and A. Boldyreva, Eds., vol. 10991. Santa Barbara, CA, USA: Springer, Heidelberg, Germany, Aug. 19–23, 2018, pp. 33–62.
  * [3] B. Poettering and P. Rösler, “Asynchronous ratcheted key exchange,” Cryptology ePrint Archive, Report 2018/296, 2018, https://eprint.iacr.org/2018/296.
  * [4] F. B. Durak and S. Vaudenay, “Bidirectional asynchronous ratcheted key agreement with linear complexity,” in _IWSEC 19: 14th International Workshop on Security, Advances in Information and Computer Security_ , ser. Lecture Notes in Computer Science, N. Attrapadung and T. Yagi, Eds., vol. 11689\. Tokyo, Japan: Springer, Heidelberg, Germany, Aug. 28–30, 2019, pp. 343–362.
  * [5] J. Alwen, S. Coretti, and Y. Dodis, “The double ratchet: Security notions, proofs, and modularization for the Signal protocol,” in _Advances in Cryptology – EUROCRYPT 2019, Part I_ , ser. Lecture Notes in Computer Science, Y. Ishai and V. Rijmen, Eds., vol. 11476. Darmstadt, Germany: Springer, Heidelberg, Germany, May 19–23, 2019, pp. 129–158.
  * [6] F. Balli, P. Rösler, and S. Vaudenay, “Determining the core primitive for optimally secure ratcheting,” in _Advances in Cryptology – ASIACRYPT 2020, Part III_ , ser. Lecture Notes in Computer Science, S. Moriai and H. Wang, Eds., vol. 12493. Daejeon, South Korea: Springer, Heidelberg, Germany, Dec. 7–11, 2020, pp. 621–650.
  * [7] R. Barnes, B. Beurdouche, R. Robert, J. Millican, E. Omara, and K. Cohn-Gordon, “The Messaging Layer Security (MLS) Protocol,” Internet Engineering Task Force, Internet-Draft draft-ietf-mls-protocol-14, May 2022, work in Progress. [Online]. Available: https://datatracker.ietf.org/doc/html/draft-ietf-mls-protocol-14
  * [8] K. Bhargavan, R. Barnes, and E. Rescorla, “TreeKEM: Asynchronous Decentralized Key Management for Large Dynamic Groups A protocol proposal for Messaging Layer Security (MLS),” Inria Paris, Research Report, May 2018. [Online]. Available: https://hal.inria.fr/hal-02425247
  * [9] J. Alwen, S. Coretti, Y. Dodis, and Y. Tselekounis, “Security analysis and improvements for the IETF MLS standard for group messaging,” in _Advances in Cryptology – CRYPTO 2020, Part I_ , ser. Lecture Notes in Computer Science, D. Micciancio and T. Ristenpart, Eds., vol. 12170. Santa Barbara, CA, USA: Springer, Heidelberg, Germany, Aug. 17–21, 2020, pp. 248–277.
  * [10] K. Klein, G. Pascual-Perez, M. Walter, C. Kamath, M. Capretto, M. Cueto, I. Markov, M. Yeo, J. Alwen, and K. Pietrzak, “Keep the dirt: Tainted TreeKEM, adaptively and actively secure continuous group key agreement,” in _2021 IEEE Symposium on Security and Privacy_. San Francisco, CA, USA: IEEE Computer Society Press, May 24–27, 2021, pp. 268–284.
  * [11] J. Alwen, S. Coretti, D. Jost, and M. Mularczyk, “Continuous group key agreement with active security,” in _TCC 2020: 18th Theory of Cryptography Conference, Part II_ , ser. Lecture Notes in Computer Science, R. Pass and K. Pietrzak, Eds., vol. 12551. Durham, NC, USA: Springer, Heidelberg, Germany, Nov. 16–19, 2020, pp. 261–290.
  * [12] J. Alwen, S. Coretti, Y. Dodis, and Y. Tselekounis, “Modular design of secure group messaging protocols and the security of MLS,” in _ACM CCS 2021: 28th Conference on Computer and Communications Security_ , G. Vigna and E. Shi, Eds. Virtual Event, Republic of Korea: ACM Press, Nov. 15–19, 2021, pp. 1463–1483.
  * [13] WhatsApp, “WhatsApp Encryption Overview Technical white paper, v.3,” Oct. 2020, https://www.whatsapp.com/security/WhatsApp-Security-Whitepaper.pdf.
  * [14] M. Marlinspike _et al._ , “Signal protocol.” [Online]. Available: https://github.com/signalapp/libsignal-protocol-java/tree/master/java/src/main/java/org/whispersystems/libsignal
  * [15] K. Cohn-Gordon, C. J. F. Cremers, and L. Garratt, “On post-compromise security,” in _CSF 2016: IEEE 29st Computer Security Foundations Symposium_ , M. Hicks and B. Köpf, Eds. Lisbon, Portugal: IEEE Computer Society Press, jun 27-1 2016, pp. 164–178.
  * [16] D. Balbás, D. Collins, and S. Vaudenay, “Cryptographic Administrators for Secure Group Messaging,” Cryptology ePrint Archive.
  * [17] C. Cremers, B. Hale, and K. Kohbrok, “The complexities of healing in secure group messaging: Why cross-group effects matter,” in _USENIX Security 2021: 30th USENIX Security Symposium_ , M. Bailey and R. Greenstadt, Eds. USENIX Association, Aug. 11–13, 2021, pp. 1847–1864.
  * [18] M. Marlinspike and T. Perrin, “The x3dh key agreement protocol,” 2016. [Online]. Available: https://signal.org/docs/specifications/x3dh/x3dh.pdf
  * [19] H. Krawczyk, M. Bellare, and R. Canetti, “HMAC: Keyed-hashing for message authentication,” IETF Internet Request for Comments 2104, Feb. 1997.
  * [20] H. Krawczyk and P. Eronen, “Hmac-based extract-and-expand key derivation function (hkdf),” Internet Requests for Comments, RFC Editor, RFC 5869, May 2010, http://www.rfc-editor.org/rfc/rfc5869.txt. [Online]. Available: http://www.rfc-editor.org/rfc/rfc5869.txt
  * [21] P. Rösler, C. Mainka, and J. Schwenk, “More is less: On the end-to-end security of group chats in signal, whatsapp, and threema,” in _2018 IEEE European Symposium on Security and Privacy (EuroS &P)_, 2018, pp. 415–429.
  * [22] B. A. LaMacchia, K. Lauter, and A. Mityagin, “Stronger security of authenticated key exchange,” in _ProvSec 2007: 1st International Conference on Provable Security_ , ser. Lecture Notes in Computer Science, W. Susilo, J. K. Liu, and Y. Mu, Eds., vol. 4784. Wollongong, Australia: Springer, Heidelberg, Germany, Nov. 1–2, 2007, pp. 1–16.