Committed-programming reductions: formalizations, implications and relations

In this work, we introduce a class of black-box (BB) reductions called committed-programming reduction (CPRed) in the random oracle model (ROM) and obtain the following interesting results: (1) we demonstrate that some well-known schemes, including the full-domain hash (FDH) signature (Eurocrypt 1996) and the Boneh-Franklin identity-based encryption (IBE) scheme (Crypto 2001), are provably secure under CPReds; (2) we prove that a CPRed associated with an instance-extraction algorithm implies a reduction in the quantum ROM (QROM). This unifies several recent results, including the security of the Gentry-Peikert-Vaikuntanathan IBE scheme by Zhandry (Crypto 2012) and the key encapsulation mechanism (KEM) variants using the Fujisaki-Okamoto transform by Jiang et al. (Crypto 2018) in the QROM. Finally, we show that CPReds are incomparable to non-programming reductions (NPReds) and randomly-programming reductions (RPReds) formalized by Fischlin et al. (Asiacrypt 2010).