Black-box separations of hash-and-sign signatures in the non-programmable random oracle model

A popular methodology of designing cryptosystems with practical efficiency is to give a security proof in the random oracle (RO) model. The work of Fischlin and Fleischhacker (Eurocrypt’13) investigated the case of Schnorr signature (and generally, Fiat-Shamir signatures) and showed the reliance of RO model is inherent. We generalize their results to a large class of “malleable” hash-andsign signatures, where one can efficiently “maul”any two valid signatures between two signature instances with different public keys if it can get the difference between the secret keys.We follow the technique of Fischlin and Fleischhacker to show that the security of malleable hash-and-sign signature cannot be reduced to its related hard cryptographic problem without programming the RO. Our proof assumes the hardness of a onemore cryptographic problem (depending on the signature instantiation). Our result applies to single-instance black-box reductions, subsuming those reductions used in existing proofs. Our framework not only encompasses Fiat-Shamir signatures as special cases, but also covers Γ-signature (Yao and Zhao, IEEE Transactions on Information Forensics and Security’13), and other schemes which implicitly used malleable hash-and-sign signatures, including Boneh-Franklin identity-based encryption, and Sakai-Ohgishi-Kasahara non-interactive identity-based key exchange.