Public-key encryption in the multi-user setting: privacy, anonymity and efficiency
Alexandra Boldyreva, Mihir Bellare · 2004
Encryption protocols are used to privately transmit data over insecure channels. Despite the fact that in reality there are many users of encryption protocols, security of encryption has been traditionally analyzed in the single-user setting, where only a single recipient of encrypted data is considered. This dissertation studies various aspects of encryption in the realistic multi-user setting. First, we answer the crucial question of whether popular protocols provide data-privacy in the multi-user setting. We provide a model for analyzing data-privacy security in this setting and prove that even though, in general, the exact security degrades as the number of users and encrypted messages increases, polynomial security in the single-user setting is preserved in the multi-user setting, as long as the former is interpreted in the strong sense of “indistinguishability”. We then highlight the practical importance of considering and achieving better concrete security, and present improved concrete security results for two popular schemes, namely ElGamal and Cramer-Shoup. Next we propose several new schemes that allow a sender to send encrypted messages to multiple recipients more efficiently (in terms of bandwidth and computation) than by using a conventional encryption scheme in the straight-forward way. Most of the proposed schemes explore a new technique called randomness re-use: for many encryption schemes we suggest the re-use of random coins tin the computation of ciphertexts encrypted under different keys. To analyze security of our constructions we introduce a new primitive, multi-recipient encryption scheme (MRES), and provide definitions of security for it. We show a way to avoid ad-hoc security analyses of randomness re-using MRESs (RR-MRESs) by providing a general test that is applied to easily identify numerous specific secure and efficient RR-MRESs. These include the ElGamal and the Cramer-Shoup-based RR-MRESs. Originally, hiding data was considered to be the only goal of encryption. However, the emerging concerns about users' privacy rights in the digital world highlighted the importance of another property, namely, hiding the identities of intended recipients of encrypted data. We study this property of encryption in the multi-user setting, which we call “anonymity” or “key-privacy”. We investigate the anonymity of existing public-key encryption schemes, which are known to provide data-privacy. We provide an appropriate security model and prove that under wildly believed assumptions the ElGamal and the Cramer-Shoup scheme provide anonymity. Our results cover both asymmetric and symmetric-key settings.