Both the formal and computational models of cryptography contain the notion of message equivalence or indistinguishability. When can we say that two equivalent formal messages are mapped into two indistinguishable computational distributions? I.e., when is an encryption scheme sound? So far, none of the existing soundness results holds when the graph of encryption keys of one of the messages is cyclic. In this talk we will see that an encryption scheme provides soundness in the presence of key cycles if it also satisfies the recently-introduced notion of key-dependent message (KDM) security. We also show that soundness in the presence of key-cycles (and KDM security) neither implies nor is implied by the "usual" notions of security, namely chosen ciphertext security (CCA-2). Therefore, soundness for key-cycles is only possible using new notions of security. This talk is joint work with G. Bana, J. Herzog and A. Scedrov.