Multirecipient encryption schemes: How to save on bandwidth and computation without sacrificing security

This paper proposes several new schemes which allow a sender to send encrypted messages to multiple recipients more efficiently (in terms of bandwidth and computation) than by using a standard encryption scheme. Most of the proposed schemes explore a new natural technique called randomness reuse. In order to analyze security of our constructions, we introduce a new notion of multirecipient encryption schemes (MRESs) and provide definitions of security for them. We finally show a way to avoid ad hoc analyses by providing a general test that can be applied to a standard encryption scheme to determine whether the associated randomness reusing MRES is secure. The results and applications cover both asymmetric and symmetric encryption.