Public-key Encryption in a Multi-User Setting: Security Proofs and Improvements

Authors: M. Bellare, A. Boldyreva and S. Micali

Abstract: This paper addresses the security of public-key cryptosystems in a ``multi-user'' setting, namely in the presence of attacks involving the encryption of related messages under different public keys, as exemplified by Hastad's classical attacks on RSA. We prove that security in the single-user setting implies security in the multi-user setting as long as the former is interpreted in the strong sense of ``indistinguishability,'' thereby pin-pointing many schemes guaranteed to be secure against H{\aa}stad-type attacks. We then highlight the importance, in practice, of considering and improving the concrete security of the general reduction, and present such improvements for two Diffie-Hellman based schemes, namely El Gamal and Cramer-Shoup.

Ref: Extended abstract in Advances in Cryptology - Eurocrypt 2000 Proceedings, Lecture Notes in Computer Science Vol. 1807, B. Preneel ed, Springer-Verlag, 2000. Full paper available below.

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