Group chat encryption in practice generally relies on symmetric cryptography to encrypt messages, and digital signatures so that users can authenticate as having sent a given message. This template forms the basis of many group chat encryption schemes in practice including MLS, Signal and Keybase, and has been abstracted as symmetric signcryption and explored in a fruitful line of recent work (Jaeger, Kumar and Stepanovs, Eurocrypt'24; Jaeger and Kumar, Eurocrypt'25). Although practical messengers like Signal claim to provide deniability for users, this has not been analysed on the chat encryption level. Therefore, in this work, we define and explore the deniability of symmetric signcryption. Deniability is unavoidably lost, however, if the adversary learns the group key, which is a significant limitation, especially in large groups.
Motivated by this limitation, we make the following contributions to characterise the practicality of strongly-deniable group chat encryption: - We introduce the extended symmetric signcryption primitive that allows public key pairs in its syntax and therefore provides stronger deniability, and construct it from symmetric encryption and multi-designated verifier signatures (MDVS) secure under strong security notions stemming from Damgård et al. (TCC'20). - Although signatures must grow linearly in size, previous MDVS constructions were impractical even for small groups. Therefore, we provide two new MDVS constructions. The first is based on DDH and is concretely efficient. The second is based on indistinguishability obfuscation and is the first construction for which signatures grow in the number of users that are allowed to be corrupted in the deniability game, which could be significantly smaller than the size of the group. The only other known construction with this property is from Damgard et al. (TCC'20) which relies on functional encryption and thus requires a master secret key, which is impractical for group messaging. - We revisit the Public Key Encryption for Broadcast (PKEBC) primitive introduced by Maurer et al. at Eurocrypt'22 used to construct deniable public-key encryption. In PKEBC, the set of public keys the sender encrypts to is output during decryption, and therefore ciphertexts grow linearly in size. We provide an information-theoretic argument to show that ciphertexts must grow linearly even if we do not require public keys to be output upon decryption. This negative result further motivates the use of symmetric encryption in group messaging.
Ongoing work with Wonseok Choi, Joseph Jaeger, Akshaya Kumar, Xiangyu Liu and Vassilis Zikas.
Daniel Collins is a postdoctoral researcher working with Juan Garay and Vassilis Zikas, currently at Texas A&M University and previously at Georgia Tech and Purdue University. His work focuses on cryptography and particularly on secure messaging systems and distributed protocol design. In secure messaging, Daniel has modelled real-world protocols used by billions in practice, designed new protocols and explored the foundations of secure communication. In distributed protocols, he has worked on reducing the cost of solving tasks like consensus, broadcast and multi-party computation, and on designing protocols that provide guarantees when parties experience severe network and adversarial behaviour. Daniel completed his PhD in 2024 at EPFL in Switzerland under Serge Vaudenay's supervision and was awarded a Thesis Distinction by the school. Before that, he received a Bachelors in Computer Science and Mathematics from the University of Sydney and was awarded the University Medal for his Honours thesis.