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 / Date: received 23 Nov 2008 Contact author: olivier pereira at uclouvain be Available formats: PDF | BibTeX Citation Note: This paper revisits the work on long-lived security posted as report 2007/406 (of which an extended abstract appeared at CONCUR 2008), adopting a conditional-probability-based approach. Version: 20081124:165427 (All versions of this report) Discussion forum: Show discussion | Start new discussion