Soundness and completeness of formal encryption: The cases of key cycles and partial information leakage

Abstract

In their seminal work, Abadi and Rogaway show that the formal (Dolev–Yao) notion of indistinguishability is sound with respect to the computational model: messages that are indistinguishable in the formal model become indistinguishable messages in the computational model. However, this result leaves two problems unsolved. First, it cannot tolerate key cycles. Second, it makes the too-strong assumption that the underlying cryptography hides all aspects of the plaintext, including its length. In this paper we extend their work in order to address these problems.

We show that the recently-introduced notion of KDM-security can provide soundness even in the presence of key cycles. For this, we have to consider encryption that reveals the length of plaintexts, which we use to motivate a general examination information-leaking encryption. In particular, we consider the conditions under which an encryption scheme that may leak some partial information will provide soundness and completeness to some (possibly weakened) version of the formal model.