Multi-Recipient Encryption Schemes: Efficient Constructions and Their 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 re-use. In order to analyze security of the constructions They introduce a new notion of Multi-Recipient Encryption Schemes (MRESs) and provide definitions of security for them. The authors 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 re-using MRES is secure. The results and applications cover both asymmetric and symmetric encryption