Portal de Periódicos da CAPES

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

2000; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-45539-6_18

1611-3349

Mihir Bellare, Alexandra Boldyreva, Silvio Micali,

Coding theory and cryptography

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 Håstad’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å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.