Multi-Recipient Encryption Schemes: Security Notions and Randomness Re-Use

Authors: M. Bellare, A. Boldyreva and J. Staddon

Abstract: This paper begins by refining Kurosawa's definitions of security for multi-recipient encryption schemes (MRESs). It then considers a subclass of MRESs, that are formed by transforming standard encryption schemes via a natural technique called randomness re-use, and that offer important performance benefits. The main result is a way to avoid ad-hoc analyses of such schemes: we provide a general test that can be applied to a standard encryption scheme to determine whether the associated randomness re-using MRES is secure. This is applied to identify numerous specific secure and efficient randomness re-using MRESs. The results and applications cover both asymmetric and symmetric encryption.

Ref: A preliminary version of this paper, entitled `` Randomness re-use in multi-recipient encryption schemes,'' appeared in Public Key Cryptography -- PKC 2003, Lecture Notes in Computer Science Vol. 2567, Y. Desmedt ed, Springer-Verlag, 2003. Full paper available below.

Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).