Paper 2022/156

Universal Reductions: Reductions Relative to Stateful Oracles

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 universal reductions models attackers as PPT algorithms having access to some arbitrary unbounded stateful Nature that cannot be rewound or restarted when queried multiple times. We also consider a more relaxed notion of universal reductions w.r.t. time-evolving, $k$-window, Natures that makes restrictions on Nature - roughly speaking, Nature's behavior may depend on number of messages it has received and the content of the last $k(\lambda)$-messages (but not on "older" messages). We present both impossibility results and general feasibility results for our notions, indicating to what extent the extended Church-Turing hypotheses are needed for a well-founded theory of Cryptography.