License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.08491.3
URN: urn:nbn:de:0030-drops-18908
Go to the corresponding Portal

Canetti, Ran ; Cheung, Ling ; Kaynar, Dilsun ; Lynch, Nancy ; Pereira, Olivier

Modeling Computational Security in Long-Lived Systems

08491.PereiraOlivier.Paper.1890.pdf (0.3 MB)


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 emph{long-lived} in nature; they are expected to be
secure and operational for a very long time (ie 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 emph{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 emph{long-term implementation}, which is an
adaptation of computational indistinguishability to the long-lived
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.

BibTeX - Entry

  author =	{Canetti, Ran and Cheung, Ling and Kaynar, Dilsun and Lynch, Nancy and Pereira, Olivier},
  title =	{{Modeling Computational Security in Long-Lived Systems}},
  booktitle =	{Theoretical Foundations of Practical Information Security},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8491},
  editor =	{Ran Canetti and Shafi Goldwasser and G\"{u}nter M\"{u}ller and Rainer Steinwandt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-18908},
  doi =		{10.4230/DagSemProc.08491.3},
  annote =	{Keywords: Long lived security; universally composable security;}

Keywords: Long lived security; universally composable security;
Collection: 08491 - Theoretical Foundations of Practical Information Security
Issue Date: 2009
Date of publication: 27.02.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI