Committed-programming reductions: formalizations, implications and relations

Jiang Zhang

doi:10.1007/s11432-022-3893-3

Committed-programming reductions: formalizations, implications and relations

2024-09-26

0

PRE

AI

DOI：10.1007/s11432-022-3893-3

Original

Original request for help

Save

Abstract

En 中文

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

Keywords:

provable security

random oracle model

quantum random oracle model

black-box reduction/separation

programmability

Committed-programming reductions: formalizations, implications and relations

Abstract

Journal

Organization