Anonymous protocols: Notions and equivalence

Privacy protection has become a major issue in modern societies. Many efforts have been provided in the last years to catch properly the requirements that cryptographic primitives and low-level protocols should meet in order to be useful for building privacy-preserving applications. In particular, anonymity is an important property to achieve, and the notion of key privacy in public-key encryption, which guarantees that an adversary is unable to tell with which public key a certain ciphertext has been produced, plays a key-role in the design of anonymous protocols.Secret sets and anonymous broadcast encryption are two examples of useful anonymous protocols. A secret set is a representation of a subset of users of a given universe satisfying some basic membership privacy properties, and anonymous broadcast encryption is a mechanism to encrypt a broadcast message that only authorized users, whose identities are kept secret, can decrypt.In this paper we show that, even if apparently the key privacy property of an encryption scheme seems to be unrelated to the security of the encrypted content, and it looks like just an additional property the encryption scheme can enjoy, for a robust encryption scheme key privacy under chosen ciphertext attack implies non-malleability and, hence, security under chosen ciphertext attacks. This result helps to simplify the set of requirements that public key encryption schemes need to satisfy when stating and proving theorems regarding anonymous protocols in which the encryption schemes are used.Then, we provide a formal model for both secret sets and anonymous broadcast encryption and we prove that they are equivalent with respect to non-adaptive adversaries: the former can be used to design the latter and vice versa.Finally, we revisit some previous constructions for secret sets, and we analyze the security properties they enjoy within our adversarial model.