Post-quantum signature with preimage chameleon hashing

In this work, we propose a generalization of the concept of chameleon hash first described in [Krawczyk and Rabin 1998], which we call preimage chameleon hash. While in the conventional chameleon hash, the trapdoor allows a user to compute second preimages, in this generalization, it is possible to compute first preimages. We show how to adapt the post-quantum chameleon hash from [Cash et al. 2010] to a preimage chameleon hash and use this modified construction to build a new signature scheme based on [Mohassel 2011]. A preimage chameleon hash allows the signer to encode in its signature chosen information to be checked during verification. We prove our signature scheme to be strongly unforgeable under a chosen message attack (SUF-CMA).