Public-Key Encryption in a Multi-user Setting: Security Proofs and Improvements

This paper addresses the security of public-key cryptosystems in a "multi-user" setting, namely in the presence of attacks involv-ing the encryption of related messages under different public keys, as exemplified by Hºastad'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ºastad-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