Paper 2022/156
Cosmic Security
Benjamin Chan and Cody Freitag and Rafael Pass
Abstract
We define a framework for analyzing the security of cryptographic protocols that makes minimal assumptions about what a "realistic model of computation is". In particular, whereas classical models assume that the attacker is a (perhaps non-uniform) probabilistic polynomial-time algorithm, and more recent definitional approaches also consider quantum polynomial-time algorithms, we consider an approach that is more agnostic to what computational model is physically realizable. Our notion of cosmic security considers a reduction-based notion of security that models attackers as arbitrary unbounded stateful algorithms; we also consider a more relaxed notion of cosmic security w.r.t. weakly-restartable adversaries which makes additional restrictions on the attacker’s behavior. We present both impossibility results and general feasibility results for our notions, indicating that extended Church-Turing hypotheses may not be needed for a well-founded theory of Cryptography.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- reductionsprovable securityrewinding
- Contact author(s)
- byc @ cs cornell edu,cfreitag @ cs cornell edu,rafael @ cs cornell edu
- History
- 2022-09-19: last of 2 revisions
- 2022-02-12: received
- See all versions
- Short URL
- https://ia.cr/2022/156
- License
-
CC BY