Functional Signatures and Pseudorandom Functions
In this paper, we introduce functional digital signatures and pseudorandom functions. In a functional signature scheme, in addition to a master signing key that can be used to sign any message, there are signing keys for a function f, which allow one to sign any message in the range of f. We show applications of functional signatures to construct succinct non-interactive arguments and delegation schemes. We give several general constructions for this primitive based on different computational hardness assumptions, and describe the trade-offs between them in terms of the assumptions they require and the size of the signatures. In a functional pseudorandom function, in addition to a master secret key that can be used to evaluate the pseudorandom function F on any point in the domain, there are additional secret keys for a function f, which allow one to evaluate F on any y for which there exists an x such that f(x) = y. This implies the ability to delegate keys per function f for computing a pseudorandom function F on points y for which f(y) = 1. We define and provide a sample construction of a functional pseudorandom function family for the prefix-fixing function family. 1