## CryptoDB

### Paper: Universal Reductions: Reductions Relative to Stateful Oracles

Authors: Benjamin Chan , Cornell Tech Cody Freitag , Cornell Tech Rafael Pass , Cornell Tech and Tel-Aviv University Search ePrint Search Google Slides TCC 2022 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 \emph{universal reductions} models attackers as PPT algorithms having access to some arbitrary unbounded \emph{stateful} Nature that cannot be rewound or restarted when queried multiple times. We also consider a more relaxed notion of \emph{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(\sec)$-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.
##### BibTeX
@inproceedings{tcc-2022-32520,
title={Universal Reductions: Reductions Relative to Stateful Oracles},
publisher={Springer-Verlag},
author={Benjamin Chan and Cody Freitag and Rafael Pass},
year=2022
}