Does non-malleability really imply indistinguishability?

摘要

Two formalizations of non-malleability of public-key cryptosystems named non-malleability for an exponential domain and non-malleability for a polynomial domain are presented. The difference between the two is on the size of the message space from which an encryption oracle chooses the message underlying challenge ciphertext. NM-ATK of Bellare et al. corresponds to non-malleability for a polynomial domain. Through discussion on one-wayness for both domains, we see that formalizations for a polynomial domain including NM-ATK of Bellare et al. are rather odd and unnatural. Relations among the new and old formalizations including indistinguishability are also discussed.