@phdthesis{22664,
  abstract     = {The widespread adoption of apps like Whatsapp and Signal has translated into billions of people all around the world communicating on a regular basis by making use of services that offer end-to-end encryption and even provide security guarantees when a user's device is compromised.

This was made possible by the introduction of the Double Ratchet Algorithm~\cite{double_ratchet}, which was designed for a setting where communication takes place between two parties.
However, in practice, many apps offer the possibility of creating groups.
The protocols they use to secure communication are inefficient for large group which has the undesireable consequence that the aforementioned apps have established limits on the group size of roughly 1000 users.
This has motivated the introduction of the Messaging Layer Security (MLS) standard~\cite{rfc9420} by the IETF which is based on a primitive called Continuous Group Key Agreement (CGKA)~\cite{C:ACDT20}.

This primitive allows a group of users to maintain a shared secret key that is frequently rotated by the group members in order to change group membership, achieve forward secrecy (FS) and post compromise security (PCS).
Most protocols are based on binary trees where the nodes are associated to a pair formed by public key and a secret key.
Each leaf corresponds to one of the group members and a user knows the secret keys associated to nodes along the path from their leaf to the root.
When a user wants to update their key material they have to change $ \log(N) $ many keys.
This requires uploading $ \log(N) $ many ciphertexts to communicate the new keys to the rest of the group members in a way that respects the tree structure.

In this thesis we study how much communication between group members is required in order to add and remove users from a group as well as in order to provide PCS when we consider CGKAs built using standard cryptographic primitives like pseudo-random functions and public-key encryption. Furthermore, we also consider the case of MLS and provide the first lower bound showing that its communication complexity is much worse than previously believed, i.e., it is very far from $ \log(N) $.
Finally, we also propose a variant of MLS which provably achieves the same security properties with a much lower communication cost.},
  author       = {Cueto Noval, Miguel},
  isbn         = { 978-3-99078-087-9},
  issn         = {2663-337X},
  pages        = {187},
  publisher    = {Institute of Science and Technology Austria},
  title        = {{Towards efficient secure group messaging}},
  doi          = {10.15479/AT-ISTA-22664},
  year         = {2026},
}

@inproceedings{20846,
  abstract     = {CVRFs are PRFs that unify the properties of verifiable and constrained PRFs. Since they were introduced concurrently by Fuchsbauer and Chandran-Raghuraman-Vinayagamurthy in 2014, it has been an open problem to construct CVRFs without using heavy machinery such as multilinear maps, obfuscation or functional encryption.
We solve this problem by constructing a prefix-constrained verifiable PRF that does not rely on the aforementioned assumptions. Essentially, our construction is a verifiable version of the Goldreich-Goldwasser-Micali PRF. To achieve verifiability we leverage degree-2 algebraic PRGs and bilinear groups. In short, proofs consist of intermediate values of the Goldreich-Goldwasser-Micali PRF raised to the exponents of group elements. These outputs can be verified using pairings since the underlying PRG is of degree 2.
We prove the selective security of our construction under the Decisional Square Diffie-Hellman (DSDH) assumption and a new assumption, which we dub recursive Decisional Diffie-Hellman (recursive DDH).
We prove the soundness of recursive DDH in the generic group model assuming the hardness of the Multivariate Quadratic (MQ) problem and a new variant thereof, which we call MQ+.
Last, in terms of applications, we observe that our CVRF is also an exponent (C)VRF in the plain model. Exponent VRFs were recently introduced by Boneh et al. (Eurocrypt’25) with various applications to threshold cryptography in mind. In addition to that, we give further applications for prefix-CVRFs in the blockchain setting, namely, stake-pooling and compressible randomness beacons.},
  author       = {Brandt, Nicholas and Cueto Noval, Miguel and Günther, Christoph Ullrich and Ünal, Akin and Wohnig, Stella},
  booktitle    = {23rd International Conference on Theory of Cryptography},
  isbn         = {9783032122896},
  issn         = {1611-3349},
  location     = {Aarhus, Denmark},
  pages        = {478--511},
  publisher    = {Springer Nature},
  title        = {{Constrained verifiable random functions without obfuscation and friends}},
  doi          = {10.1007/978-3-032-12290-2_16},
  volume       = {16271},
  year         = {2025},
}

@inproceedings{19712,
  abstract     = {We study recent algebraic attacks (Briaud-Øygarden EC’23) on the Regular Syndrome Decoding (RSD) problem and the assumptions underlying the correctness of their attacks’ complexity estimates. By relating these assumptions to interesting algebraic-combinatorial problems, we prove that they do not hold in full generality. However, we show that they are (asymptotically) true for most parameter sets, supporting the soundness of algebraic attacks on RSD. Further, we prove—without any heuristics or assumptions—that RSD can be broken in polynomial time whenever the number of error blocks times the square of the size of error blocks is larger than 2 times the square of the dimension of the code.
Additionally, we use our methodology to attack a variant of the Learning With Errors problem where each error term lies in a fixed set of constant size. We prove that this problem can be broken in polynomial time, given a sufficient number of samples. This result improves on the seminal work by Arora and Ge (ICALP’11), as the attack’s time complexity is independent of the LWE modulus.},
  author       = {Cueto Noval, Miguel and Merz, Simon-Philipp and Stählin, Patrick and Ünal, Akin},
  booktitle    = {44th Annual International Conference on the Theory and Applications of Cryptographic Techniques},
  isbn         = {9783031910944},
  issn         = {1611-3349},
  location     = {Madrid, Spain},
  pages        = {385--415},
  publisher    = {Springer Nature},
  title        = {{On the soundness of algebraic attacks against code-based assumptions}},
  doi          = {10.1007/978-3-031-91095-1_14},
  volume       = {15606},
  year         = {2025},
}

@inproceedings{21262,
  abstract     = {Continuous Group Key Agreement (CGKA) is the primitive underlying secure group messaging. It allows a large group of N users to maintain a shared secret key that is frequently rotated by the
group members in order to achieve forward secrecy and post compromise security. The group messaging scheme Messaging Layer Security (MLS) standardized by the IETF makes use of a CGKA called TreeKEM which arranges the N group members in a binary tree. Here, each node is associated with a public-key, each user is assigned one of the leaves, and a user knows the corresponding secret keys from their leaf to the root. To update the key material known to them, a user must just replace keys at log(N) nodes, which requires them to create and upload log(N) ciphertexts. Such updates must be processed sequentially by all users, which for large groups is impractical. To allow for concurrent updates, TreeKEM uses the “propose and commit” paradigm, where multiple users can concurrently propose to update (by just sampling a fresh leaf key), and a single user can then commit to all proposals at once. Unfortunately, this process destroys the binary tree structure as the tree gets pruned and some nodes must be “blanked” at the cost of increasing the in-degree of others, which makes the commit operation, as well as, future commits more costly. In the worst case, the update cost (in terms of uploaded ciphertexts) per user can grow from log(N) to Ω(N). In this work we provide two main contributions. First, we show that MLS’ communication complexity is bad not only in the worst case but also if the proposers and committers are chosen at random: even if there’s just one update proposal for every commit the expected cost is already over √N, and it approaches N as this ratio changes towards more proposals. Our second contribution is a new variant of propose and commit for
TreeKEM which for moderate amounts of update proposals per commit provably achieves an update cost of Θ(log(N)) assuming the proposers and committers are chosen at random.},
  author       = {Auerbach, Benedikt and Cueto Noval, Miguel and Erol, Boran and Pietrzak, Krzysztof Z},
  booktitle    = {45th Annual International Cryptology Conference},
  isbn         = {9783032019127},
  issn         = {1611-3349},
  location     = {Santa Barbara, CA, United States},
  pages        = {141--172},
  publisher    = {Springer Nature},
  title        = {{Continuous group-key agreement: Concurrent updates without pruning}},
  doi          = {10.1007/978-3-032-01913-4_5},
  volume       = {16007},
  year         = {2025},
}

@inproceedings{18086,
  abstract     = {Abstract. Continuous group key agreement (CGKA) allows a group of
users to maintain a continuously updated shared key in an asynchronous
setting where parties only come online sporadically and their messages
are relayed by an untrusted server. CGKA captures the basic primitive
underlying group messaging schemes.
Current solutions including TreeKEM (“Messaging Layer Security”
(MLS) IETF RFC 9420) cannot handle concurrent requests while retaining low communication complexity. The exception being CoCoA, which
is concurrent while having extremely low communication complexity (in
groups of size n and for m concurrent updates the communication per
user is log(n), i.e., independent of m). The main downside of CoCoA
is that in groups of size n, users might have to do up to log(n) update
requests to the server to ensure their (potentially corrupted) key material has been refreshed.
In this work we present a “fast healing” concurrent CGKA protocol,
named DeCAF, where users will heal after at most log(t) requests, with
t being the number of corrupted users. While also suitable for the standard central-server setting, our protocol is particularly interesting for
realizing decentralized group messaging, where protocol messages (add,
remove, update) are being posted on some append-only data structure
rather than sent to a server. In this setting, concurrency is crucial once
the rate of requests exceeds, say, the rate at which new blocks are added
to a blockchain.
In the central-server setting, CoCoA (the only alternative with concurrency, sub-linear communication and basic post-compromise security)
enjoys much lower download communication. However, in the decentralized setting – where there is no server which can craft specific messages
for different users to reduce their download communication – our protocol
significantly outperforms CoCoA. DeCAF heals in fewer epochs (log(t)
vs. log(n)) while incurring a similar per epoch per user communication
cost.},
  author       = {Alwen, Joel F and Auerbach, Benedikt and Cueto Noval, Miguel and Klein, Karen and Pascual Perez, Guillermo and Pietrzak, Krzysztof Z},
  booktitle    = {Security and Cryptography for Networks: 14th International Conference},
  editor       = {Galdi, Clemente and Phan, Duong Hieu},
  isbn         = {9783031710728},
  issn         = {1611-3349},
  location     = {Amalfi, Italy},
  pages        = {294–313},
  publisher    = {Springer Nature},
  title        = {{DeCAF: Decentralizable CGKA with fast healing}},
  doi          = {10.1007/978-3-031-71073-5_14},
  volume       = {14974},
  year         = {2024},
}

@inproceedings{18702,
  abstract     = {In this work we prove lower bounds on the (communication) cost of maintaining a shared key among a dynamic group of users. Being “dynamic” means one can add and remove users from the group. This captures important protocols like multicast encryption (ME) and continuous group-key agreement (CGKA), which is the primitive underlying many group messaging applications. We prove our bounds in a combinatorial setting where the state of the protocol progresses in rounds. The state of the protocol in each round is captured by a set system, with each of its elements specifying a set of users who share a secret key. We show this combinatorial model implies bounds in symbolic models for ME and CGKA that capture, as building blocks, PRGs, PRFs, dual PRFs, secret sharing, and symmetric encryption in the setting of ME, and PRGs, PRFs, dual PRFs, secret sharing, public-key encryption, and key-updatable public-key encryption in the setting of CGKA. The models are related to the ones used by Micciancio and Panjwani (Eurocrypt’04) and Bienstock et al. (TCC’20) to analyze ME and CGKA, respectively. We prove – using the Bollobás’ Set Pairs Inequality – that the cost (number of uploaded ciphertexts) for replacing a set of d users in a group of size n is Ω(dln(n/d)). Our lower bound is asymptotically tight and both improves on a bound of Ω(d) by Bienstock et al. (TCC’20), and generalizes a result by Micciancio and Panjwani (Eurocrypt’04), who proved a lower bound of Ω(log(n)) for d=1. },
  author       = {Anastos, Michael and Auerbach, Benedikt and Baig, Mirza Ahad and Cueto Noval, Miguel and Kwan, Matthew Alan and Pascual Perez, Guillermo and Pietrzak, Krzysztof Z},
  booktitle    = {22nd International Conference on Theory of Cryptography},
  isbn         = {9783031780103},
  issn         = {1611-3349},
  location     = {Milan, Italy},
  pages        = {413--443},
  publisher    = {Springer Nature},
  title        = {{The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging}},
  doi          = {10.1007/978-3-031-78011-0_14},
  volume       = {15364},
  year         = {2024},
}

@inproceedings{14691,
  abstract     = {Continuous Group-Key Agreement (CGKA) allows a group of users to maintain a shared key. It is the fundamental cryptographic primitive underlying group messaging schemes and related protocols, most notably TreeKEM, the underlying key agreement protocol of the Messaging Layer Security (MLS) protocol, a standard for group messaging by the IETF. CKGA works in an asynchronous setting where parties only occasionally must come online, and their messages are relayed by an untrusted server. The most expensive operation provided by CKGA is that which allows for a user to refresh their key material in order to achieve forward secrecy (old messages are secure when a user is compromised) and post-compromise security (users can heal from compromise). One caveat of early CGKA protocols is that these update operations had to be performed sequentially, with any user wanting to update their key material having had to receive and process all previous updates. Late versions of TreeKEM do allow for concurrent updates at the cost of a communication overhead per update message that is linear in the number of updating parties. This was shown to be indeed necessary when achieving PCS in just two rounds of communication by [Bienstock et al. TCC’20].
The recently proposed protocol CoCoA [Alwen et al. Eurocrypt’22], however, shows that this overhead can be reduced if PCS requirements are relaxed, and only a logarithmic number of rounds is required. The natural question, thus, is whether CoCoA is optimal in this setting.
In this work we answer this question, providing a lower bound on the cost (concretely, the amount of data to be uploaded to the server) for CGKA protocols that heal in an arbitrary k number of rounds, that shows that CoCoA is very close to optimal. Additionally, we extend CoCoA to heal in an arbitrary number of rounds, and propose a modification of it, with a reduced communication cost for certain k.
We prove our bound in a combinatorial setting where the state of the protocol progresses in rounds, and the state of the protocol in each round is captured by a set system, each set specifying a set of users who share a secret key. We show this combinatorial model is equivalent to a symbolic model capturing building blocks including PRFs and public-key encryption, related to the one used by Bienstock et al.
Our lower bound is of order k•n1+1/(k-1)/log(k), where 2≤k≤log(n) is the number of updates per user the protocol requires to heal. This generalizes the n2 bound for k=2 from Bienstock et al.. This bound almost matches the k⋅n1+2/(k-1) or k2⋅n1+1/(k-1) efficiency we get for the variants of the CoCoA protocol also introduced in this paper.},
  author       = {Auerbach, Benedikt and Cueto Noval, Miguel and Pascual Perez, Guillermo and Pietrzak, Krzysztof Z},
  booktitle    = {21st International Conference on Theory of Cryptography},
  isbn         = {9783031486203},
  issn         = {1611-3349},
  location     = {Taipei, Taiwan},
  pages        = {271--300},
  publisher    = {Springer Nature},
  title        = {{On the cost of post-compromise security in concurrent Continuous Group-Key Agreement}},
  doi          = {10.1007/978-3-031-48621-0_10},
  volume       = {14371},
  year         = {2023},
}

@inproceedings{12516,
  abstract     = {The homogeneous continuous LWE (hCLWE) problem is to distinguish samples of a specific high-dimensional Gaussian mixture from standard normal samples. It was shown to be at least as hard as Learning with Errors, but no reduction in the other direction is currently known.
We present four new public-key encryption schemes based on the hardness of hCLWE, with varying tradeoffs between decryption and security errors, and different discretization techniques. Our schemes yield a polynomial-time algorithm for solving hCLWE using a Statistical Zero-Knowledge oracle.},
  author       = {Bogdanov, Andrej and Cueto Noval, Miguel and Hoffmann, Charlotte and Rosen, Alon},
  booktitle    = {Theory of Cryptography},
  isbn         = {9783031223648},
  issn         = {1611-3349},
  location     = {Chicago, IL, United States},
  pages        = {565--592},
  publisher    = {Springer Nature},
  title        = {{Public-Key Encryption from Homogeneous CLWE}},
  doi          = {10.1007/978-3-031-22365-5_20},
  volume       = {13748},
  year         = {2022},
}

@inproceedings{11476,
  abstract     = {Messaging platforms like Signal are widely deployed and provide strong security in an asynchronous setting. It is a challenging problem to construct a protocol with similar security guarantees that can efficiently scale to large groups. A major bottleneck are the frequent key rotations users need to perform to achieve post compromise forward security.

In current proposals – most notably in TreeKEM (which is part of the IETF’s Messaging Layer Security (MLS) protocol draft) – for users in a group of size n to rotate their keys, they must each craft a message of size log(n) to be broadcast to the group using an (untrusted) delivery server.

In larger groups, having users sequentially rotate their keys requires too much bandwidth (or takes too long), so variants allowing any T≤n users to simultaneously rotate their keys in just 2 communication rounds have been suggested (e.g. “Propose and Commit” by MLS). Unfortunately, 2-round concurrent updates are either damaging or expensive (or both); i.e. they either result in future operations being more costly (e.g. via “blanking” or “tainting”) or are costly themselves requiring Ω(T) communication for each user [Bienstock et al., TCC’20].

In this paper we propose CoCoA; a new scheme that allows for T concurrent updates that are neither damaging nor costly. That is, they add no cost to future operations yet they only require Ω(log2(n)) communication per user. To circumvent the [Bienstock et al.] lower bound, CoCoA increases the number of rounds needed to complete all updates from 2 up to (at most) log(n); though typically fewer rounds are needed.

The key insight of our protocol is the following: in the (non-concurrent version of) TreeKEM, a delivery server which gets T concurrent update requests will approve one and reject the remaining T−1. In contrast, our server attempts to apply all of them. If more than one user requests to rotate the same key during a round, the server arbitrarily picks a winner. Surprisingly, we prove that regardless of how the server chooses the winners, all previously compromised users will recover after at most log(n) such update rounds.

To keep the communication complexity low, CoCoA is a server-aided CGKA. That is, the delivery server no longer blindly forwards packets, but instead actively computes individualized packets tailored to each user. As the server is untrusted, this change requires us to develop new mechanisms ensuring robustness of the protocol.},
  author       = {Alwen, Joël and Auerbach, Benedikt and Cueto Noval, Miguel and Klein, Karen and Pascual Perez, Guillermo and Pietrzak, Krzysztof Z and Walter, Michael},
  booktitle    = {Advances in Cryptology – EUROCRYPT 2022},
  isbn         = {9783031070846},
  issn         = {1611-3349},
  location     = {Trondheim, Norway},
  pages        = {815–844},
  publisher    = {Springer Nature},
  title        = {{CoCoA: Concurrent continuous group key agreement}},
  doi          = {10.1007/978-3-031-07085-3_28},
  volume       = {13276},
  year         = {2022},
}

@inproceedings{10408,
  abstract     = {Key trees are often the best solution in terms of transmission cost and storage requirements for managing keys in a setting where a group needs to share a secret key, while being able to efficiently rotate the key material of users (in order to recover from a potential compromise, or to add or remove users). Applications include multicast encryption protocols like LKH (Logical Key Hierarchies) or group messaging like the current IETF proposal TreeKEM. A key tree is a (typically balanced) binary tree, where each node is identified with a key: leaf nodes hold users’ secret keys while the root is the shared group key. For a group of size N, each user just holds   log(N)  keys (the keys on the path from its leaf to the root) and its entire key material can be rotated by broadcasting   2log(N)  ciphertexts (encrypting each fresh key on the path under the keys of its parents). In this work we consider the natural setting where we have many groups with partially overlapping sets of users, and ask if we can find solutions where the cost of rotating a key is better than in the trivial one where we have a separate key tree for each group. We show that in an asymptotic setting (where the number m of groups is fixed while the number N of users grows) there exist more general key graphs whose cost converges to the cost of a single group, thus saving a factor linear in the number of groups over the trivial solution. As our asymptotic “solution” converges very slowly and performs poorly on concrete examples, we propose an algorithm that uses a natural heuristic to compute a key graph for any given group structure. Our algorithm combines two greedy algorithms, and is thus very efficient: it first converts the group structure into a “lattice graph”, which is then turned into a key graph by repeatedly applying the algorithm for constructing a Huffman code. To better understand how far our proposal is from an optimal solution, we prove lower bounds on the update cost of continuous group-key agreement and multicast encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom generators, and secret sharing as building blocks.},
  author       = {Alwen, Joel F and Auerbach, Benedikt and Baig, Mirza Ahad and Cueto Noval, Miguel and Klein, Karen and Pascual Perez, Guillermo and Pietrzak, Krzysztof Z and Walter, Michael},
  booktitle    = {19th International Conference},
  isbn         = {9-783-0309-0455-5},
  issn         = {1611-3349},
  location     = {Raleigh, NC, United States},
  pages        = {222--253},
  publisher    = {Springer Nature},
  title        = {{Grafting key trees: Efficient key management for overlapping groups}},
  doi          = {10.1007/978-3-030-90456-2_8},
  volume       = {13044},
  year         = {2021},
}

@inproceedings{10049,
  abstract     = {While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations.Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. The security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security – where also the users can arbitrarily deviate – remains open.},
  author       = {Klein, Karen and Pascual Perez, Guillermo and Walter, Michael and Kamath Hosdurg, Chethan and Capretto, Margarita and Cueto Noval, Miguel and Markov, Ilia and Yeo, Michelle X and Alwen, Joel F and Pietrzak, Krzysztof Z},
  booktitle    = {2021 IEEE Symposium on Security and Privacy },
  location     = {San Francisco, CA, United States},
  pages        = {268--284},
  publisher    = {IEEE},
  title        = {{Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement}},
  doi          = {10.1109/sp40001.2021.00035},
  year         = {2021},
}

