Computational and Information-Theoretic Soundness and Completeness of Formal Encryption (joint work with Gergei Bana and Andre Scedrov)
In 18th IEEE Computer Security Foundations Workshop (CSFW), pages 170-184, Aix-en-Provence, France, June 20-22 2005. © IEEE Computer Society Press.

Abstract: We consider expansions of the Abadi-Rogaway logic of indistinguishability of formal cryptographic expressions. We expand the logic in order to cover cases when partial information of the encrypted plaintext is revealed. We consider not only computational, but also purely probabilistic, information-theoretic interpretations. We present a general, systematic treatment of the expansions of the logic for symmetric encryption. We establish general soundness and completeness theorems for the interpretations. We also present applications to specific settings not covered in earlier works: a purely probabilistic one based on One-Time Pad, and computational settings of the so-called type-2 (which-key revealing) and type-3 (which-key and length revealing) encryption schemes based on computational complexity.

Date: 01 February 2005, last revised 05 April 2005.

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