Functional Signatures and Pseudorandom Functions

We introduce two new cryptographic primitives:

functional digital signatures

and

functional 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

. As a special case, this implies the ability to generate keys for predicates

P

, which allow one to sign any message

m

for which

P

(

m

) = 1.

We show applications of functional signatures to constructing 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

. As a special case, this implies

pseudorandom functions with selective access

, where one can delegate the ability to evaluate the pseudorandom function on inputs

y

for which a predicate

P

(

y

) = 1 holds. We define and provide a sample construction of a functional pseudorandom function family for prefix-fixing functions. This construction yields, in particular,

punctured pseudorandom functions

, which have proven an invaluable tool in recent advances in obfuscation (Sahai and Waters ePrint 2013).