Complete non-malleability from strong chosen-ciphertext security
Manuel Barbosa
Departamento de Informática
Universidade do Minho

Resumo

In this talk we establish a connection between two strong variants of standard security notions for public-key encryption schemes: indistinguishability under strong chosen-ciphertext attacks and complete non-malleability. Strong chosen-ciphertext attacks model adversaries who can maliciously replace public keys of users and subse- quently ask for decryptions under unknown secret keys. We give the first precise definition of a strong decryption oracle, pointing out the subtleties in alternative approaches that can be taken. In particular, we specify how to deal with invalid ciphertext and/or public keys and the inherent ambiguity in the message that the oracle should return. We extend indistinguishability of ciphertexts, comparison-based non-malleability and simulation non-malleability under various attack models to allow strong decryption queries. We show that the known relations for the stan- dard versions of these definitions naturally extend to their stronger versions. We examine the relation between our new definitions of non-malleability and the notion of complete non-malleability introduced by Fischlin (ICALP 05) and by Ventre and Visconti (PKC 2008). We conclude that they can be seen as alternative formulations of complete non-malleability. Furthermore, our discussion reveals that two different decryption oracle definitions co- exist in the original formulations, which makes them hard to relate to standard notions of security for encryption schemes. Finally, our characterisation of non-malleability via indistinguishability allows us to construct a practical scheme which is secure against strong chosen-ciphertext attacks in the standard model, and therefore completely non-malleable. We also discuss the apparent contradiction between the existence of our construction and Fischlin’s impossibility results for completely non-malleable schemes.

Encontro Matemático SPM/CIM em Teoria da Codificação, Informação e Criptografia