Soundness and Completeness of Formal Encryption: the Cases of Key-Cycles and Partial Information Leakage
| Title | Soundness and Completeness of Formal Encryption: the Cases of Key-Cycles and Partial Information Leakage |
| Publication Type | Journal Article |
| Year of Publication | 2009 |
| Authors | Adao, Pedro, Gergei Bana, Jonathan Herzog, and Andre Scedrov |
| Journal | Journal of Computer Security |
| Volume | 7 |
| Issue | 5 |
| Pagination | 737-797 |
| 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. |
| URL | http://files.jonathanherzog.com/adao_soundness.pdf |
| DOI | 10.3233/JCS-2009-0358 |
