### 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.

Available format(s)
Category
Foundations
Publication info
Preprint.
Keywords
reductions provable security rewinding
Contact author(s)
byc @ cs cornell edu
cfreitag @ cs cornell edu
rafael @ cs cornell edu
History
2022-09-19: last of 2 revisions
See all versions
Short URL
https://ia.cr/2022/156

CC BY

BibTeX

@misc{cryptoeprint:2022/156,
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{https://eprint.iacr.org/2022/156}},
url = {https://eprint.iacr.org/2022/156}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.