Paper 2022/156

Universal Reductions: Reductions Relative to Stateful Oracles

Benjamin Chan
Cody Freitag
Rafael Pass

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.

Available format(s)
Publication info
reductions provable security rewinding
Contact author(s)
byc @ cs cornell edu
cfreitag @ cs cornell edu
rafael @ cs cornell edu
2022-09-19: last of 2 revisions
2022-02-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benjamin Chan and Cody Freitag and Rafael Pass},
      title = {Universal Reductions: Reductions Relative to Stateful Oracles},
      howpublished = {Cryptology ePrint Archive, Paper 2022/156},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.