Soundness of Formal Encryption in the Presence of Key-Cycles (joint work with Gergei Bana, Jonathan Herzog and Andre Scedrov)
In S. De Capitani di Vimercati, P. Syverson, and D. Gollmann, editors, 10th European Symposium on Research in Computer Security (ESORICS), volume 3679 of LNCS, pages 374-396, Milan, Italy, September 12-14 2005. © Springer.

Abstract: Both the formal and the computational models of cryptography contain the notion of message equivalence or indistinguishability. An encryption scheme provides soundness for indistinguishability if, when mapping formal messages into the computational model, equivalent formal messages are mapped to indistinguishable computational distributions. Previous soundness results are limited in that they do not apply when key-cycles are present. We demonstrate that an encryption scheme provides soundness in the presence of key-cycles if it 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 security against chosen ciphertext attack (CCA-2). Therefore, soundness for key-cycles is possible using a new notion of computational security, not possible using previous such notions, and the relationship between the formal and computational models extends beyond chosen-ciphertext security.

Date: 04 April 2005, last revised 06 July 2005.

Get a preprint: PDF | PS | BibTeX Citation.
Get it from the publisher's website.