Committed-programming reductions:formalizations,implications and relations  

作　　者：Jiang ZHANG Yu YU Dengguo FENG Shuqin FAN Zhenfeng ZHANG 

机构地区：[1]State Key Laboratory of Cryptology,Beijing 100878,China [2]Department of Computer Science and Engineering,Shanghai Jiao Tong University,Shanghai 200240,China [3]Trusted Computing and Information Assurance Laboratory,Institute of Software,Chinese Academy of Sciences,Beijing 100190,China

出　　处：《Science China(Information Sciences)》2024年第10期147-167,共21页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant Nos.62022018,61932019);supported by National Natural Science Foundation of China(Grant Nos.62125204,92270201);National Key Research and Development Program of China(Grant No.2022YFB2702000);National Key Research and Development Program of China(Grant No.2018YFA0704701);Major Program of Guangdong Basic and Applied Research(Grant No.2019B030302008);the support from the XPLORER PRIZE。

摘　　要：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(Eurocrypt1996)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).

关 键 词：provable security random oracle model quantum random oracle model black-box reduction/separation PROGRAMMABILITY 

分 类 号：O413[理学—理论物理] TN918.4[理学—物理]