Programmable Hash Functions and Their Applications
The authors introduce a new combinatorial primitive called Programmable Hash Functions (PHFs). PHFs can be used to program the output of a hash function such that it contains solved or unsolved discrete logarithm instances with a certain probability. This is a technique originally used for security proofs in the random oracle model. They give a variety of standard model realizations of PHFs (with different parameters). The programmability makes PHFs a suitable tool to obtain black-box proofs of cryptographic protocols when considering adaptive attacks. They propose generic digital signature schemes from the strong RSA problem and from some hardness assumption on bilinear maps that can be instantiated with any PHF. The schemes offer various improvements over known constructions.