Abstract

In this paper we show that standard model black-box reduc-tions naturally lift to various setup assumptions, such as random oracle(ROM) or ideal cipher model. Concretely, we prove that a black-boxreduction from a security notion P to security notion Q in the standard model can be turned into a non-programmable black-box reduction fromPOtoQOin a model with a the setup assumption O, where P_O and Q_O are the natural extensions of P and Q to a model with setup assumption O. Our results rely on a generalization of the recent framework by Hofheinz and Nguyen (PKC 2019) to support primitives which make use of atrusted setup. Our framework encompasses standard idealized settings like the random oracle and the ideal cipher model. At the core of ourmain result lie novel properties of negligible functions that can be ofindependent interest.