Cryptology ePrint Archive: Report 2006/486

Inductive Trace Properties for Computational Security

Arnab Roy and Anupam Datta and Ante Derek and John C. Mitchell

Abstract: Protocol authentication properties are generally trace-based, meaning that authentication holds for the protocol if authentication holds for individual traces (runs of the protocol and adversary). Computational secrecy conditions, on the other hand, often are not trace based: the ability to computationally distinguish a system that transmits a secret from one that does not is measured by overall success on the \textit{set} of all traces of each system. This presents a challenge for inductive or compositional methods: induction is a natural way of reasoning about traces of a system, but it does not appear applicable to non-trace properties. We therefore investigate the semantic connection between trace properties that could be established by induction and non-trace-based security requirements. Specifically, we prove that a certain trace property implies computational secrecy and authentication properties, assuming the encryption scheme provides chosen ciphertext security and ciphertext integrity. We also prove a similar theorem for computational secrecy assuming Decisional Diffie-Hellman and a chosen plaintext secure encryption scheme.

Category / Keywords: cryptographic protocols /

Publication Info: Manuscript

Date: received 27 Dec 2006

Contact author: arnab at stanford edu

Available format(s): PDF | BibTeX Citation

Version: 20061229:203945 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]