Verifiable Unpredictable Functions (VUFs)

A VUF allows a party with a secret key to compute a deterministic (keyed) function and prove to an external verifier that the result is correct. The notion is related to signatures, with the extra requirement that the output of the signer must be unique, even to a party that can choose the secret key.

Definition 1 (Verifiable Unpredictable Function). Let  VUF.Setup, VUF.Gen, VUF.Eval, VUF.Sign, VUF.Derive, VUF.Ver) be the following set of efficient algorithms:

•  VUF.Setup  a DPT algorithm that takes as input the security parameter and outputs a common reference string.

•  VUF.Gen  a PPT algorithm that takes as input a common reference string and returns a public key and a secret key.

•   VUF.Eval(,  a DPT algorithm that takes as input a common reference string, secret key, and message  and returns  

•  VUF.Sign(,  a PPT algorithm that takes as input a common reference string, secret key, and message, and returns a signature .

•   VUF.Derive(,  a DPT algorithm that takes as input a common reference string, public key, message and signature and returns  

•  VUF.Ver  a DPT algorithm that takes as input a common reference string, public key, message and signature and returns 1 to indicate acceptance and 0 to indicate rejection.

We say that  is a verifiable unpredictable function (VUF) if it satisfies correctness, uniqueness, and unpredictability (defined below).

• A VUF is correct if an honest signer always convinces an honest verifier and always outputs a seed such that the derive function outputs the correct value.

Definition 2 (Correctness).  VUF is correct if for all  and   we have that

• A VUF is unique if an adversary (even one that chooses the secret key) cannot output a verifying signature such that the derive function outputs the wrong value.

Definition 3 (Uniqueness). For a VUF  and an adversary  let      where  is defined as follows:

 VUF.Derive 

 VUF.Derive 

return  VUF.Ver  VUF.Ver 

We say that  is unique if for all PPT adversaries  we have that  

• Finally, a VUF is unpredictable if an adversary cannot predict the output of the function VUF.Eval on a message for which it has not seen any valid signatures.

Definition 4 (Unpredictability). For a VUF  and an adversary , let  Game where Game  is defined as follows:

MAIN Game  :

 VUF.Setup 

 VUF.Gen 

return (VUF.Eval(, 

 :

We say that  is unpredictable if for all PPT adversaries  we have that