Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / reductions; provable security; rewinding

Date: received 10 Feb 2022

Contact author: byc at cs cornell edu, cfreitag at cs cornell edu, rafael at cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20220212:065123 (All versions of this report)

Short URL: ia.cr/2022/156