Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Canetti, Ran; Cheung, Ling; Kaynar, Dilsun; Lynch, Nancy; Pereira, Olivier License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-18908

; ; ; ;

Modeling Computational Security in Long-Lived Systems



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 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.

BibTeX - Entry

  author =	{Ran Canetti and Ling Cheung and Dilsun Kaynar and Nancy Lynch and Olivier Pereira},
  title =	{Modeling Computational Security in Long-Lived Systems},
  booktitle =	{Theoretical Foundations of Practical Information Security},
  year =	{2009},
  editor =	{Ran Canetti and Shafi Goldwasser and G{\"u}nter M{\"u}ller and Rainer Steinwandt},
  number =	{08491},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Long lived security; universally composable security;}

Keywords: Long lived security; universally composable security;
Seminar: 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