Unique Signatures and Verifiable Random Functions from the DH-DDH Separation

A unique signature scheme has the property that a signature σ _PK (m) is a (hard-to-compute) function of the public key PK and message m, for all, even adversarially chosen, PK. Unique signatures, introduced by Goldwasser and Ostrovsky, have been shown to be a building block for constructing verifiable random functions. Another useful property of unique signatures is that they are stateless: the signer does not need to update his secret key after an invocation.The only previously known construction of a unique signature in the plain model was based on the RSA assumption. The only other previously known provably secure constructions of stateless signatures were based on the Strong RSA assumption. Here, we give a construction of a unique signature scheme based on a generalization of the Diffe-Hellman assumption in groups where decisional Diffe-Hellman is easy. Several recent results suggest plausibility of such groups.We also give a few related constructions of verifiable random functions (VRFs). VRFs, introduced by Micali, Rabin, and Vadhan, are objects that combine the properties of pseudorandom functions (i.e. indistinguishability from random even after querying) with the verifiability property. Prior to our work, VRFs were only known to exist under the RSA assumption.