A multi-designated verifier signature (MDVS) is a digital signature that empowers a signer to designate specific verifiers capable of verifying signatures. Notably, designated verifiers are allowed to not only verify signatures but also simulate “fake” signatures indistinguishable from real ones produced by the original signer. Since this property is useful for realizing off-the-record (i.e., deniable) communication in group settings, MDVS is attracting attention in secure messaging. Recently, Damgård et al. (TCC'20) and Chakraborty et al. (EUROCRYPT'23) have introduced new MDVS schemes, allowing a subset of designated verifiers to simulate signatures in contrast to the conventional one, which requires all designated verifiers for signature simulation. They also define a stronger notion of security for them. This work delves into this new MDVS and offers a comprehensive formalization. We identify all possible security levels of MDVS schemes in subset simulations and prove that some of them are not feasible. Furthermore, we demonstrate that MDVS schemes meeting the security notion defined by Chakraborty et al. imply IND-CCA secure public-key encryption schemes. Beyond formalization, we present new constructions of MDVS schemes in subset simulation. Notably, we introduce a new construction of strongly secure MDVS schemes based on ring signatures and public-key encryption, accompanied by a generic conversion for achieving consistency through non-interactive zero-knowledge arguments. Finally, we evaluate the efficiency of our MDVS schemes in classical and post-quantum settings, showing their practicality.

Abstract Threshold public-key encryption (threshold PKE) has various useful applications. A lot of threshold PKE schemes are proposed based on RSA, Diffie–Hellman and lattice, but to the best of our knowledge, code-based threshold PKEs have not been proposed. In this paper, we provide three IND-CCA secure code-based threshold PKE schemes. The first scheme is the concrete instantiation of Dodis–Katz conversion (Dodis and Katz, TCC’05) that converts an IND-CCA secure PKE into an IND-CCA secure threshold PKE using parallel encryption and a signature scheme. This approach provides non-interactive threshold decryption, but ciphertexts are large (about 16 kilobytes for 128-bit security) due to long code-based signatures even in the state-of-the-art one. The second scheme is a new parallel encryption-based construction without signature schemes. Unlike the Dodis–Katz conversion, our parallel encryption converts an OW-CPA secure PKE into an OW-CPA secure threshold PKE. To enhance security, we use Cong et al.’s conversion (Cong et al., ASIACRYPT’21). Thanks to eliminating signatures, its ciphertext is 512 bytes, which is only 3% of the first scheme. The decryption process needs an MPC for computing hash functions, but decryption of OW-CPA secure PKE can be done locally. The third scheme is an MPC-based threshold PKE scheme from code-based assumption. We take the same approach Cong et al. took to construct efficient lattice-based threshold PKEs. We build an MPC for the decryption algorithm of OW-CPA secure Classic McEliece PKE. This scheme has the shortest ciphertext among the three schemes at just 192 bytes. Compared to the regular CCA secure Classic McEliece PKE, the additional ciphertext length is only 100 bytes. The cons are heavy distributed computation in the decryption process.

Secure group messaging (SGM) protocols allow large groups of users to communicate in a secure and asynchronous manner. In recent years, continuous group key agreements (CGKAs) have provided a powerful abstraction to reason on the security properties we expect from SGM protocols. While robust techniques have been developed to protect the contents of conversations in this context, it is in general more challenging to protect metadata (e.g. the identity and social relationships of group members), since their knowledge is often needed by the server in order to ensure the proper function of the SGM protocol.

Continuous group key agreements (CGKAs) are a class of protocols that can provide strong security guarantees to secure group messaging protocols such as Signal and MLS. Protection against device compromise is provided by commit messages: at a regular rate, each group member may refresh their key material by uploading a commit message, which is then downloaded and processed by all the other members. In practice, propagating commit messages dominates the bandwidth consumption of existing CGKAs.