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