---
OA_place: repository
OA_type: green
_id: '19712'
abstract:
- lang: eng
text: "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.\r\nAdditionally, 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."
acknowledgement: We thank Pierre Briaud and Morten Øygarden for helpful discussions
on algebraic attacks on RSD, and the EC reviewers for helpful comments.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Simon-Philipp
full_name: Merz, Simon-Philipp
last_name: Merz
- first_name: Patrick
full_name: Stählin, Patrick
last_name: Stählin
- first_name: Akin
full_name: Ünal, Akin
id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
last_name: Ünal
orcid: 0000-0002-8929-0221
citation:
ama: 'Cueto Noval M, Merz S-P, Stählin P, Ünal A. On the soundness of algebraic
attacks against code-based assumptions. In: 44th Annual International Conference
on the Theory and Applications of Cryptographic Techniques. Vol 15606. Springer
Nature; 2025:385-415. doi:10.1007/978-3-031-91095-1_14'
apa: 'Cueto Noval, M., Merz, S.-P., Stählin, P., & Ünal, A. (2025). On the soundness
of algebraic attacks against code-based assumptions. In 44th Annual International
Conference on the Theory and Applications of Cryptographic Techniques (Vol.
15606, pp. 385–415). Madrid, Spain: Springer Nature. https://doi.org/10.1007/978-3-031-91095-1_14'
chicago: Cueto Noval, Miguel, Simon-Philipp Merz, Patrick Stählin, and Akin Ünal.
“On the Soundness of Algebraic Attacks against Code-Based Assumptions.” In 44th
Annual International Conference on the Theory and Applications of Cryptographic
Techniques, 15606:385–415. Springer Nature, 2025. https://doi.org/10.1007/978-3-031-91095-1_14.
ieee: M. Cueto Noval, S.-P. Merz, P. Stählin, and A. Ünal, “On the soundness of algebraic
attacks against code-based assumptions,” in 44th Annual International Conference
on the Theory and Applications of Cryptographic Techniques, Madrid, Spain,
2025, vol. 15606, pp. 385–415.
ista: 'Cueto Noval M, Merz S-P, Stählin P, Ünal A. 2025. On the soundness of algebraic
attacks against code-based assumptions. 44th Annual International Conference on
the Theory and Applications of Cryptographic Techniques. EUROCRYPT: International
Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol.
15606, 385–415.'
mla: Cueto Noval, Miguel, et al. “On the Soundness of Algebraic Attacks against
Code-Based Assumptions.” 44th Annual International Conference on the Theory
and Applications of Cryptographic Techniques, vol. 15606, Springer Nature,
2025, pp. 385–415, doi:10.1007/978-3-031-91095-1_14.
short: M. Cueto Noval, S.-P. Merz, P. Stählin, A. Ünal, in:, 44th Annual International
Conference on the Theory and Applications of Cryptographic Techniques, Springer
Nature, 2025, pp. 385–415.
conference:
end_date: 2025-05-08
location: Madrid, Spain
name: 'EUROCRYPT: International Conference on the Theory and Applications of Cryptographic
Techniques'
start_date: 2025-05-04
corr_author: '1'
date_created: 2025-05-19T14:15:01Z
date_published: 2025-04-28T00:00:00Z
date_updated: 2025-05-28T06:12:39Z
day: '28'
department:
- _id: KrPi
doi: 10.1007/978-3-031-91095-1_14
intvolume: ' 15606'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.research-collection.ethz.ch/handle/20.500.11850/732894
month: '04'
oa: 1
oa_version: Submitted Version
page: 385-415
publication: 44th Annual International Conference on the Theory and Applications of
Cryptographic Techniques
publication_identifier:
eisbn:
- '9783031910951'
eissn:
- 1611-3349
isbn:
- '9783031910944'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the soundness of algebraic attacks against code-based assumptions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15606
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20846'
abstract:
- lang: eng
text: "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.\r\nWe 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.\r\nWe 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).\r\nWe 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+.\r\nLast,
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."
acknowledgement: "We thank Jonas Steinbach and Gertjan De Mulder for helpful discussions
on BIP 32, Dennis Hofheinz and Julia Kastner for helpful discussions on early prototypes
of our CVRF, and Klaus Kraßnitzer for running pairing benchmarks on his MacBook
Pro.\r\nChristoph U. Günther: This research was funded in whole or in part by the
Austrian Science Fund (FWF) 10.55776/F85. For open access purposes, the author has
applied a CC BY public copyright license to any author-accepted manuscript version
arising from this submission."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Nicholas
full_name: Brandt, Nicholas
last_name: Brandt
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Christoph Ullrich
full_name: Günther, Christoph Ullrich
id: ec98511c-eb8e-11eb-b029-edd25d7271a1
last_name: Günther
- first_name: Akin
full_name: Ünal, Akin
id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
last_name: Ünal
orcid: 0000-0002-8929-0221
- first_name: Stella
full_name: Wohnig, Stella
last_name: Wohnig
citation:
ama: 'Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. Constrained verifiable
random functions without obfuscation and friends. In: 23rd International Conference
on Theory of Cryptography. Vol 16271. Springer Nature; 2025:478-511. doi:10.1007/978-3-032-12290-2_16'
apa: 'Brandt, N., Cueto Noval, M., Günther, C. U., Ünal, A., & Wohnig, S. (2025).
Constrained verifiable random functions without obfuscation and friends. In 23rd
International Conference on Theory of Cryptography (Vol. 16271, pp. 478–511).
Aarhus, Denmark: Springer Nature. https://doi.org/10.1007/978-3-032-12290-2_16'
chicago: Brandt, Nicholas, Miguel Cueto Noval, Christoph Ullrich Günther, Akin Ünal,
and Stella Wohnig. “Constrained Verifiable Random Functions without Obfuscation
and Friends.” In 23rd International Conference on Theory of Cryptography,
16271:478–511. Springer Nature, 2025. https://doi.org/10.1007/978-3-032-12290-2_16.
ieee: N. Brandt, M. Cueto Noval, C. U. Günther, A. Ünal, and S. Wohnig, “Constrained
verifiable random functions without obfuscation and friends,” in 23rd International
Conference on Theory of Cryptography, Aarhus, Denmark, 2025, vol. 16271, pp.
478–511.
ista: 'Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. 2025. Constrained
verifiable random functions without obfuscation and friends. 23rd International
Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol.
16271, 478–511.'
mla: Brandt, Nicholas, et al. “Constrained Verifiable Random Functions without Obfuscation
and Friends.” 23rd International Conference on Theory of Cryptography,
vol. 16271, Springer Nature, 2025, pp. 478–511, doi:10.1007/978-3-032-12290-2_16.
short: N. Brandt, M. Cueto Noval, C.U. Günther, A. Ünal, S. Wohnig, in:, 23rd International
Conference on Theory of Cryptography, Springer Nature, 2025, pp. 478–511.
conference:
end_date: 2025-12-05
location: Aarhus, Denmark
name: 'TCC: Theory of Cryptography'
start_date: 2025-12-01
corr_author: '1'
date_created: 2025-12-21T23:01:34Z
date_published: 2025-12-05T00:00:00Z
date_updated: 2025-12-29T11:11:29Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-032-12290-2_16
intvolume: ' 16271'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1045
month: '12'
oa: 1
oa_version: Preprint
page: 478-511
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 23rd International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032122896'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constrained verifiable random functions without obfuscation and friends
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16271
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '21262'
abstract:
- lang: eng
text: "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\r\ngroup 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\r\nTreeKEM 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."
acknowledgement: B. Auerbach and B. Erol—Conducted part of this work at ISTA.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Boran
full_name: Erol, Boran
last_name: Erol
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Auerbach B, Cueto Noval M, Erol B, Pietrzak KZ. Continuous group-key agreement:
Concurrent updates without pruning. In: 45th Annual International Cryptology
Conference. Vol 16007. Springer Nature; 2025:141-172. doi:10.1007/978-3-032-01913-4_5'
apa: 'Auerbach, B., Cueto Noval, M., Erol, B., & Pietrzak, K. Z. (2025). Continuous
group-key agreement: Concurrent updates without pruning. In 45th Annual International
Cryptology Conference (Vol. 16007, pp. 141–172). Santa Barbara, CA, United
States: Springer Nature. https://doi.org/10.1007/978-3-032-01913-4_5'
chicago: 'Auerbach, Benedikt, Miguel Cueto Noval, Boran Erol, and Krzysztof Z Pietrzak.
“Continuous Group-Key Agreement: Concurrent Updates without Pruning.” In 45th
Annual International Cryptology Conference, 16007:141–72. Springer Nature,
2025. https://doi.org/10.1007/978-3-032-01913-4_5.'
ieee: 'B. Auerbach, M. Cueto Noval, B. Erol, and K. Z. Pietrzak, “Continuous group-key
agreement: Concurrent updates without pruning,” in 45th Annual International
Cryptology Conference, Santa Barbara, CA, United States, 2025, vol. 16007,
pp. 141–172.'
ista: 'Auerbach B, Cueto Noval M, Erol B, Pietrzak KZ. 2025. Continuous group-key
agreement: Concurrent updates without pruning. 45th Annual International Cryptology
Conference. CRYPTO: International Cryptology Conference, LNCS, vol. 16007, 141–172.'
mla: 'Auerbach, Benedikt, et al. “Continuous Group-Key Agreement: Concurrent Updates
without Pruning.” 45th Annual International Cryptology Conference, vol.
16007, Springer Nature, 2025, pp. 141–72, doi:10.1007/978-3-032-01913-4_5.'
short: B. Auerbach, M. Cueto Noval, B. Erol, K.Z. Pietrzak, in:, 45th Annual International
Cryptology Conference, Springer Nature, 2025, pp. 141–172.
conference:
end_date: 2025-08-21
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2025-08-17
date_created: 2026-02-17T07:41:04Z
date_published: 2025-08-17T00:00:00Z
date_updated: 2026-02-18T07:36:42Z
day: '17'
department:
- _id: KrPi
doi: 10.1007/978-3-032-01913-4_5
intvolume: ' 16007'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1035
month: '08'
oa: 1
oa_version: Preprint
page: 141-172
publication: 45th Annual International Cryptology Conference
publication_identifier:
eisbn:
- '9783032019134'
eissn:
- 1611-3349
isbn:
- '9783032019127'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: 'Continuous group-key agreement: Concurrent updates without pruning'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16007
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '18702'
abstract:
- lang: eng
text: '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. '
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Anastos M, Auerbach B, Baig MA, et al. The cost of maintaining keys in dynamic
groups with applications to multicast encryption and group messaging. In: 22nd
International Conference on Theory of Cryptography. Vol 15364. Springer Nature;
2024:413-443. doi:10.1007/978-3-031-78011-0_14'
apa: 'Anastos, M., Auerbach, B., Baig, M. A., Cueto Noval, M., Kwan, M. A., Pascual
Perez, G., & Pietrzak, K. Z. (2024). The cost of maintaining keys in dynamic
groups with applications to multicast encryption and group messaging. In 22nd
International Conference on Theory of Cryptography (Vol. 15364, pp. 413–443).
Milan, Italy: Springer Nature. https://doi.org/10.1007/978-3-031-78011-0_14'
chicago: Anastos, Michael, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval,
Matthew Alan Kwan, Guillermo Pascual Perez, and Krzysztof Z Pietrzak. “The Cost
of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption
and Group Messaging.” In 22nd International Conference on Theory of Cryptography,
15364:413–43. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-78011-0_14.
ieee: M. Anastos et al., “The cost of maintaining keys in dynamic groups
with applications to multicast encryption and group messaging,” in 22nd International
Conference on Theory of Cryptography, Milan, Italy, 2024, vol. 15364, pp.
413–443.
ista: 'Anastos M, Auerbach B, Baig MA, Cueto Noval M, Kwan MA, Pascual Perez G,
Pietrzak KZ. 2024. The cost of maintaining keys in dynamic groups with applications
to multicast encryption and group messaging. 22nd International Conference on
Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 15364, 413–443.'
mla: Anastos, Michael, et al. “The Cost of Maintaining Keys in Dynamic Groups with Applications
to Multicast Encryption and Group Messaging.” 22nd International Conference
on Theory of Cryptography, vol. 15364, Springer Nature, 2024, pp. 413–43,
doi:10.1007/978-3-031-78011-0_14.
short: M. Anastos, B. Auerbach, M.A. Baig, M. Cueto Noval, M.A. Kwan, G. Pascual
Perez, K.Z. Pietrzak, in:, 22nd International Conference on Theory of Cryptography,
Springer Nature, 2024, pp. 413–443.
conference:
end_date: 2024-12-06
location: Milan, Italy
name: 'TCC: Theory of Cryptography'
start_date: 2024-12-02
corr_author: '1'
date_created: 2024-12-22T23:01:47Z
date_published: 2024-12-02T00:00:00Z
date_updated: 2025-12-02T13:55:46Z
day: '02'
department:
- _id: MaKw
- _id: KrPi
doi: 10.1007/978-3-031-78011-0_14
external_id:
isi:
- '001545628900014'
intvolume: ' 15364'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2024/1097
month: '12'
oa: 1
oa_version: Preprint
page: 413-443
publication: 22nd International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031780103'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: The cost of maintaining keys in dynamic groups with applications to multicast
encryption and group messaging
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15364
year: '2024'
...
---
_id: '18086'
abstract:
- lang: eng
text: "Abstract. Continuous group key agreement (CGKA) allows a group of\r\nusers
to maintain a continuously updated shared key in an asynchronous\r\nsetting where
parties only come online sporadically and their messages\r\nare relayed by an
untrusted server. CGKA captures the basic primitive\r\nunderlying group messaging
schemes.\r\nCurrent solutions including TreeKEM (“Messaging Layer Security”\r\n(MLS)
IETF RFC 9420) cannot handle concurrent requests while retaining low communication
complexity. The exception being CoCoA, which\r\nis concurrent while having extremely
low communication complexity (in\r\ngroups of size n and for m concurrent updates
the communication per\r\nuser is log(n), i.e., independent of m). The main downside
of CoCoA\r\nis that in groups of size n, users might have to do up to log(n) update\r\nrequests
to the server to ensure their (potentially corrupted) key material has been refreshed.\r\nIn
this work we present a “fast healing” concurrent CGKA protocol,\r\nnamed DeCAF,
where users will heal after at most log(t) requests, with\r\nt being the number
of corrupted users. While also suitable for the standard central-server setting,
our protocol is particularly interesting for\r\nrealizing decentralized group
messaging, where protocol messages (add,\r\nremove, update) are being posted on
some append-only data structure\r\nrather than sent to a server. In this setting,
concurrency is crucial once\r\nthe rate of requests exceeds, say, the rate at
which new blocks are added\r\nto a blockchain.\r\nIn the central-server setting,
CoCoA (the only alternative with concurrency, sub-linear communication and basic
post-compromise security)\r\nenjoys much lower download communication. However,
in the decentralized setting – where there is no server which can craft specific
messages\r\nfor different users to reduce their download communication – our protocol\r\nsignificantly
outperforms CoCoA. DeCAF heals in fewer epochs (log(t)\r\nvs. log(n)) while incurring
a similar per epoch per user communication\r\ncost."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Alwen JF, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ.
DeCAF: Decentralizable CGKA with fast healing. In: Galdi C, Phan DH, eds. Security
and Cryptography for Networks: 14th International Conference. Vol 14974. Cham:
Springer Nature; 2024:294–313. doi:10.1007/978-3-031-71073-5_14'
apa: 'Alwen, J. F., Auerbach, B., Cueto Noval, M., Klein, K., Pascual Perez, G.,
& Pietrzak, K. Z. (2024). DeCAF: Decentralizable CGKA with fast healing. In
C. Galdi & D. H. Phan (Eds.), Security and Cryptography for Networks: 14th
International Conference (Vol. 14974, pp. 294–313). Cham: Springer Nature.
https://doi.org/10.1007/978-3-031-71073-5_14'
chicago: 'Alwen, Joel F, Benedikt Auerbach, Miguel Cueto Noval, Karen Klein, Guillermo
Pascual Perez, and Krzysztof Z Pietrzak. “DeCAF: Decentralizable CGKA with Fast
Healing.” In Security and Cryptography for Networks: 14th International Conference,
edited by Clemente Galdi and Duong Hieu Phan, 14974:294–313. Cham: Springer Nature,
2024. https://doi.org/10.1007/978-3-031-71073-5_14.'
ieee: 'J. F. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, and
K. Z. Pietrzak, “DeCAF: Decentralizable CGKA with fast healing,” in Security
and Cryptography for Networks: 14th International Conference, Amalfi, Italy,
2024, vol. 14974, pp. 294–313.'
ista: 'Alwen JF, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ.
2024. DeCAF: Decentralizable CGKA with fast healing. Security and Cryptography
for Networks: 14th International Conference. SCN: Security and Cryptography for
Networks, LNCS, vol. 14974, 294–313.'
mla: 'Alwen, Joel F., et al. “DeCAF: Decentralizable CGKA with Fast Healing.” Security
and Cryptography for Networks: 14th International Conference, edited by Clemente
Galdi and Duong Hieu Phan, vol. 14974, Springer Nature, 2024, pp. 294–313, doi:10.1007/978-3-031-71073-5_14.'
short: 'J.F. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z.
Pietrzak, in:, C. Galdi, D.H. Phan (Eds.), Security and Cryptography for Networks:
14th International Conference, Springer Nature, Cham, 2024, pp. 294–313.'
conference:
end_date: 2024-09-13
location: Amalfi, Italy
name: 'SCN: Security and Cryptography for Networks'
start_date: 2024-09-11
corr_author: '1'
date_created: 2024-09-18T11:35:14Z
date_published: 2024-09-10T00:00:00Z
date_updated: 2026-04-07T13:01:26Z
day: '10'
department:
- _id: GradSch
- _id: KrPi
doi: 10.1007/978-3-031-71073-5_14
editor:
- first_name: Clemente
full_name: Galdi, Clemente
last_name: Galdi
- first_name: Duong Hieu
full_name: Phan, Duong Hieu
last_name: Phan
external_id:
isi:
- '001330408000014'
intvolume: ' 14974'
isi: 1
language:
- iso: eng
month: '09'
oa_version: None
page: 294–313
place: Cham
publication: 'Security and Cryptography for Networks: 14th International Conference'
publication_identifier:
eisbn:
- '9783031710735'
eissn:
- 1611-3349
isbn:
- '9783031710728'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '18088'
relation: dissertation_contains
status: public
status: public
title: 'DeCAF: Decentralizable CGKA with fast healing'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14974
year: '2024'
...
---
_id: '14691'
abstract:
- lang: eng
text: "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].\r\nThe 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.\r\nIn 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.\r\nWe 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.\r\nOur
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."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Auerbach B, Cueto Noval M, Pascual Perez G, Pietrzak KZ. On the cost of post-compromise
security in concurrent Continuous Group-Key Agreement. In: 21st International
Conference on Theory of Cryptography. Vol 14371. Springer Nature; 2023:271-300.
doi:10.1007/978-3-031-48621-0_10'
apa: 'Auerbach, B., Cueto Noval, M., Pascual Perez, G., & Pietrzak, K. Z. (2023).
On the cost of post-compromise security in concurrent Continuous Group-Key Agreement.
In 21st International Conference on Theory of Cryptography (Vol. 14371,
pp. 271–300). Taipei, Taiwan: Springer Nature. https://doi.org/10.1007/978-3-031-48621-0_10'
chicago: Auerbach, Benedikt, Miguel Cueto Noval, Guillermo Pascual Perez, and Krzysztof
Z Pietrzak. “On the Cost of Post-Compromise Security in Concurrent Continuous
Group-Key Agreement.” In 21st International Conference on Theory of Cryptography,
14371:271–300. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-48621-0_10.
ieee: B. Auerbach, M. Cueto Noval, G. Pascual Perez, and K. Z. Pietrzak, “On the cost
of post-compromise security in concurrent Continuous Group-Key Agreement,” in
21st International Conference on Theory of Cryptography, Taipei, Taiwan,
2023, vol. 14371, pp. 271–300.
ista: 'Auerbach B, Cueto Noval M, Pascual Perez G, Pietrzak KZ. 2023. On the cost
of post-compromise security in concurrent Continuous Group-Key Agreement. 21st
International Conference on Theory of Cryptography. TCC: Theory of Cryptography,
LNCS, vol. 14371, 271–300.'
mla: Auerbach, Benedikt, et al. “On the Cost of Post-Compromise Security in Concurrent
Continuous Group-Key Agreement.” 21st International Conference on Theory of
Cryptography, vol. 14371, Springer Nature, 2023, pp. 271–300, doi:10.1007/978-3-031-48621-0_10.
short: B. Auerbach, M. Cueto Noval, G. Pascual Perez, K.Z. Pietrzak, in:, 21st International
Conference on Theory of Cryptography, Springer Nature, 2023, pp. 271–300.
conference:
end_date: 2023-12-02
location: Taipei, Taiwan
name: 'TCC: Theory of Cryptography'
start_date: 2023-11-29
corr_author: '1'
date_created: 2023-12-17T23:00:53Z
date_published: 2023-11-27T00:00:00Z
date_updated: 2025-09-09T13:42:16Z
day: '27'
department:
- _id: KrPi
doi: 10.1007/978-3-031-48621-0_10
external_id:
isi:
- '001160724400010'
intvolume: ' 14371'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2023/1123
month: '11'
oa: 1
oa_version: Preprint
page: 271-300
publication: 21st International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031486203'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the cost of post-compromise security in concurrent Continuous Group-Key
Agreement
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14371
year: '2023'
...
---
_id: '12516'
abstract:
- lang: eng
text: "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.\r\nWe 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."
acknowledgement: "We are grateful to Devika Sharma and Luca Trevisan for their insight
and advice and to an anonymous reviewer for helpful comments.\r\n\r\nThis work was
supported by the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation programme (Grant agreement No. 101019547). The first
author was additionally supported by RGC GRF CUHK14209920 and the fourth author
was additionally supported by ISF grant No. 1399/17, project PROMETHEUS (Grant 780701),
and Cariplo CRYPTONOMEX grant."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Andrej
full_name: Bogdanov, Andrej
last_name: Bogdanov
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
- first_name: Alon
full_name: Rosen, Alon
last_name: Rosen
citation:
ama: 'Bogdanov A, Cueto Noval M, Hoffmann C, Rosen A. Public-Key Encryption from Homogeneous
CLWE. In: Theory of Cryptography. Vol 13748. Springer Nature; 2022:565-592.
doi:10.1007/978-3-031-22365-5_20'
apa: 'Bogdanov, A., Cueto Noval, M., Hoffmann, C., & Rosen, A. (2022). Public-Key
Encryption from Homogeneous CLWE. In Theory of Cryptography (Vol. 13748,
pp. 565–592). Chicago, IL, United States: Springer Nature. https://doi.org/10.1007/978-3-031-22365-5_20'
chicago: Bogdanov, Andrej, Miguel Cueto Noval, Charlotte Hoffmann, and Alon Rosen.
“Public-Key Encryption from Homogeneous CLWE.” In Theory of Cryptography,
13748:565–92. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-22365-5_20.
ieee: A. Bogdanov, M. Cueto Noval, C. Hoffmann, and A. Rosen, “Public-Key Encryption
from Homogeneous CLWE,” in Theory of Cryptography, Chicago, IL, United
States, 2022, vol. 13748, pp. 565–592.
ista: 'Bogdanov A, Cueto Noval M, Hoffmann C, Rosen A. 2022. Public-Key Encryption
from Homogeneous CLWE. Theory of Cryptography. TCC: Theory of Cryptography, LNCS,
vol. 13748, 565–592.'
mla: Bogdanov, Andrej, et al. “Public-Key Encryption from Homogeneous CLWE.” Theory
of Cryptography, vol. 13748, Springer Nature, 2022, pp. 565–92, doi:10.1007/978-3-031-22365-5_20.
short: A. Bogdanov, M. Cueto Noval, C. Hoffmann, A. Rosen, in:, Theory of Cryptography,
Springer Nature, 2022, pp. 565–592.
conference:
end_date: 2022-11-10
location: Chicago, IL, United States
name: 'TCC: Theory of Cryptography'
start_date: 2022-11-07
corr_author: '1'
date_created: 2023-02-05T23:01:00Z
date_published: 2022-12-21T00:00:00Z
date_updated: 2024-10-09T21:04:05Z
day: '21'
department:
- _id: KrPi
doi: 10.1007/978-3-031-22365-5_20
external_id:
isi:
- '000921318200020'
intvolume: ' 13748'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2022/093
month: '12'
oa: 1
oa_version: Preprint
page: 565-592
publication: Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031223648'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Public-Key Encryption from Homogeneous CLWE
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13748
year: '2022'
...
---
_id: '11476'
abstract:
- lang: eng
text: "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.\r\n\r\nIn 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.\r\n\r\nIn 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].\r\n\r\nIn
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.\r\n\r\nThe
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.\r\n\r\nTo 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."
acknowledgement: We thank Marta Mularczyk and Yiannis Tselekounis for their very helpful
feedback on an earlier draft of this paper.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Joël
full_name: Alwen, Joël
last_name: Alwen
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
last_name: Walter
citation:
ama: 'Alwen J, Auerbach B, Cueto Noval M, et al. CoCoA: Concurrent continuous group
key agreement. In: Advances in Cryptology – EUROCRYPT 2022. Vol 13276.
Cham: Springer Nature; 2022:815–844. doi:10.1007/978-3-031-07085-3_28'
apa: 'Alwen, J., Auerbach, B., Cueto Noval, M., Klein, K., Pascual Perez, G., Pietrzak,
K. Z., & Walter, M. (2022). CoCoA: Concurrent continuous group key agreement.
In Advances in Cryptology – EUROCRYPT 2022 (Vol. 13276, pp. 815–844). Cham:
Springer Nature. https://doi.org/10.1007/978-3-031-07085-3_28'
chicago: 'Alwen, Joël, Benedikt Auerbach, Miguel Cueto Noval, Karen Klein, Guillermo
Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “CoCoA: Concurrent Continuous
Group Key Agreement.” In Advances in Cryptology – EUROCRYPT 2022, 13276:815–844.
Cham: Springer Nature, 2022. https://doi.org/10.1007/978-3-031-07085-3_28.'
ieee: 'J. Alwen et al., “CoCoA: Concurrent continuous group key agreement,”
in Advances in Cryptology – EUROCRYPT 2022, Trondheim, Norway, 2022, vol.
13276, pp. 815–844.'
ista: 'Alwen J, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ,
Walter M. 2022. CoCoA: Concurrent continuous group key agreement. Advances in
Cryptology – EUROCRYPT 2022. EUROCRYPT: Theory and Applications of Cryptology
and Information Security, LNCS, vol. 13276, 815–844.'
mla: 'Alwen, Joël, et al. “CoCoA: Concurrent Continuous Group Key Agreement.” Advances
in Cryptology – EUROCRYPT 2022, vol. 13276, Springer Nature, 2022, pp. 815–844,
doi:10.1007/978-3-031-07085-3_28.'
short: J. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak,
M. Walter, in:, Advances in Cryptology – EUROCRYPT 2022, Springer Nature, Cham,
2022, pp. 815–844.
conference:
end_date: 2022-06-03
location: Trondheim, Norway
name: 'EUROCRYPT: Theory and Applications of Cryptology and Information Security'
start_date: 2022-05-30
corr_author: '1'
date_created: 2022-06-30T16:48:00Z
date_published: 2022-05-25T00:00:00Z
date_updated: 2026-04-07T13:01:26Z
day: '25'
department:
- _id: GradSch
- _id: KrPi
doi: 10.1007/978-3-031-07085-3_28
ec_funded: 1
external_id:
isi:
- '000832305300028'
intvolume: ' 13276'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2022/251
month: '05'
oa: 1
oa_version: Preprint
page: 815–844
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication: Advances in Cryptology – EUROCRYPT 2022
publication_identifier:
eisbn:
- '9783031070853'
eissn:
- 1611-3349
isbn:
- '9783031070846'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '18088'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'CoCoA: Concurrent continuous group key agreement'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13276
year: '2022'
...
---
_id: '10408'
abstract:
- lang: eng
text: '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.'
acknowledgement: B. Auerbach, M.A. Baig and K. Pietrzak—received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020 research
and innovation programme (682815 - TOCNeT); Karen Klein was supported in part by
ERC CoG grant 724307 and conducted part of this work at IST Austria, funded by the
ERC under the European Union’s Horizon 2020 research and innovation programme (682815
- TOCNeT); Guillermo Pascual-Perez was funded by the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
No. 665385; Michael Walter conducted part of this work at IST Austria, funded by
the ERC under the European Union’s Horizon 2020 research and innovation programme
(682815 - TOCNeT).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management
for overlapping groups. In: 19th International Conference. Vol 13044. Springer
Nature; 2021:222-253. doi:10.1007/978-3-030-90456-2_8'
apa: 'Alwen, J. F., Auerbach, B., Baig, M. A., Cueto Noval, M., Klein, K., Pascual
Perez, G., … Walter, M. (2021). Grafting key trees: Efficient key management for
overlapping groups. In 19th International Conference (Vol. 13044, pp. 222–253).
Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90456-2_8'
chicago: 'Alwen, Joel F, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval,
Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter.
“Grafting Key Trees: Efficient Key Management for Overlapping Groups.” In 19th
International Conference, 13044:222–53. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90456-2_8.'
ieee: 'J. F. Alwen et al., “Grafting key trees: Efficient key management
for overlapping groups,” in 19th International Conference, Raleigh, NC,
United States, 2021, vol. 13044, pp. 222–253.'
ista: 'Alwen JF, Auerbach B, Baig MA, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak
KZ, Walter M. 2021. Grafting key trees: Efficient key management for overlapping
groups. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol.
13044, 222–253.'
mla: 'Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping
Groups.” 19th International Conference, vol. 13044, Springer Nature, 2021,
pp. 222–53, doi:10.1007/978-3-030-90456-2_8.'
short: J.F. Alwen, B. Auerbach, M.A. Baig, M. Cueto Noval, K. Klein, G. Pascual
Perez, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer
Nature, 2021, pp. 222–253.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography'
start_date: 2021-11-08
date_created: 2021-12-05T23:01:42Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2026-04-07T13:01:26Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90456-2_8
ec_funded: 1
external_id:
isi:
- '000728363700008'
intvolume: ' 13044'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1158
month: '11'
oa: 1
oa_version: Preprint
page: 222-253
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication: 19th International Conference
publication_identifier:
eisbn:
- 978-3-030-90456-2
eissn:
- 1611-3349
isbn:
- 9-783-0309-0455-5
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '18088'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'Grafting key trees: Efficient key management for overlapping groups'
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13044
year: '2021'
...
---
_id: '10049'
abstract:
- lang: eng
text: 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.
acknowledgement: The first three authors contributed equally to this work. Funded
by the European Research Council (ERC) under the European Union’s Horizon2020 research
and innovation programme (682815-TOCNeT). Funded by the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
No.665385.
article_processing_charge: No
author:
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Margarita
full_name: Capretto, Margarita
last_name: Capretto
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Ilia
full_name: Markov, Ilia
id: D0CF4148-C985-11E9-8066-0BDEE5697425
last_name: Markov
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM,
adaptively and actively secure continuous group key agreement. In: 2021 IEEE
Symposium on Security and Privacy . IEEE; 2021:268-284. doi:10.1109/sp40001.2021.00035'
apa: 'Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M.,
Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively
and actively secure continuous group key agreement. In 2021 IEEE Symposium
on Security and Privacy (pp. 268–284). San Francisco, CA, United States:
IEEE. https://doi.org/10.1109/sp40001.2021.00035'
chicago: 'Klein, Karen, Guillermo Pascual Perez, Michael Walter, Chethan Kamath
Hosdurg, Margarita Capretto, Miguel Cueto Noval, Ilia Markov, Michelle X Yeo,
Joel F Alwen, and Krzysztof Z Pietrzak. “Keep the Dirt: Tainted TreeKEM, Adaptively
and Actively Secure Continuous Group Key Agreement.” In 2021 IEEE Symposium
on Security and Privacy , 268–84. IEEE, 2021. https://doi.org/10.1109/sp40001.2021.00035.'
ieee: 'K. Klein et al., “Keep the dirt: tainted TreeKEM, adaptively and actively
secure continuous group key agreement,” in 2021 IEEE Symposium on Security
and Privacy , San Francisco, CA, United States, 2021, pp. 268–284.'
ista: 'Klein K, Pascual Perez G, Walter M, Kamath Hosdurg C, Capretto M, Cueto Noval
M, Markov I, Yeo MX, Alwen JF, Pietrzak KZ. 2021. Keep the dirt: tainted TreeKEM,
adaptively and actively secure continuous group key agreement. 2021 IEEE Symposium
on Security and Privacy . SP: Symposium on Security and Privacy, 268–284.'
mla: 'Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively
Secure Continuous Group Key Agreement.” 2021 IEEE Symposium on Security and
Privacy , IEEE, 2021, pp. 268–84, doi:10.1109/sp40001.2021.00035.'
short: K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M.
Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium
on Security and Privacy , IEEE, 2021, pp. 268–284.
conference:
end_date: 2021-05-27
location: San Francisco, CA, United States
name: 'SP: Symposium on Security and Privacy'
start_date: 2021-05-24
corr_author: '1'
date_created: 2021-09-27T13:46:27Z
date_published: 2021-08-26T00:00:00Z
date_updated: 2026-04-08T07:01:44Z
day: '26'
department:
- _id: KrPi
- _id: DaAl
doi: 10.1109/sp40001.2021.00035
ec_funded: 1
external_id:
isi:
- '001316065000016'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/1489
month: '08'
oa: 1
oa_version: Preprint
page: 268-284
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: '2021 IEEE Symposium on Security and Privacy '
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '18088'
relation: dissertation_contains
status: public
- id: '10035'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous
group key agreement'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2021'
...