Cryptology ePrint Archive: Report 2007/406

Modeling Computational Security in Long-Lived Systems

Ran Canetti and Ling Cheung and Dilsun Kaynar and Nancy Lynch and Olivier Pereira

Abstract: For many cryptographic protocols, security relies on the assumption that adversarial entities have limited computational power. This type of security degrades progressively over the lifetime of a protocol. However, some cryptographic services, such as timestamping services or digital archives, are long-lived in nature; they are expected to be secure and operational for a very long time (i.e., super-polynomial). In such cases, security cannot be guaranteed in the traditional sense: a computationally secure protocol may become insecure if the attacker has a super-polynomial number of interactions with the protocol.

This paper proposes a new paradigm for the analysis of long-lived security protocols. We allow entities to be active for a potentially unbounded amount of real time, provided they perform only a polynomial amount of work per unit of real time. Moreover, the space used by these entities is allocated dynamically and must be polynomially bounded. We propose a new notion of long-term implementation, which is an adaptation of computational indistinguishability to the long-lived setting. We show that long-term implementation is preserved under polynomial parallel composition and exponential sequential composition. We illustrate the use of this new paradigm by analyzing some security properties of the long-lived timestamping protocol of Haber and Kamat.

Category / Keywords: foundations /

Publication Info: An abstract of this paper will appear at CONCUR 08.

Date: received 24 Oct 2007, last revised 26 Jun 2008

Contact author: olivier pereira at uclouvain be

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20080626:083003 (All versions of this report)

Discussion forum: Show discussion | Start new discussion