Modeling Computational Security in Long-Lived Systems, Version 2
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 l...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Published: |
2008
|
| Online Access: | http://hdl.handle.net/1721.1/43711 |
| _version_ | 1826202816685801472 |
|---|---|
| author | Lynch, Nancy Pereira, Olivier Kaynar, Dilsun Cheung, Ling Canetti, Ran |
| author2 | Nancy Lynch |
| author_facet | Nancy Lynch Lynch, Nancy Pereira, Olivier Kaynar, Dilsun Cheung, Ling Canetti, Ran |
| author_sort | Lynch, Nancy |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T12:19:49Z |
| id | mit-1721.1/43711 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T12:19:49Z |
| publishDate | 2008 |
| record_format | dspace |
| spelling | mit-1721.1/437112019-04-12T09:57:48Z Modeling Computational Security in Long-Lived Systems, Version 2 Lynch, Nancy Pereira, Olivier Kaynar, Dilsun Cheung, Ling Canetti, Ran Nancy Lynch Theory of Computation 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. 2008-11-24T06:00:04Z 2008-11-24T06:00:04Z 2008-11-22 http://hdl.handle.net/1721.1/43711 MIT-CSAIL-TR-2008-068 27 p. application/pdf application/postscript |
| spellingShingle | Lynch, Nancy Pereira, Olivier Kaynar, Dilsun Cheung, Ling Canetti, Ran Modeling Computational Security in Long-Lived Systems, Version 2 |
| title | Modeling Computational Security in Long-Lived Systems, Version 2 |
| title_full | Modeling Computational Security in Long-Lived Systems, Version 2 |
| title_fullStr | Modeling Computational Security in Long-Lived Systems, Version 2 |
| title_full_unstemmed | Modeling Computational Security in Long-Lived Systems, Version 2 |
| title_short | Modeling Computational Security in Long-Lived Systems, Version 2 |
| title_sort | modeling computational security in long lived systems version 2 |
| url | http://hdl.handle.net/1721.1/43711 |
| work_keys_str_mv | AT lynchnancy modelingcomputationalsecurityinlonglivedsystemsversion2 AT pereiraolivier modelingcomputationalsecurityinlonglivedsystemsversion2 AT kaynardilsun modelingcomputationalsecurityinlonglivedsystemsversion2 AT cheungling modelingcomputationalsecurityinlonglivedsystemsversion2 AT canettiran modelingcomputationalsecurityinlonglivedsystemsversion2 |