# A Novel Construction of Constrained Verifiable Random Functions

Authors: Muhua Liu; Ping Zhang; Qingtao Wu
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Constrained verifiable random functions (VRFs) were introduced by Fuchsbauer. In a constrained VRF, one can drive a constrained keyskS from the master secret key sk, where S is a subset of the domain. Using the constrained key skS, one can compute function values at points which are not in the set S. The security of constrained VRFs requires that the VRFs’ output should be indistinguishable from a random value in the range. They showed how to construct constrained VRFs for the bit-fixing class and the circuit constrained class based on multilinear maps. Their construction can only achieve selective security where an attacker must declare which point he will attack at the beginning of experiment. In this work, we propose a novel construction for constrained verifiable random function from bilinear maps and prove that it satisfies a new security definition which is stronger than the selective security. We call it semiadaptive security where the attacker is allowed to make the evaluation queries before it outputs the challenge point. It can immediately get that if a scheme satisfied semiadaptive security, and it must satisfy selective security.


---

## Body

## 1. Introduction

Pseudorandom functions (PRFs) are one of the basic concepts in modern cryptography, which were introduced by Goldreich et al. [1]. A PRF is an efficiently computable function F:K×X⟶Y. For a randomly chosen key sk∈K, a polynomial probabilistic time (PPT) adversary cannot distinguish the outputs Fsk,x of the function for any x∈X from a randomly chosen values from Y.Boneh and Waters [2] put forward the concept of PRFs and presented a new notion which was called constrained pseudorandom functions. A constrained PRF is the same as the standard PRF except that it is associated with a set S⊂X. It contains a master key sk∈K which can be used to evaluate all points that belonged to the domain X. Given the master key sk∈K and a set S⊂X, it can generate a constrained key skS which can be used to evaluate Fsk,x for any x∉S. Pseudorandomness requires that given several constrained keys for sets S1,…,Sq1⊂X and several function values at points x1,…,xq2∈X which were chosen adaptively by the adversary, the adversary cannot distinguish a function value Fsk,x from a random value for all x≠xi,∀i∈1,…,q2, and x∈∩j=1q1Sj. Constrained PRFs have been used to optimize the ciphertext length of broadcast encryption [2] and construct multiparty key exchange [3].Verifiable random functions were introduced by Micali et al. [4]. A VRF is similar to a pseudorandom function. It also preserves the pseudorandomness that a PPT adversary cannot distinguish an evaluated value Fsk,x from a random value even if it is given several values at other points. A VRF has an additional property that the party holding the secret key is allowed to evaluate F on x∈X associated with a noninteractive proof. With the proof, anyone can verify the correctness of a given evaluation by the public key. In addition, the evaluation of Fsk,x should remain pseudorandomness and even an adversary can query values and proofs at other points. Lastly, the verification should remain sound even if the public key was computed maliciously. VRFs have been used to construct zero knowledge proofs [5], and electronic payment schemes [6], and so on.In SCN 2014, Fuchsbauer [7] extended the notion of VRFs to a new notion, which was called constrained VRFs. In addition to three polynomial time algorithms: Setup,Prove, and Verify, they defined another algorithm Constrain, which was used to drive a constrained key. For constrained VRFs, it generates a pair key pk,sk in the Setup algorithm. Given a constrained key skS for a set S⊂X, the algorithm Prove computes a value y=Fsk,x associated with a prove π which can be used to verify the correctness of y=Fsk,x by the public key pk. A constrained VRF should satisfy the security notions of provability, uniqueness, and pseudorandomness. The pseudorandomness requires that the evaluation of Fsk,x should be indistinguishable from a random value, even if the adversary is given several constrained keys for subset S1,…,Sq1⊂X and several function values associated with proofs at points x1,…,xq2, where x≠xi,∀i∈q2, and x∈∩j=1q1Sj.A possible application of constrained VRFs is micropayments [8]. Micropayment schemes emphasized the ability to make payments of small amounts. In the micropayment based on probability, a large number of users and merchants jointly select a user to pay the cheque. It can realize the micropayment of a large number of users to be converted into a macropayment of a certain user with a small probability. In this scheme, how do we decide which cheque C should be payable in fair way? Using the VRFs, merchant M publishes pkM for VRF with range Y∈0,1. Cheque C is payable if FskM,C<s, where s is a known selection rate. However, it has a drawback which needs a public key infrastructure (PKI) for merchants’ keys pkM. By the constrained VRFs, every merchant uses the same key sk. Merchant M gets constrained key skM for set idM,C, where idM is the identity of merchant M. Cheque C is payable if FskM,idMC<s. Anybody can check the result by the same public key pk. Therefore, it does not need the PKI for merchants.Fuchsbauer [7] gave two constructions from the multilinear maps based on constrained PRFs proposed by Boneh and Waters [2]. The first one is bit-fixing VRFs, in which the constrained keys can be derived for any set Sυ⊂0,1n, where Sυ is described by a vector υ∈0,1,⊥ as the set of all strings such that it matches υ at all coordinates that are not ⊥. The second one is circuit constrained VRFs, in which the constrained keys can be derived for any set that is decidable by a polynomial size circuit.However, Fuchsbauer’s constructions [7] can only achieve selective security—a weaker notion where the adversary must commit to a challenge point x∗ at the beginning of the experiment. By the technology of complexity leveraging, any selective security can be converted into adaptive security where the adversary can make its challenge query at any point. The reduction simply guesses beforehand which challenge value the adversary will query. Therefore, it leads to a security loss that is exponential in the input length. In this work, we attempt to ask an ambitious question: is it possible to construct a constrained VRF which satisfies a more stronger security compared with the selective security?In this work, we propose a novel construction based on the bilinear maps. Inspired by the constrained PRFs of Hohenberber et al. [9], we construct a VRF with constrained keys for any sets of polynomial size and define a new security named semiadaptive security. It allows the adversary to query the evaluation oracle before it outputs a challenge point, while the public key is returned to the adversary associated with the challenge evaluation. This definition is stronger than the selective security, which can be verified easily.Our scheme is derived from the constructions of constrained PRFs given by Hohenberger et al. [9]. It is defined over a bilinear group, which contains three groups G1,G2,andGT with composite order N=pq, equipped with bilinear maps e:G1×G2⟶GT. The constrained VRFs map an input from 0,1ℓλ to an element of GT. The secret key is a tuple sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1,h, where v∈G1,w∈G2,γ⟵ℤN2,di,0,di,1i=1n⟵ℤN2, h:0,1ℓλ⟶0,1nλ is an admissible hash function. VRFs are defined as(1)Fsk,x≔ev∏i=1ndi,hxi,wγ,associated with a proof(2)Psk,x≔v∏i=1ndi,hxi,where hxi is the i′th bit of hx.In order to verify the correctness of evaluation, we define a public key aspk=w,wγ,iOC, where iOC is an obfuscation of a circuit which takes a point x as input and outputs an element Dx≔ev∏i=1ndi,hxi,w from GT. The verifier only needs to check ePsk,x,w=Dx and ePsk,x,wγ=Fsk,x. The constrained key is an obfuscation of a circuit that has the secret key sk and the constrained set S hardwired in it. On input a value x∉S, it outputs Fsk,x,Psk,x. While this solution would work only if the obfuscator achieves a black box obfuscation definition [10], there is no reason to believe that an indistinguishability obfuscator would necessarily hide the secret key sk.We solve this problem by a new technique which was introduced by Hohenberger [9]. We divide the domain into two disjoint sets by the admissible hash function: computable set and challenge set. The proportion of computable set in the domain is about 1−1/Qλ, and the proportion of challenge set in the domain is about 1/Qλ, where Qλ is the number of queries made by the adversary. In the evaluation queries before the adversary outputs the challenge point, we use the secret key sk to answer the evaluation query x and abort the experiment if x belonged to the challenge set. After the adversary outputs a challenge point x∗, we use a freshly chosen secret key sk′ to answer the evaluation queries. Via a hybrid argument, we reduce weak Bilinear Diffie–Hellman Inversion (BDHI) assumption to the pseudorandomness of constrained VRFs.


### 1.1. Related Works

Lysyanskaya [11] gave a construction of VRFs in bilinear groups, but the size of proofs and keys is linear in input size, which may be undesirable in resource constrained user. Dodis and Yampolskiy [12] gave a simple and efficient construction of VRFs based on bilinear mapping. Their VRFs’ proofs and keys have constant size, but it is only suitable for small input spaces. Hohenberger and Waters [13] presented the first VRFs for exponentially large input spaces under a noninteractive assumption. Abdalla et al. [14] showed a relation between VRFs and identity-based key encapsulation mechanisms and proposed a new VRF-suitable identity-based key encapsulation mechanism from the decisional ℓ−weak Bilinear Diffie–Hellman Inversion assumption.Fuchsbauer et al. [15] studied the adaptive security of the GGM construction for constrained PRFs and gave a new reduction that only loses a quasipolynomial factor qOlogλ, where q is the number of adversary’s queries. Hofheinz et al. [16] gave a new constrained PRF construction for circuit that has polynomial reduction to indistinguishability obfuscation in the random oracle model.Kiayias et al. [17] introduced a novel cryptographic primitive called delegatable pseudorandom function, which enables a proxy to evaluate a pseudorandom function on a strict subset of its domain using a trapdoor derived from the delegatable PRF’s secret key. Boyle et al. [18] introduced functional PRFs which can be seen as constrained PRFs. In functional PRFs, in addition to a master secret key, there are other secret keys for a function f, which allows one to evaluate the pseudorandom function on any y for which there exists an x such that fx=y. Chandran et al. [19] showed constructions of selectively secure constrained VRFs for the class of all polynomial-sized circuits.Notations.
In what follows, we will denote withλ∈ℕ a security parameter. We say neglλ is negligible if neglλ<1/polyλ holds for all polynomials polyλ and all sufficiently large λ. Denote PPT as probabilistic polynomial time. Denote n as the set 1,…,n.


## 1.1. Related Works

Lysyanskaya [11] gave a construction of VRFs in bilinear groups, but the size of proofs and keys is linear in input size, which may be undesirable in resource constrained user. Dodis and Yampolskiy [12] gave a simple and efficient construction of VRFs based on bilinear mapping. Their VRFs’ proofs and keys have constant size, but it is only suitable for small input spaces. Hohenberger and Waters [13] presented the first VRFs for exponentially large input spaces under a noninteractive assumption. Abdalla et al. [14] showed a relation between VRFs and identity-based key encapsulation mechanisms and proposed a new VRF-suitable identity-based key encapsulation mechanism from the decisional ℓ−weak Bilinear Diffie–Hellman Inversion assumption.Fuchsbauer et al. [15] studied the adaptive security of the GGM construction for constrained PRFs and gave a new reduction that only loses a quasipolynomial factor qOlogλ, where q is the number of adversary’s queries. Hofheinz et al. [16] gave a new constrained PRF construction for circuit that has polynomial reduction to indistinguishability obfuscation in the random oracle model.Kiayias et al. [17] introduced a novel cryptographic primitive called delegatable pseudorandom function, which enables a proxy to evaluate a pseudorandom function on a strict subset of its domain using a trapdoor derived from the delegatable PRF’s secret key. Boyle et al. [18] introduced functional PRFs which can be seen as constrained PRFs. In functional PRFs, in addition to a master secret key, there are other secret keys for a function f, which allows one to evaluate the pseudorandom function on any y for which there exists an x such that fx=y. Chandran et al. [19] showed constructions of selectively secure constrained VRFs for the class of all polynomial-sized circuits.Notations.
In what follows, we will denote withλ∈ℕ a security parameter. We say neglλ is negligible if neglλ<1/polyλ holds for all polynomials polyλ and all sufficiently large λ. Denote PPT as probabilistic polynomial time. Denote n as the set 1,…,n.


## 2. Preliminaries

We first give a definition of admissible hash functions which is introduced by Boneh and Boyen [20].Definition 1 (see [20]).
Letℓ,n, and θ be efficiently computable univariate polynomials. An efficiently computable function h:0,1ℓλ⟶0,1nλ and an efficient randomized algorithm AdmSample are θ−admissible if for any u∈0,1,⊥nλ, define Hu:0,1ℓλ⟶0,1 as follows: Hux=0 if for all 1≤j≤nλ and hxj≠uj, else Hux=1. For any efficiently computable polynomial Qλ, ∀x1,…,xQλ,z∈0,1ℓλ, where z≠xi,∀i∈Qλ, we have that(3)Pr∀i≤Qλ,Huxi=1∧Huz=0≥1/θQλ,where the probability is taken only over u⟵AdmSample1λ,Qλ.
Next, we present the formal definition of indistinguishability obfuscation following the syntax of Garg et al. [21].Definition 2 (indistinguishability obfuscation (iO)).
A uniform PPT machineiO is called an indistinguishability obfuscator for a circuit class Cλ if the following holds:(i)
Correctness: for all security parametersλ∈ℕ, for all C∈Cλ, and for all inputs x, we have(4)PrC′x=Cx:C′⟵iOλ,C=1.(ii)
Indistinguishability: for any (not necessarily uniform) PPT distinguisherSamp,D, there exists a negligible function negl such that the following holds: if Pr∀x,C0x=C1x;C0,C1,σ⟵Samp1λ>1−neglλ, then(5)PrDσ,iOλ,C0=1:C0,C1,σ⟵Samp1λ−PrDσ,iOλ,C1=1:C0,C1,σ⟵Samp1λ≤neglλ.


### 2.1. Assumptions

LetG be a PPT group algorithm that takes a security parameter 1λ as input and outputs as tuple N,Gp,Gq,G1,G2,GT,e, in which p and q are independent uniform random λ−bit primes. G1,G2, and GT are groups of order N=pq, e:G1×G2⟶GT is a bilinear map, and Gp and Gq are the subgroups of G1 with the order p and q, respectively.The subgroup decision assumption [22] in the bilinear group is said that the uniform distribution on G1 is computationally indistinguishable from the uniform distribution on a subgroup of Gp or Gq.Assumption 1 (subgroup hiding for composite order bilinear groups).
LetN,Gp,Gq,G1,G2,GT,e⟵G1λ and b⟵0,1. Let T⟵G1 if b=0, else T⟵Gp. The advantage of algorithm A in solving the subgroup decision problem is defined as(6)AdvASGH=Prb⟵AN,Gp,Gq,G1,G2,GT,e,T−1/2.
We say that the subgroup decision problem is hard if for all PPTA, AdvASGH is negligible in λ.Assumption 2 (weak Bilinear Diffie–Hellman Inversion).
LetN,Gp,Gq,G1,G2,GT,e⟵G1λ,g1⟵G1,a⟵ℤN∗, and g2⟵G2,γ⟵ℤN∗. Let D=N,Gp,Gq,G1,G2,GT,e,g1,g1a,…,g1an−1,g2,g2γ. Let T=eg1an,g2γ if b=0, else T⟵GT. The advantage of algorithm A in solving the problem is defined as(7)AdvABDHI=Prb⟵AD,T−1/2.
We say that the weak bilinear Diffie–Hellman inversion problem is hard if for all PPTA, AdvABDHI is negligible in λ.
Chase et al. [22] showed that many q−type assumptions can be implied by subgroup hiding in bilinear groups of composite order.


## 2.1. Assumptions

LetG be a PPT group algorithm that takes a security parameter 1λ as input and outputs as tuple N,Gp,Gq,G1,G2,GT,e, in which p and q are independent uniform random λ−bit primes. G1,G2, and GT are groups of order N=pq, e:G1×G2⟶GT is a bilinear map, and Gp and Gq are the subgroups of G1 with the order p and q, respectively.The subgroup decision assumption [22] in the bilinear group is said that the uniform distribution on G1 is computationally indistinguishable from the uniform distribution on a subgroup of Gp or Gq.Assumption 1 (subgroup hiding for composite order bilinear groups).
LetN,Gp,Gq,G1,G2,GT,e⟵G1λ and b⟵0,1. Let T⟵G1 if b=0, else T⟵Gp. The advantage of algorithm A in solving the subgroup decision problem is defined as(6)AdvASGH=Prb⟵AN,Gp,Gq,G1,G2,GT,e,T−1/2.
We say that the subgroup decision problem is hard if for all PPTA, AdvASGH is negligible in λ.Assumption 2 (weak Bilinear Diffie–Hellman Inversion).
LetN,Gp,Gq,G1,G2,GT,e⟵G1λ,g1⟵G1,a⟵ℤN∗, and g2⟵G2,γ⟵ℤN∗. Let D=N,Gp,Gq,G1,G2,GT,e,g1,g1a,…,g1an−1,g2,g2γ. Let T=eg1an,g2γ if b=0, else T⟵GT. The advantage of algorithm A in solving the problem is defined as(7)AdvABDHI=Prb⟵AD,T−1/2.
We say that the weak bilinear Diffie–Hellman inversion problem is hard if for all PPTA, AdvABDHI is negligible in λ.
Chase et al. [22] showed that many q−type assumptions can be implied by subgroup hiding in bilinear groups of composite order.


## 3. Definition

We recall the definition of constrained VRFs which was given by Fuchsbauer [7].LetF:K×X⟶Y be an efficiently computable function, where K is the key space, X is the input domain, and Y is the range. F is said to be constrained VRFs with regard to a set S⊂X if there exists a constrained key space K′, a proof space P, and four algorithmsSetup,Constrain,Prove,and Verify:(i)
Setup1λ⟶pk,sk: it is a PPT algorithm that takes the security parameter λ as input and outputs a pair of keys pk,sk, a description of the key space K, and a constrained key space K′(ii)
Constrainsk,S⟶skS: this algorithm takes the secret key sk and a set S⊂X as input and outputs a constrained key skS∈K′(iii)
ProveskS,x⟶y,π or ⊥,⊥: this algorithm takes the constrained key skS and a value x as input and outputs a pair y,π∈Y×P of a function value and a proof if x∉S, else outputs ⊥,⊥(iv)
Verifypk,x,y,π⟶0,1: this algorithm takes the public key pk, an input x, a function value y, and a proof π as input and outputs a value in 0,1, where “1” indicates that y=Fsk,x


### 3.1. Provability

For allλ∈ℕ,pk,sk⟵Setup1λ,S⊂X,skS⟵Constrainsk,S, x∈X, and y,π⟵ProveskS,x, it holds that(i)
Ifx∉S, then y=Fsk,x and Verifypk,x,y,π=1(ii)
Ifx∈S, then y,π=⊥,⊥


### 3.2. Uniqueness

For allλ∈ℕ,pk,sk⟵Setup1λ,x∈X,y0,y1∈Y, and π0,π1∈P, one of the following conditions holds:(i)
y0=y1,(ii)
Verifypk,x,y0,π0=1, or(iii)
Verifypk,x,y1,π1=1,which implies that for every x there is only one value y such that Fsk,x=y.


### 3.3. Pseudorandomness

We consider the following experimentExpAVRF1λ,b for λ∈ℕ:(i)
The challenger first choosesb⟵0,1 and then generates pk,sk by running the algorithm Setup1λ and returns pk to the adversary A(ii)
The challenger initializes two setsV and E and sets V≔Ø,E≔Ø, where V will contain the points that the adversary A cannot evaluate and E contains the points at which the adversary queries the evaluation oracle(iii)
The adversaryA is given the following oracle:(1)
Constrain: on input a setS⊂X, if V∩S≠Ø, return skS⟵Constrainsk,S and set V≔V∩S; else return ⊥(2)
Evaluation: givenx∈X, return Fsk,xandPsk,x and set E≔E∪x(3)
Challenge: on inputx∗∈X, if x∗∈E or x∗∉V, then it returns ⊥. Else, it returns Fsk,x∗ if b=0, or it returns a random value from Y if b=1(iv)
A outputs a bit b′; if b=b′, the experiment outputs 1A constrained VRF is pseudorandomness if for all PPT adversaryA, it holds that(8)PrExpAVRF1λ,b=1−1/2≤neglλ.


### 3.4. Semiadaptive Security

We give a weak definition for pseudorandomness which is called semiadaptive security. It allows the adversary to query the evaluation before it outputs a challenge point, while the public key is returned to the adversary after the adversary commits a challenge point. In the selective security, the adversary must commit a challenge input at the beginning of the experiment. Therefore, we can find that if a scheme satisfies the semiadaptive security, it must satisfy selective security. Conversely, it may be not true.


### 3.5. Puncturable Verifiable Random Functions

Puncturable VRFs are a special class of constrained VRFs, in which the constrained set contains only one value, i.e.,S=x∗. The properties of provability, uniqueness, and pseudorandomness are similar to the constrained VRFs. To avoid repetition, we omit the formal definitions.


## 3.1. Provability

For allλ∈ℕ,pk,sk⟵Setup1λ,S⊂X,skS⟵Constrainsk,S, x∈X, and y,π⟵ProveskS,x, it holds that(i)
Ifx∉S, then y=Fsk,x and Verifypk,x,y,π=1(ii)
Ifx∈S, then y,π=⊥,⊥


## 3.2. Uniqueness

For allλ∈ℕ,pk,sk⟵Setup1λ,x∈X,y0,y1∈Y, and π0,π1∈P, one of the following conditions holds:(i)
y0=y1,(ii)
Verifypk,x,y0,π0=1, or(iii)
Verifypk,x,y1,π1=1,which implies that for every x there is only one value y such that Fsk,x=y.


## 3.3. Pseudorandomness

We consider the following experimentExpAVRF1λ,b for λ∈ℕ:(i)
The challenger first choosesb⟵0,1 and then generates pk,sk by running the algorithm Setup1λ and returns pk to the adversary A(ii)
The challenger initializes two setsV and E and sets V≔Ø,E≔Ø, where V will contain the points that the adversary A cannot evaluate and E contains the points at which the adversary queries the evaluation oracle(iii)
The adversaryA is given the following oracle:(1)
Constrain: on input a setS⊂X, if V∩S≠Ø, return skS⟵Constrainsk,S and set V≔V∩S; else return ⊥(2)
Evaluation: givenx∈X, return Fsk,xandPsk,x and set E≔E∪x(3)
Challenge: on inputx∗∈X, if x∗∈E or x∗∉V, then it returns ⊥. Else, it returns Fsk,x∗ if b=0, or it returns a random value from Y if b=1(iv)
A outputs a bit b′; if b=b′, the experiment outputs 1A constrained VRF is pseudorandomness if for all PPT adversaryA, it holds that(8)PrExpAVRF1λ,b=1−1/2≤neglλ.


## 3.4. Semiadaptive Security

We give a weak definition for pseudorandomness which is called semiadaptive security. It allows the adversary to query the evaluation before it outputs a challenge point, while the public key is returned to the adversary after the adversary commits a challenge point. In the selective security, the adversary must commit a challenge input at the beginning of the experiment. Therefore, we can find that if a scheme satisfies the semiadaptive security, it must satisfy selective security. Conversely, it may be not true.


## 3.5. Puncturable Verifiable Random Functions

Puncturable VRFs are a special class of constrained VRFs, in which the constrained set contains only one value, i.e.,S=x∗. The properties of provability, uniqueness, and pseudorandomness are similar to the constrained VRFs. To avoid repetition, we omit the formal definitions.


## 4. Construction

In this section, we give our construction for puncturable VRFs. A puncturable VRFF:K×X⟶Y consists of four algorithms Setup,Puncture,Prove,and Verify. The input domain is X⟵0,1ℓ, where ℓ=ℓλ. The key space K and range space Y are defined as a part of the setup algorithm.(i)
Setup1λ⟶pk,sk: On input the security parameter 1λ, run N,Gp,Gq,G1,G2,GT,e⟵G1λ such that e:G1×G2⟶GT and GpandGq are subgroups of G1. Let n,θ be polynomials such that there exists a θ−admissible hash function h:0,1ℓλ⟶0,1nλ.The key space isK=G1×G2×ℤN×ℤN2n, the range is Y=GT, and the proof space is P=G1. The setup algorithm chooses v∈G1,w∈G2,γ∈ℤN, and d1,0,d1,1,…,dn,0,dn,1∈ℤN2 uniformly at random and sets sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1. The public key contains an obfuscation of a circuit C1, where C1 is described in Figure 1. Note that C1 has v,w,d1,0,d1,1,…,dn,0,dn,1,h hardwired in it. Set pk=w,wγ,iOC1, where C1 is padded to be of appropriate size. The puncturable VRF F is defined as follows. Let hx=b1,…,bn, where bi∈0,1. Then,(9)Fsk,x=ev∏j=1ndj,bj,wγ,Psk,x=v∏j=1ndj,bj.(ii)
Puncturesk,x′⟶skx′: This algorithm computes an obfuscation of a circuit C2 which is defined in Figure 2. Note that C2 has the secret key sk and the puncturable value x′ hardwired in it. Set skx′⟵iOC2 where C2 is padded to be of appropriate size.(iii)
Proveskx′,x⟶y,π or ⊥,⊥: The punctured key skx′ is a program that takes an ℓ−bit input x. We define(10)Proveskx′,x=skx′x.(iv)
Verifypk,x,y,π⟶0,1: To verify x,y,π∈0,1ℓλ×GT×G1 with regard to pk=w,wγ,iOC1, compute Dx≔C1x=ev∏j=1ndj,bj,w and output 1 if the following equations are satisfied:(11)eπ,w=Dx,eπ,wγ=y.Figure 1
CircuitC1.Figure 2
CircuitC2.


### 4.1. Properties

#### 4.1.1. Provability

From the definition ofF and P, we observe that for pk,sk⟵Setup1λ, x∈X,skx′⟵Puncturesk,x′,y,π=Proveskx′,x, if x≠x′:(12)eπ,w=ev∏j=1ndj,bj,w=Dx,eπ,wγ=ev∏j=1ndj,bj,wγ=y=Fsk,x.Therefore, we haveVerifypk,x,y,π=1. When x=x′, we can get that Proveskx′,x′ =⊥,⊥. This completes the proof of provability.


#### 4.1.2. Uniqueness

Consider a public keypk=w,wγ,iOC1, where w∈G2,γ∈ℤN, and C1 is described in Figure 1. Given a value x∈0,1ℓλ and two pair values y0,π0 and y1,π1∈GT×G1 that satisfy Verifypk,x,yb,πb=1 for b∈0,1. We show that y0=y1.From the verification equations, we observe thateπb,w=Dx and eπb,wγ=yb. Because Dx=ev∏j=1ndj,bj,w, then π0=π1. Therefore, we can get that y0=eπ0,wγ=eπ1,wγ=y1.


### 4.2. Proof of Pseudorandomness

In this section, we prove that our construction is secure puncturable VRFs as defined in Section3.Theorem 1.
AssumingiO is a secure indistinguishability obfuscator and the subgroup hiding assumption for composite order bilinear groups holds, then our construction described as above satisfies the semiadaptive security as defined in Section 3.Proof.
To prove the above theorem, we first define a sequence of games where the first one is the original pseudorandomness security game and show that each adjacent games is computationally indistinguishable for any PPT adversaryA. Without loss of generality, we assume that the adversary A makes Q=Qλ evaluation queries before outputting the challenge point, where Qλ is a polynomial. We present a full description of each game and underline the changes from the present one to the previous one. Each such game is completely characterized by its key generation algorithm and its challenge answer. The differences between these games are summarized in Table 1.Table 1
The differences between each adjacent games.
Game
Key generation
Challenge answer
Game 1
s
k
=
v
,
w
,
γ
,
d
i
,
0
,
d
i
,
1
i
=
1
n
y
0
=
e
v
∏
j
=
1
n
d
j
,
b
j
∗
,
w
γ
Game 2
s
k
=
v
,
w
,
γ
,
d
i
,
0
,
d
i
,
1
i
=
1
n
IfHux∗=1, abort, else y0=ev∏j=1ndj,bj∗,wγ
Game 3
IfHux=1, sk=v,w,γ,di,0,di,1i=1n. Else, sk′=v1,w,γ,ei,0,ei,1i=1n
IfHux∗=1, abort, else y0=ev1∏j=1nej,bj∗,wγ
Game 4
IfHux=1, sk=v,w,γ,di,0,di,1i=1n. Else, sk′=v1,w,γ,ei,0,ei,1i=1n where ei,b=ei,0′⋅a, if Hux∗i=b
IfHux∗=1, abort, else y0=ev1∏j=1nej,bj∗,wγ
Game 5
IfHux=1, sk=v,w,γ,di,0,di,1i=1n. Else, sk′=V,w,γ,ei,0′,ei,1′i=1n where V=v1,v1a,…,v1an−1
IfHux∗=1, abort, else y0=ev1an∏j=1nej,bj∗′,wγ
Game 6
IfHux=1, sk=v,w,γ,di,0,di,1i=1n. Else, sk′=V,w,γ,ei,0′,ei,1′i=1n where V=v1,v1a,…,v1an−1
IfHux∗=1, abort, else y0=T∏j=1nej,bj∗′


#### 4.2.1. Game 1

The first game is the original security for our construction. Here, the challenger first chooses a puncturable VRF key. Then,A makes evaluation queries and finally outputs a challenge point. The challenger responds with either a PRF evaluation or a random value.(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN,d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1.(2)
The adversaryA makes a evaluation query xi∈0,1ℓλ. Then, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger computesskx∗⟵iOC2 and hx∗=b1∗,…,bn∗, sets y0=ev∏j=1ndj,bj∗,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.


#### 4.2.2. Game 2

This game is the same as the Game 1 except that a partitioning game is simulated. If the undesirable partition is queried, we abort the game. The partition game is defined as follows: the challenger samples a stringu∈0,1,⊥n by the algorithm AdmSample of admissible hash function and aborts if either there exists a evaluation query x such that Hux=0 or the challenge query x∗ such that Hux∗=1.(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN,d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1 and runs u⟵AdmSample1λ,Q.(2)
The adversaryA makes a evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC2 and hx∗=b1∗,…,bn∗, sets y0=ev∏j=1ndj,bj∗,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 1.
For any PPT adversaryA, if A wins with advantage ϵ in Game 1, then it wins with advantage ϵ/θQλ in Game 2.Proof.
The difference between Game 1 and Game 2 is that we add an abort condition in Game 2. From theθ−admissible of hash function h, we can get that for all x1,…,xQ,x∗, Pru⟵AdmSample1λ,Qλ∀i,Huxi=1∧Hux∗=0≥1/θQλ. The two experiments are equal if Game 2 does not abort. Therefore, if A wins with advantage ϵ in Game 1, then it wins with advantage at least ϵ/θQλ in Game 2.


#### 4.2.3. Game 3

This game is the same as the previous one except that the public key and the punctured key are obfuscation of two other circuits defined in Figures3 and 4, respectively. On inputs x such that Hux=1, the public key and the punctured key use the same secret key sk as before. However, if Hux=0, the public key and the punctured key use a different secret key sk′ which is randomly chosen from the key space. The detailed description is given as follows:(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN,andd1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1andpk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1 and runs u⟵AdmSample1λ,Q.(2)
The adversaryA makes a evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger chooses v1∈G1,e1,0,e1,1,…,en,0,en,1∈ℤN2, sets sk′=v1,w,γ,e1,0,e1,1,…,en,0,en,1, computes pk′=w,wγ,iOC3,skx∗⟵iOC4 and hx∗=b1∗,…,bn∗, and sets y0=ev1∏j=1nej,bj∗,wγ and y1⟵GT. Then, it returns pk′,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Figure 3
CircuitC3.Figure 4
CircuitC4.Lemma 2.
AssumingiO is a secure indistinguishability obfuscator and the assumption 1 holds, Game 2 and Game 3 are computationally indistinguishable.
This proof is given in Section4.3.


#### 4.2.4. Game 4

This game is the same as the previous one except that the generation way of secret keysk′ is different. We make some elements of secret key sk′ to contain a factor a, for use on inputs x where Hux=0. The detailed description is given as follows:(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN,d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1 and runs u⟵AdmSample1λ,Q.(2)
The adversaryA makes a evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger chooses v1∈G1, a∈ℤN,e1,0′,e1,1′,…,en,0′,en,1′∈ℤN2. Set ei,b=ei,b′⋅a, if hx∗i=b, else ei,b=ei,b′. Let sk′=v1,w,γ,e1,0,e1,1,…,en,0,en,1, compute pk′=w,wγ,iOC3, skx∗⟵iOC4, and hx∗=b1∗,…,bn∗ and set y0=ev1∏j=1nej,bj∗,wγ and y1⟵GT. Then, it returns pk′,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 3.
The outputs of Game 3 and Game 4 are statistically indistinguishable.Proof.
Recall that the difference between Game 3 and Game 4 is the manner in whichei,bi∈n,b∈0,1 are chosen. In Game 3, ei,bi∈n,b∈0,1 are chosen randomly from ℤN, while in Game 4, the challenger first chooses ei,b′⟵ℤN and a⟵ℤN and sets ei,b=ei,b′⋅a, if hx∗i=b, else ei,b=ei,b′. Since a∈ℤN which is invertible with overwhelming probability, ei,b=ei,b′⋅a is a uniform element in ℤN. Hence, the two experiments are statistically indistinguishable.


#### 4.2.5. Game 5

This game is the same as the previous one except that the hardwire of circuitsC3 and C4 is changed. The two circuits contain some constants v1aii=1n−1. When Hux=0, the related function values are computed using the constants v1aii=1n. The detailed description is given as follows:(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN, and d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1 and runs u⟵AdmSample1λ,Q.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger chooses v1∈G1,a∈ℤN,e1,0′,e1,1′,…,e1,0′,en,1′∈ℤN2. Set V⟶=v1,v1a,…,v1an−1. Let sk′=v1,w,γ,e1,0,e1,1,…,en,0,en,1, compute pk′=w,wγ,iOC5, skx∗⟵iOC6, hx∗=b1∗,…,bn∗, and Dx∗=ev1an∏j=1nej,bj∗′,w. Set y0=ev1an∏j=1nej,bj∗′,w and y1⟵GT, where the descriptions of C5 and C6 are given in Figures 5 and 6, respectively. Then, it returns pk′,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Figure 5
CircuitC5.Figure 6
CircuitC6.Lemma 4.
AssumingiO is a secure indistinguishability obfuscator, Game 4 and Game 5 are computationally indistinguishable.Proof.
We will introduce an intermediate experiment4A and prove that Game 4 and 4A are computationally indistinguishable and Game 4A and Game 5 are computationally indistinguishable.
The experiment4A is the same as Game 5 except that skx∗ is generated by obfuscating the circuit C4 in Step 4. Assume that there exists a PPT adversary A that distinguishes the outputs of Game 4 and Game 4A, we construct a PPT adversary ℬ that breaks the iO security with the same probability. ℬ runs Step 1 and Step 3 as in experiment 4. If the experiment does not abort, ℬ chooses values to construct the circuits: v1∈G1,a⟵ℤN,e1,0′,e1,1′,…,en,0′,en,1′∈ℤN2. Set ei,b=ei,b′⋅a, if hx∗i=b, else ei,b=ei,b′. Let sk′=v1,w,γ,e1,0,e1,1,…,en,0,en,1, V⟶=v1,v1a,…,v1an−1, and sk″=v1,w,γ,e1,0′,e1,1′,…,en,0′,en,1′. ℬ constructs circuits C0=C3 and C1=C5, where sk′ is replaced by sk″. Then, he sends C0andC1 to the iO challenger and gets pk′=iOCβ. ℬ computes skx∗=iOC4,hx∗=b1∗,…,bn∗, y0=ev1∏j=1nej,bj∗,wγ,andy1⟵GT and returns pk′,skx∗,yα to the adversary A. A outputs α′, if α=α′ and ℬ outputs 0, else outputs 1. The circuits C0 and C1 have identical functionality. We observe that for any string x, hx=b1,…,bn:(i)
For anyx∈0,1ℓ such that Hux=1, both circuits output Dx=ev∏j=1ndj,bj,w(ii)
For anyx∈0,1ℓ such that Hux=0,x≠x∗, we have C0x=v1∏j=1nej,bj,w=v1anx∏j=1nej,bj′,w=C1x, where nx=i:bi=bi∗(iii)
For anyx∈0,1ℓ such that Hux=0,x=x∗, we have C0x=v1∏j=1nej,bj,w=Dx∗=C1x
Therefore, if there exists an adversaryA that distinguishes the outputs of Game 4 and Game 4A with advantage ϵ, then there exists an adversary ℬ that breaks the security of iO with the same advantage.
The indistinguishability of Game4A and Game 5 is similar to the previous one (Game 4 and Game 4A).


#### 4.2.6. Game 6

This game is the same as the previous one except thatev1an,wγ is replaced by a random element from GT. Formally, the challenger chooses a random element T⟵GT, and uses y0=T∏j=1nej,bj∗′ to replace y0=ev1an∏j=1nej,bj∗′,wγ.Lemma 5.
If there exists an adversaryA that distinguishes Game 5 and Game 6 with advantage ϵ, then there exists an adversary ℬ that breaks assumption 2 with advantage ϵ.Proof.
We observe that the difference between Game 5 and Game 6 is that the elementev1an,wγ in Game 5 is replaced by a random element in Game 6. ℬ receives an instance N,Gp,G1,G1,G2,GT,e,g1,g1a,…,g1an−1,g2,g2γ,T, where T is either equal to eg1an,g2γ or a random element of GT. Then, ℬ simulates Game 5 except that yα=T∏j=1nej,bj∗′. A outputs α′,. If α=α′, ℬ outputs 0, which indicates that T=eg1an,g2γ; else, ℬ outputs 1, which implies that T is a random element from GT.
We observe that bothy0 and y1 are chosen randomly from GT in Game 6. This completes the proof of Theorem 1.


### 4.3. Proof of Lemma 2

The major difference between Game 2 and Game 3 is the ‘challenge partition’ inputsx where Hux=0. Therefore, in order to show that for any PPT adversary A, the outputs of Game 2 and Game 3 are indistinguishable; we give a sequence of subexperiments Game 2A to Game 2F and prove that any PPT attacker’s advantage in each game must be negligible close to the previous one. We omit the previous experiment Game 2 and describe the intermediate experiments. In the first game, we change the secret key such that the circuit computes the output in a different manner and the output is the same as in the original circuit. Next, using the weak bilinear Diffie–Hellman inversion assumption, we modify the constants hardwired in the program such that the output of all challenge partition inputs is changed. Essentially, a different base for the challenge partition is used in the two programs, respectively. Finally, using Subgroup Hiding Assumption and Chinese Remainder Theorem, we can change the exponents for the challenge partition and ensure that the original circuit (in Game 2) and final circuit (in Game 3) use different secret keys for the challenge partition.


#### 4.3.1. Game2A

In this game, we modify the secret keydi,b for j∈1,…,nandb∈0,1. It is easy to verify that the two experiments are statistically indistinguishable. The detailed description is given as follows:(1)
The challenger flips a coinα⟵0,1 and runs u⟵AdmSample1λ,Q. Then, the challenger runs N,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,a,γ∈ℤN, and d1,0′,d1,1′,…,dn,0′,dn,1′∈ℤN2, sets di,b=di,b′ if ui=b, else di,b=a⋅di,b′, and sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0, if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC2 and hx∗=b1∗,…,bn∗, sets y0=ev∏j=1ndj,bj∗,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 6.
The outputs of Game 2 and Game2A are statistically indistinguishable.Proof.
We observe the difference between Game 2 and Game2A is the manner in which di,b are chosen. In Game 2, di,b are chosen randomly from ℤN, while in Game 2A, the challenger first chooses di,b′⟵ℤN and a⟵ℤN and sets di,b=di,b′, if ui=b, else di,b=di,b′⋅a. Since a∈ℤN, which is invertible with overwhelming probability, di,b=di,b′⋅a is a uniformly random element in ℤN. Therefore, the two experiments are statistically indistinguishable.


#### 4.3.2. Game2B

This game is the same as the previous one except the hardwire of the circuit is changed. The domain is divided into two disjoint sets by the admissible hash function. WhenHux=0, all elements di,b used to compute function values y contain a factor a. Therefore, the related function values can be computed by v′=van. On the other hand, only some elements di,b used to compute function values y contain the factor a when Hux=1. Therefore, the related function values can only be computed by v,va,…,van−1.(1)
The challenger flips a coinα⟵0,1 and runs u⟵AdmSample1λ,Q. Let mx=i:ui≠hxi. Then, the challenger runs N,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,a,γ∈ℤN, and d1,0′,d1,1′,…,dn,0′,dn,1′∈ℤN2, sets di,b=di,b′ if ui=b, else di,b=a⋅di,b′, and D=d1,0′,d1,1′,…,dn,0′,dn,1′, V⟶=v,va,…,van−1,v′=van, and pk=w,wγ,iOC7, where the description of C7 is given in Figure 7.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0, if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC8 and hx∗=b1∗,…,bn∗, sets y0=ev∏j=1ndj,bj∗,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A, where the description of C8 is given in Figure 8.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Figure 7
CircuitC7.Figure 8
CircuitC8.Lemma 7.
AssumingiO is a secure indistinguishability obfuscator, Game 2A and Game 2B are computationally indistinguishable.Proof.
The proof method is similar to Lemma 4.


#### 4.3.3. Game2C

This game is the same as the previous one except thatv′ is chosen randomly from G1 in Step 1, and y0=ev′∏j=1ndj,bj∗′,wγ in Step 4.Lemma 8.
If there exists an adversaryA that distinguishes the Game 2B and Game 2C with advantage ϵ, then there exists an adversary ℬ that breaks assumption 2 with advantage ϵ.Proof.
We observe that the difference between Game2B and Game 2C is that the term van is replaced by a random element of G1. This proof is similar to the proof of Lemma 5.


#### 4.3.4. Game2D

This game is the same as the previous one except thatv is chosen randomly from the subgroup Gp, and v′ is chosen randomly from the subgroup Gq in Step 1.Lemma 9.
Assuming assumption 1 holds, Game2C and Game 2D are computationally indistinguishable.Proof.
We introduce an intermediate experiment2C1 and show that Game 2C1 and 2C are computationally indistinguishable. Similarly, Game 2C1 and Game 2D are computationally indistinguishable.
Game2C1 is the same as Game 2C except that v is chosen from Gp. Suppose that there exists an adversary A which can distinguish Game 2C1 and 2C, we construct an adversary ℬ that breaks assumption 1. ℬ receives N,Gp,Gq,G1,G2,GT,e,T, where T⟵G1 or T⟵Gp. ℬ sets v=T, chooses v′⟵G1,w⟵G2,a,γ∈ℤN, and d1,0′,d1,1′,…,dn,0′,dn,1′∈ℤN2, and computes V⟶,D,andpk as in Game 2C. Then, ℬ runs the rest steps as in Game 2C. At last, A outputs α′, if α=α′ and ℬ guesses T∈G1, else ℬ guesses T∈Gp. Note that ℬ simulates exactly Game 2C when T∈G1, and ℬ simulates exactly Game 2C1 when T∈Gp. Therefore, if there exists an adversary A that distinguishes the outputs 2C and 2C1 with advantage ϵ, then there exists an adversary ℬ that breaks the assumption 1.


#### 4.3.5. Game2E

This game is the same as the previous one except that the secret key is divided into two partssk and sk′. If Hux=0, the related function values are computed by sk′. Else, the related function values are computed by sk.(1)
The challenger flips a coinα⟵0,1 and runs u⟵AdmSample1λ,Q. Let mx=i:ui≠hxi. Then, the challenger runs N,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈Gp,v′∈Gq,w∈G2,a,γ∈ℤN, and d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1, sk′=v′,wγ,d1,0,d1,1,…,dn,0,dn,1, and pk=w,wγ,iOC3.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC4 and hx∗=b1∗,…,bn∗, sets y0=ev′∏j=1ndj,bj∗′,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 10.
AssumingiO is a secure indistinguishability obfuscator, Game 2D and Game 2E are computationally indistinguishable.Proof.
We introduce two intermediate experiments2D1 and 2D2 and show that Game 2D and 2D1 are computationally indistinguishable, Game 2D1 and Game 2D2 are computationally indistinguishable, and Game 2D2 and Game 2E are computationally indistinguishable.
First, we define the experiments2D1 and 2D2. In experiment 2D1, the challenger samples v,v′,w,a,γ,anddi,b′ as in Game 2D, sets di,b=di,b′ if ui=b, else di,b=a⋅di,b′. Then, it answers the evaluation queries of A exactly as in Game 2D. For the challenge queries, it sets v″=v′1/an and computes y0=ev″∏j=1ndj,bj∗,wγandy1⟵GT. The public key pk is computed by the circuit C3, where sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1 and sk′=v″,wγ,d1,0,d1,1,…,dn,0,dn,1. The constrained key skx∗ is computed as in Game 2D.
Game2D2 is the same as the game 2D1, except that the constrained key skx∗ is computed by the circuit C4.Claim 1.
AssumingA is a secure indistinguishability obfuscator, Game α′ and Game α′=α are computationally indistinguishable.Proof.
We construct a PPT adversaryiO that uses 2A to break the security of 2B. 2C runs Step 1 and Step 3 as in Game v′. On receiving the challenge point G1, y0=ev′∏j=1ndj,bj∗′,wγ sets A and 2B as in 2C and constructs circuits ℬ and 2B. Then, he sends 2C to the van challenger and receives G1. 2D computes Gp as in Game v′ and sends Gq to 2C. 2D returns 2C1, if 2C1, 2C outputs 0, else outputs 1.
Next, we only show that the circuit2C1 and 2D have the identical functionality. For any 2C1 such that 2C. For any Gp such that A. Therefore, the two circuits are functionally equivalent. Hence, if there exists an adversary that can distinguish the two games, then we can construct an adversary 2C1 that breaks the 2C security.Claim 2.
Assumingℬ is a secure indistinguishability obfuscator, Game ℬ and Game N,Gp,Gq,G1,G2,GT,e,T are computationally indistinguishable.Proof.
The proof method is similar to the previous one.Claim 3.
GameT⟵G1 and Game T⟵Gp are statistically indistinguishable.Proof.
The difference between Gameℬ and Game v=T is the chosen way of v′⟵G1,w⟵G2,a,γ∈ℤN. In addition, d1,0′,d1,′,…,dn,0′,dn,′∈ℤN2 is replaced by the value V⟶,D,andpk in Game 2C. Since ℬ, a is invertible with overwhelming probability. Therefore, 2C is a uniform element from A and α′ is also a uniformly random element from α=α′ in Game ℬ. It follows that the two experiments are statistically indistinguishable.


#### 4.3.6. Game2F

This game is the same as the previous one except that the generation way of secret keysk′ is different to the one of sk.(1)
The challenger flips a coinα⟵0,1 and runs u⟵AdmSample1λ,Q. Let mx=i:ui≠hxi. Then, the challenger runs N,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈Gp,v′∈Gq,w∈G2,a,γ∈ℤN, d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and e1,0,e1,1,…,en,0,en,1∈ℤN2, and sets sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1, sk′=v′,wγ,e1,0,e1,1,…,en,0,en,1, and pk=w,wγ,iOC3.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC4 and hx∗=b1∗,…,bn∗, sets y0=ev′∏j=1ndj,bj∗′,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 11.
Game2E and Game 2F are statistically indistinguishable.Proof.
The only difference between Game2E and Game 2F is the chosen way of the secret key sk and sk′. In Game 2E, the challenger chooses v∈Gp,v′∈Gq,w∈G2,γ,di,b∈ℤN and sets sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1 and sk′=v′,wγ,d1,0,d1,1,…,dn,0,dn,1. While the challenger chooses di,b,ei,b∈ℤN and sets sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1 and sk′=v′,wγ,e1,0,e1,1,…,en,0,en,1 in Game 2F. Using Chinese remainder theorem, the distributions xmodp,xmodq:x⟵ℤN and xmodp,ymodq:x,y⟵ℤN are statistically indistinguishable. Therefore, Game 2E and Game 2F are statistically indistinguishable.Lemma 12.
Assuming assumption 1 holds, Game2F and Game 3 are computationally indistinguishable.Proof.
The proof method is similar to Lemma 9.


## 4.1. Properties

### 4.1.1. Provability

From the definition ofF and P, we observe that for pk,sk⟵Setup1λ, x∈X,skx′⟵Puncturesk,x′,y,π=Proveskx′,x, if x≠x′:(12)eπ,w=ev∏j=1ndj,bj,w=Dx,eπ,wγ=ev∏j=1ndj,bj,wγ=y=Fsk,x.Therefore, we haveVerifypk,x,y,π=1. When x=x′, we can get that Proveskx′,x′ =⊥,⊥. This completes the proof of provability.


### 4.1.2. Uniqueness

Consider a public keypk=w,wγ,iOC1, where w∈G2,γ∈ℤN, and C1 is described in Figure 1. Given a value x∈0,1ℓλ and two pair values y0,π0 and y1,π1∈GT×G1 that satisfy Verifypk,x,yb,πb=1 for b∈0,1. We show that y0=y1.From the verification equations, we observe thateπb,w=Dx and eπb,wγ=yb. Because Dx=ev∏j=1ndj,bj,w, then π0=π1. Therefore, we can get that y0=eπ0,wγ=eπ1,wγ=y1.


## 4.1.1. Provability

From the definition ofF and P, we observe that for pk,sk⟵Setup1λ, x∈X,skx′⟵Puncturesk,x′,y,π=Proveskx′,x, if x≠x′:(12)eπ,w=ev∏j=1ndj,bj,w=Dx,eπ,wγ=ev∏j=1ndj,bj,wγ=y=Fsk,x.Therefore, we haveVerifypk,x,y,π=1. When x=x′, we can get that Proveskx′,x′ =⊥,⊥. This completes the proof of provability.


## 4.1.2. Uniqueness

Consider a public keypk=w,wγ,iOC1, where w∈G2,γ∈ℤN, and C1 is described in Figure 1. Given a value x∈0,1ℓλ and two pair values y0,π0 and y1,π1∈GT×G1 that satisfy Verifypk,x,yb,πb=1 for b∈0,1. We show that y0=y1.From the verification equations, we observe thateπb,w=Dx and eπb,wγ=yb. Because Dx=ev∏j=1ndj,bj,w, then π0=π1. Therefore, we can get that y0=eπ0,wγ=eπ1,wγ=y1.


## 4.2. Proof of Pseudorandomness

In this section, we prove that our construction is secure puncturable VRFs as defined in Section3.Theorem 1.
AssumingiO is a secure indistinguishability obfuscator and the subgroup hiding assumption for composite order bilinear groups holds, then our construction described as above satisfies the semiadaptive security as defined in Section 3.Proof.
To prove the above theorem, we first define a sequence of games where the first one is the original pseudorandomness security game and show that each adjacent games is computationally indistinguishable for any PPT adversaryA. Without loss of generality, we assume that the adversary A makes Q=Qλ evaluation queries before outputting the challenge point, where Qλ is a polynomial. We present a full description of each game and underline the changes from the present one to the previous one. Each such game is completely characterized by its key generation algorithm and its challenge answer. The differences between these games are summarized in Table 1.Table 1
The differences between each adjacent games.
Game
Key generation
Challenge answer
Game 1
s
k
=
v
,
w
,
γ
,
d
i
,
0
,
d
i
,
1
i
=
1
n
y
0
=
e
v
∏
j
=
1
n
d
j
,
b
j
∗
,
w
γ
Game 2
s
k
=
v
,
w
,
γ
,
d
i
,
0
,
d
i
,
1
i
=
1
n
IfHux∗=1, abort, else y0=ev∏j=1ndj,bj∗,wγ
Game 3
IfHux=1, sk=v,w,γ,di,0,di,1i=1n. Else, sk′=v1,w,γ,ei,0,ei,1i=1n
IfHux∗=1, abort, else y0=ev1∏j=1nej,bj∗,wγ
Game 4
IfHux=1, sk=v,w,γ,di,0,di,1i=1n. Else, sk′=v1,w,γ,ei,0,ei,1i=1n where ei,b=ei,0′⋅a, if Hux∗i=b
IfHux∗=1, abort, else y0=ev1∏j=1nej,bj∗,wγ
Game 5
IfHux=1, sk=v,w,γ,di,0,di,1i=1n. Else, sk′=V,w,γ,ei,0′,ei,1′i=1n where V=v1,v1a,…,v1an−1
IfHux∗=1, abort, else y0=ev1an∏j=1nej,bj∗′,wγ
Game 6
IfHux=1, sk=v,w,γ,di,0,di,1i=1n. Else, sk′=V,w,γ,ei,0′,ei,1′i=1n where V=v1,v1a,…,v1an−1
IfHux∗=1, abort, else y0=T∏j=1nej,bj∗′


### 4.2.1. Game 1

The first game is the original security for our construction. Here, the challenger first chooses a puncturable VRF key. Then,A makes evaluation queries and finally outputs a challenge point. The challenger responds with either a PRF evaluation or a random value.(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN,d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1.(2)
The adversaryA makes a evaluation query xi∈0,1ℓλ. Then, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger computesskx∗⟵iOC2 and hx∗=b1∗,…,bn∗, sets y0=ev∏j=1ndj,bj∗,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.


### 4.2.2. Game 2

This game is the same as the Game 1 except that a partitioning game is simulated. If the undesirable partition is queried, we abort the game. The partition game is defined as follows: the challenger samples a stringu∈0,1,⊥n by the algorithm AdmSample of admissible hash function and aborts if either there exists a evaluation query x such that Hux=0 or the challenge query x∗ such that Hux∗=1.(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN,d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1 and runs u⟵AdmSample1λ,Q.(2)
The adversaryA makes a evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC2 and hx∗=b1∗,…,bn∗, sets y0=ev∏j=1ndj,bj∗,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 1.
For any PPT adversaryA, if A wins with advantage ϵ in Game 1, then it wins with advantage ϵ/θQλ in Game 2.Proof.
The difference between Game 1 and Game 2 is that we add an abort condition in Game 2. From theθ−admissible of hash function h, we can get that for all x1,…,xQ,x∗, Pru⟵AdmSample1λ,Qλ∀i,Huxi=1∧Hux∗=0≥1/θQλ. The two experiments are equal if Game 2 does not abort. Therefore, if A wins with advantage ϵ in Game 1, then it wins with advantage at least ϵ/θQλ in Game 2.


### 4.2.3. Game 3

This game is the same as the previous one except that the public key and the punctured key are obfuscation of two other circuits defined in Figures3 and 4, respectively. On inputs x such that Hux=1, the public key and the punctured key use the same secret key sk as before. However, if Hux=0, the public key and the punctured key use a different secret key sk′ which is randomly chosen from the key space. The detailed description is given as follows:(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN,andd1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1andpk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1 and runs u⟵AdmSample1λ,Q.(2)
The adversaryA makes a evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger chooses v1∈G1,e1,0,e1,1,…,en,0,en,1∈ℤN2, sets sk′=v1,w,γ,e1,0,e1,1,…,en,0,en,1, computes pk′=w,wγ,iOC3,skx∗⟵iOC4 and hx∗=b1∗,…,bn∗, and sets y0=ev1∏j=1nej,bj∗,wγ and y1⟵GT. Then, it returns pk′,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Figure 3
CircuitC3.Figure 4
CircuitC4.Lemma 2.
AssumingiO is a secure indistinguishability obfuscator and the assumption 1 holds, Game 2 and Game 3 are computationally indistinguishable.
This proof is given in Section4.3.


### 4.2.4. Game 4

This game is the same as the previous one except that the generation way of secret keysk′ is different. We make some elements of secret key sk′ to contain a factor a, for use on inputs x where Hux=0. The detailed description is given as follows:(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN,d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1 and runs u⟵AdmSample1λ,Q.(2)
The adversaryA makes a evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger chooses v1∈G1, a∈ℤN,e1,0′,e1,1′,…,en,0′,en,1′∈ℤN2. Set ei,b=ei,b′⋅a, if hx∗i=b, else ei,b=ei,b′. Let sk′=v1,w,γ,e1,0,e1,1,…,en,0,en,1, compute pk′=w,wγ,iOC3, skx∗⟵iOC4, and hx∗=b1∗,…,bn∗ and set y0=ev1∏j=1nej,bj∗,wγ and y1⟵GT. Then, it returns pk′,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 3.
The outputs of Game 3 and Game 4 are statistically indistinguishable.Proof.
Recall that the difference between Game 3 and Game 4 is the manner in whichei,bi∈n,b∈0,1 are chosen. In Game 3, ei,bi∈n,b∈0,1 are chosen randomly from ℤN, while in Game 4, the challenger first chooses ei,b′⟵ℤN and a⟵ℤN and sets ei,b=ei,b′⋅a, if hx∗i=b, else ei,b=ei,b′. Since a∈ℤN which is invertible with overwhelming probability, ei,b=ei,b′⋅a is a uniform element in ℤN. Hence, the two experiments are statistically indistinguishable.


### 4.2.5. Game 5

This game is the same as the previous one except that the hardwire of circuitsC3 and C4 is changed. The two circuits contain some constants v1aii=1n−1. When Hux=0, the related function values are computed using the constants v1aii=1n. The detailed description is given as follows:(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN, and d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1 and runs u⟵AdmSample1λ,Q.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger chooses v1∈G1,a∈ℤN,e1,0′,e1,1′,…,e1,0′,en,1′∈ℤN2. Set V⟶=v1,v1a,…,v1an−1. Let sk′=v1,w,γ,e1,0,e1,1,…,en,0,en,1, compute pk′=w,wγ,iOC5, skx∗⟵iOC6, hx∗=b1∗,…,bn∗, and Dx∗=ev1an∏j=1nej,bj∗′,w. Set y0=ev1an∏j=1nej,bj∗′,w and y1⟵GT, where the descriptions of C5 and C6 are given in Figures 5 and 6, respectively. Then, it returns pk′,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Figure 5
CircuitC5.Figure 6
CircuitC6.Lemma 4.
AssumingiO is a secure indistinguishability obfuscator, Game 4 and Game 5 are computationally indistinguishable.Proof.
We will introduce an intermediate experiment4A and prove that Game 4 and 4A are computationally indistinguishable and Game 4A and Game 5 are computationally indistinguishable.
The experiment4A is the same as Game 5 except that skx∗ is generated by obfuscating the circuit C4 in Step 4. Assume that there exists a PPT adversary A that distinguishes the outputs of Game 4 and Game 4A, we construct a PPT adversary ℬ that breaks the iO security with the same probability. ℬ runs Step 1 and Step 3 as in experiment 4. If the experiment does not abort, ℬ chooses values to construct the circuits: v1∈G1,a⟵ℤN,e1,0′,e1,1′,…,en,0′,en,1′∈ℤN2. Set ei,b=ei,b′⋅a, if hx∗i=b, else ei,b=ei,b′. Let sk′=v1,w,γ,e1,0,e1,1,…,en,0,en,1, V⟶=v1,v1a,…,v1an−1, and sk″=v1,w,γ,e1,0′,e1,1′,…,en,0′,en,1′. ℬ constructs circuits C0=C3 and C1=C5, where sk′ is replaced by sk″. Then, he sends C0andC1 to the iO challenger and gets pk′=iOCβ. ℬ computes skx∗=iOC4,hx∗=b1∗,…,bn∗, y0=ev1∏j=1nej,bj∗,wγ,andy1⟵GT and returns pk′,skx∗,yα to the adversary A. A outputs α′, if α=α′ and ℬ outputs 0, else outputs 1. The circuits C0 and C1 have identical functionality. We observe that for any string x, hx=b1,…,bn:(i)
For anyx∈0,1ℓ such that Hux=1, both circuits output Dx=ev∏j=1ndj,bj,w(ii)
For anyx∈0,1ℓ such that Hux=0,x≠x∗, we have C0x=v1∏j=1nej,bj,w=v1anx∏j=1nej,bj′,w=C1x, where nx=i:bi=bi∗(iii)
For anyx∈0,1ℓ such that Hux=0,x=x∗, we have C0x=v1∏j=1nej,bj,w=Dx∗=C1x
Therefore, if there exists an adversaryA that distinguishes the outputs of Game 4 and Game 4A with advantage ϵ, then there exists an adversary ℬ that breaks the security of iO with the same advantage.
The indistinguishability of Game4A and Game 5 is similar to the previous one (Game 4 and Game 4A).


### 4.2.6. Game 6

This game is the same as the previous one except thatev1an,wγ is replaced by a random element from GT. Formally, the challenger chooses a random element T⟵GT, and uses y0=T∏j=1nej,bj∗′ to replace y0=ev1an∏j=1nej,bj∗′,wγ.Lemma 5.
If there exists an adversaryA that distinguishes Game 5 and Game 6 with advantage ϵ, then there exists an adversary ℬ that breaks assumption 2 with advantage ϵ.Proof.
We observe that the difference between Game 5 and Game 6 is that the elementev1an,wγ in Game 5 is replaced by a random element in Game 6. ℬ receives an instance N,Gp,G1,G1,G2,GT,e,g1,g1a,…,g1an−1,g2,g2γ,T, where T is either equal to eg1an,g2γ or a random element of GT. Then, ℬ simulates Game 5 except that yα=T∏j=1nej,bj∗′. A outputs α′,. If α=α′, ℬ outputs 0, which indicates that T=eg1an,g2γ; else, ℬ outputs 1, which implies that T is a random element from GT.
We observe that bothy0 and y1 are chosen randomly from GT in Game 6. This completes the proof of Theorem 1.


## 4.2.1. Game 1

The first game is the original security for our construction. Here, the challenger first chooses a puncturable VRF key. Then,A makes evaluation queries and finally outputs a challenge point. The challenger responds with either a PRF evaluation or a random value.(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN,d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1.(2)
The adversaryA makes a evaluation query xi∈0,1ℓλ. Then, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger computesskx∗⟵iOC2 and hx∗=b1∗,…,bn∗, sets y0=ev∏j=1ndj,bj∗,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.


## 4.2.2. Game 2

This game is the same as the Game 1 except that a partitioning game is simulated. If the undesirable partition is queried, we abort the game. The partition game is defined as follows: the challenger samples a stringu∈0,1,⊥n by the algorithm AdmSample of admissible hash function and aborts if either there exists a evaluation query x such that Hux=0 or the challenge query x∗ such that Hux∗=1.(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN,d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1 and runs u⟵AdmSample1λ,Q.(2)
The adversaryA makes a evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC2 and hx∗=b1∗,…,bn∗, sets y0=ev∏j=1ndj,bj∗,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 1.
For any PPT adversaryA, if A wins with advantage ϵ in Game 1, then it wins with advantage ϵ/θQλ in Game 2.Proof.
The difference between Game 1 and Game 2 is that we add an abort condition in Game 2. From theθ−admissible of hash function h, we can get that for all x1,…,xQ,x∗, Pru⟵AdmSample1λ,Qλ∀i,Huxi=1∧Hux∗=0≥1/θQλ. The two experiments are equal if Game 2 does not abort. Therefore, if A wins with advantage ϵ in Game 1, then it wins with advantage at least ϵ/θQλ in Game 2.


## 4.2.3. Game 3

This game is the same as the previous one except that the public key and the punctured key are obfuscation of two other circuits defined in Figures3 and 4, respectively. On inputs x such that Hux=1, the public key and the punctured key use the same secret key sk as before. However, if Hux=0, the public key and the punctured key use a different secret key sk′ which is randomly chosen from the key space. The detailed description is given as follows:(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN,andd1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1andpk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1 and runs u⟵AdmSample1λ,Q.(2)
The adversaryA makes a evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger chooses v1∈G1,e1,0,e1,1,…,en,0,en,1∈ℤN2, sets sk′=v1,w,γ,e1,0,e1,1,…,en,0,en,1, computes pk′=w,wγ,iOC3,skx∗⟵iOC4 and hx∗=b1∗,…,bn∗, and sets y0=ev1∏j=1nej,bj∗,wγ and y1⟵GT. Then, it returns pk′,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Figure 3
CircuitC3.Figure 4
CircuitC4.Lemma 2.
AssumingiO is a secure indistinguishability obfuscator and the assumption 1 holds, Game 2 and Game 3 are computationally indistinguishable.
This proof is given in Section4.3.


## 4.2.4. Game 4

This game is the same as the previous one except that the generation way of secret keysk′ is different. We make some elements of secret key sk′ to contain a factor a, for use on inputs x where Hux=0. The detailed description is given as follows:(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN,d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1 and runs u⟵AdmSample1λ,Q.(2)
The adversaryA makes a evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger chooses v1∈G1, a∈ℤN,e1,0′,e1,1′,…,en,0′,en,1′∈ℤN2. Set ei,b=ei,b′⋅a, if hx∗i=b, else ei,b=ei,b′. Let sk′=v1,w,γ,e1,0,e1,1,…,en,0,en,1, compute pk′=w,wγ,iOC3, skx∗⟵iOC4, and hx∗=b1∗,…,bn∗ and set y0=ev1∏j=1nej,bj∗,wγ and y1⟵GT. Then, it returns pk′,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 3.
The outputs of Game 3 and Game 4 are statistically indistinguishable.Proof.
Recall that the difference between Game 3 and Game 4 is the manner in whichei,bi∈n,b∈0,1 are chosen. In Game 3, ei,bi∈n,b∈0,1 are chosen randomly from ℤN, while in Game 4, the challenger first chooses ei,b′⟵ℤN and a⟵ℤN and sets ei,b=ei,b′⋅a, if hx∗i=b, else ei,b=ei,b′. Since a∈ℤN which is invertible with overwhelming probability, ei,b=ei,b′⋅a is a uniform element in ℤN. Hence, the two experiments are statistically indistinguishable.


## 4.2.5. Game 5

This game is the same as the previous one except that the hardwire of circuitsC3 and C4 is changed. The two circuits contain some constants v1aii=1n−1. When Hux=0, the related function values are computed using the constants v1aii=1n. The detailed description is given as follows:(1)
The challenger runsN,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,γ∈ℤN, and d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1. Then, the challenger flips a coin α⟵0,1 and runs u⟵AdmSample1λ,Q.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger chooses v1∈G1,a∈ℤN,e1,0′,e1,1′,…,e1,0′,en,1′∈ℤN2. Set V⟶=v1,v1a,…,v1an−1. Let sk′=v1,w,γ,e1,0,e1,1,…,en,0,en,1, compute pk′=w,wγ,iOC5, skx∗⟵iOC6, hx∗=b1∗,…,bn∗, and Dx∗=ev1an∏j=1nej,bj∗′,w. Set y0=ev1an∏j=1nej,bj∗′,w and y1⟵GT, where the descriptions of C5 and C6 are given in Figures 5 and 6, respectively. Then, it returns pk′,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Figure 5
CircuitC5.Figure 6
CircuitC6.Lemma 4.
AssumingiO is a secure indistinguishability obfuscator, Game 4 and Game 5 are computationally indistinguishable.Proof.
We will introduce an intermediate experiment4A and prove that Game 4 and 4A are computationally indistinguishable and Game 4A and Game 5 are computationally indistinguishable.
The experiment4A is the same as Game 5 except that skx∗ is generated by obfuscating the circuit C4 in Step 4. Assume that there exists a PPT adversary A that distinguishes the outputs of Game 4 and Game 4A, we construct a PPT adversary ℬ that breaks the iO security with the same probability. ℬ runs Step 1 and Step 3 as in experiment 4. If the experiment does not abort, ℬ chooses values to construct the circuits: v1∈G1,a⟵ℤN,e1,0′,e1,1′,…,en,0′,en,1′∈ℤN2. Set ei,b=ei,b′⋅a, if hx∗i=b, else ei,b=ei,b′. Let sk′=v1,w,γ,e1,0,e1,1,…,en,0,en,1, V⟶=v1,v1a,…,v1an−1, and sk″=v1,w,γ,e1,0′,e1,1′,…,en,0′,en,1′. ℬ constructs circuits C0=C3 and C1=C5, where sk′ is replaced by sk″. Then, he sends C0andC1 to the iO challenger and gets pk′=iOCβ. ℬ computes skx∗=iOC4,hx∗=b1∗,…,bn∗, y0=ev1∏j=1nej,bj∗,wγ,andy1⟵GT and returns pk′,skx∗,yα to the adversary A. A outputs α′, if α=α′ and ℬ outputs 0, else outputs 1. The circuits C0 and C1 have identical functionality. We observe that for any string x, hx=b1,…,bn:(i)
For anyx∈0,1ℓ such that Hux=1, both circuits output Dx=ev∏j=1ndj,bj,w(ii)
For anyx∈0,1ℓ such that Hux=0,x≠x∗, we have C0x=v1∏j=1nej,bj,w=v1anx∏j=1nej,bj′,w=C1x, where nx=i:bi=bi∗(iii)
For anyx∈0,1ℓ such that Hux=0,x=x∗, we have C0x=v1∏j=1nej,bj,w=Dx∗=C1x
Therefore, if there exists an adversaryA that distinguishes the outputs of Game 4 and Game 4A with advantage ϵ, then there exists an adversary ℬ that breaks the security of iO with the same advantage.
The indistinguishability of Game4A and Game 5 is similar to the previous one (Game 4 and Game 4A).


## 4.2.6. Game 6

This game is the same as the previous one except thatev1an,wγ is replaced by a random element from GT. Formally, the challenger chooses a random element T⟵GT, and uses y0=T∏j=1nej,bj∗′ to replace y0=ev1an∏j=1nej,bj∗′,wγ.Lemma 5.
If there exists an adversaryA that distinguishes Game 5 and Game 6 with advantage ϵ, then there exists an adversary ℬ that breaks assumption 2 with advantage ϵ.Proof.
We observe that the difference between Game 5 and Game 6 is that the elementev1an,wγ in Game 5 is replaced by a random element in Game 6. ℬ receives an instance N,Gp,G1,G1,G2,GT,e,g1,g1a,…,g1an−1,g2,g2γ,T, where T is either equal to eg1an,g2γ or a random element of GT. Then, ℬ simulates Game 5 except that yα=T∏j=1nej,bj∗′. A outputs α′,. If α=α′, ℬ outputs 0, which indicates that T=eg1an,g2γ; else, ℬ outputs 1, which implies that T is a random element from GT.
We observe that bothy0 and y1 are chosen randomly from GT in Game 6. This completes the proof of Theorem 1.


## 4.3. Proof of Lemma 2

The major difference between Game 2 and Game 3 is the ‘challenge partition’ inputsx where Hux=0. Therefore, in order to show that for any PPT adversary A, the outputs of Game 2 and Game 3 are indistinguishable; we give a sequence of subexperiments Game 2A to Game 2F and prove that any PPT attacker’s advantage in each game must be negligible close to the previous one. We omit the previous experiment Game 2 and describe the intermediate experiments. In the first game, we change the secret key such that the circuit computes the output in a different manner and the output is the same as in the original circuit. Next, using the weak bilinear Diffie–Hellman inversion assumption, we modify the constants hardwired in the program such that the output of all challenge partition inputs is changed. Essentially, a different base for the challenge partition is used in the two programs, respectively. Finally, using Subgroup Hiding Assumption and Chinese Remainder Theorem, we can change the exponents for the challenge partition and ensure that the original circuit (in Game 2) and final circuit (in Game 3) use different secret keys for the challenge partition.


### 4.3.1. Game2A

In this game, we modify the secret keydi,b for j∈1,…,nandb∈0,1. It is easy to verify that the two experiments are statistically indistinguishable. The detailed description is given as follows:(1)
The challenger flips a coinα⟵0,1 and runs u⟵AdmSample1λ,Q. Then, the challenger runs N,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,a,γ∈ℤN, and d1,0′,d1,1′,…,dn,0′,dn,1′∈ℤN2, sets di,b=di,b′ if ui=b, else di,b=a⋅di,b′, and sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0, if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC2 and hx∗=b1∗,…,bn∗, sets y0=ev∏j=1ndj,bj∗,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 6.
The outputs of Game 2 and Game2A are statistically indistinguishable.Proof.
We observe the difference between Game 2 and Game2A is the manner in which di,b are chosen. In Game 2, di,b are chosen randomly from ℤN, while in Game 2A, the challenger first chooses di,b′⟵ℤN and a⟵ℤN and sets di,b=di,b′, if ui=b, else di,b=di,b′⋅a. Since a∈ℤN, which is invertible with overwhelming probability, di,b=di,b′⋅a is a uniformly random element in ℤN. Therefore, the two experiments are statistically indistinguishable.


### 4.3.2. Game2B

This game is the same as the previous one except the hardwire of the circuit is changed. The domain is divided into two disjoint sets by the admissible hash function. WhenHux=0, all elements di,b used to compute function values y contain a factor a. Therefore, the related function values can be computed by v′=van. On the other hand, only some elements di,b used to compute function values y contain the factor a when Hux=1. Therefore, the related function values can only be computed by v,va,…,van−1.(1)
The challenger flips a coinα⟵0,1 and runs u⟵AdmSample1λ,Q. Let mx=i:ui≠hxi. Then, the challenger runs N,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,a,γ∈ℤN, and d1,0′,d1,1′,…,dn,0′,dn,1′∈ℤN2, sets di,b=di,b′ if ui=b, else di,b=a⋅di,b′, and D=d1,0′,d1,1′,…,dn,0′,dn,1′, V⟶=v,va,…,van−1,v′=van, and pk=w,wγ,iOC7, where the description of C7 is given in Figure 7.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0, if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC8 and hx∗=b1∗,…,bn∗, sets y0=ev∏j=1ndj,bj∗,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A, where the description of C8 is given in Figure 8.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Figure 7
CircuitC7.Figure 8
CircuitC8.Lemma 7.
AssumingiO is a secure indistinguishability obfuscator, Game 2A and Game 2B are computationally indistinguishable.Proof.
The proof method is similar to Lemma 4.


### 4.3.3. Game2C

This game is the same as the previous one except thatv′ is chosen randomly from G1 in Step 1, and y0=ev′∏j=1ndj,bj∗′,wγ in Step 4.Lemma 8.
If there exists an adversaryA that distinguishes the Game 2B and Game 2C with advantage ϵ, then there exists an adversary ℬ that breaks assumption 2 with advantage ϵ.Proof.
We observe that the difference between Game2B and Game 2C is that the term van is replaced by a random element of G1. This proof is similar to the proof of Lemma 5.


### 4.3.4. Game2D

This game is the same as the previous one except thatv is chosen randomly from the subgroup Gp, and v′ is chosen randomly from the subgroup Gq in Step 1.Lemma 9.
Assuming assumption 1 holds, Game2C and Game 2D are computationally indistinguishable.Proof.
We introduce an intermediate experiment2C1 and show that Game 2C1 and 2C are computationally indistinguishable. Similarly, Game 2C1 and Game 2D are computationally indistinguishable.
Game2C1 is the same as Game 2C except that v is chosen from Gp. Suppose that there exists an adversary A which can distinguish Game 2C1 and 2C, we construct an adversary ℬ that breaks assumption 1. ℬ receives N,Gp,Gq,G1,G2,GT,e,T, where T⟵G1 or T⟵Gp. ℬ sets v=T, chooses v′⟵G1,w⟵G2,a,γ∈ℤN, and d1,0′,d1,1′,…,dn,0′,dn,1′∈ℤN2, and computes V⟶,D,andpk as in Game 2C. Then, ℬ runs the rest steps as in Game 2C. At last, A outputs α′, if α=α′ and ℬ guesses T∈G1, else ℬ guesses T∈Gp. Note that ℬ simulates exactly Game 2C when T∈G1, and ℬ simulates exactly Game 2C1 when T∈Gp. Therefore, if there exists an adversary A that distinguishes the outputs 2C and 2C1 with advantage ϵ, then there exists an adversary ℬ that breaks the assumption 1.


### 4.3.5. Game2E

This game is the same as the previous one except that the secret key is divided into two partssk and sk′. If Hux=0, the related function values are computed by sk′. Else, the related function values are computed by sk.(1)
The challenger flips a coinα⟵0,1 and runs u⟵AdmSample1λ,Q. Let mx=i:ui≠hxi. Then, the challenger runs N,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈Gp,v′∈Gq,w∈G2,a,γ∈ℤN, and d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1, sk′=v′,wγ,d1,0,d1,1,…,dn,0,dn,1, and pk=w,wγ,iOC3.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC4 and hx∗=b1∗,…,bn∗, sets y0=ev′∏j=1ndj,bj∗′,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 10.
AssumingiO is a secure indistinguishability obfuscator, Game 2D and Game 2E are computationally indistinguishable.Proof.
We introduce two intermediate experiments2D1 and 2D2 and show that Game 2D and 2D1 are computationally indistinguishable, Game 2D1 and Game 2D2 are computationally indistinguishable, and Game 2D2 and Game 2E are computationally indistinguishable.
First, we define the experiments2D1 and 2D2. In experiment 2D1, the challenger samples v,v′,w,a,γ,anddi,b′ as in Game 2D, sets di,b=di,b′ if ui=b, else di,b=a⋅di,b′. Then, it answers the evaluation queries of A exactly as in Game 2D. For the challenge queries, it sets v″=v′1/an and computes y0=ev″∏j=1ndj,bj∗,wγandy1⟵GT. The public key pk is computed by the circuit C3, where sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1 and sk′=v″,wγ,d1,0,d1,1,…,dn,0,dn,1. The constrained key skx∗ is computed as in Game 2D.
Game2D2 is the same as the game 2D1, except that the constrained key skx∗ is computed by the circuit C4.Claim 1.
AssumingA is a secure indistinguishability obfuscator, Game α′ and Game α′=α are computationally indistinguishable.Proof.
We construct a PPT adversaryiO that uses 2A to break the security of 2B. 2C runs Step 1 and Step 3 as in Game v′. On receiving the challenge point G1, y0=ev′∏j=1ndj,bj∗′,wγ sets A and 2B as in 2C and constructs circuits ℬ and 2B. Then, he sends 2C to the van challenger and receives G1. 2D computes Gp as in Game v′ and sends Gq to 2C. 2D returns 2C1, if 2C1, 2C outputs 0, else outputs 1.
Next, we only show that the circuit2C1 and 2D have the identical functionality. For any 2C1 such that 2C. For any Gp such that A. Therefore, the two circuits are functionally equivalent. Hence, if there exists an adversary that can distinguish the two games, then we can construct an adversary 2C1 that breaks the 2C security.Claim 2.
Assumingℬ is a secure indistinguishability obfuscator, Game ℬ and Game N,Gp,Gq,G1,G2,GT,e,T are computationally indistinguishable.Proof.
The proof method is similar to the previous one.Claim 3.
GameT⟵G1 and Game T⟵Gp are statistically indistinguishable.Proof.
The difference between Gameℬ and Game v=T is the chosen way of v′⟵G1,w⟵G2,a,γ∈ℤN. In addition, d1,0′,d1,′,…,dn,0′,dn,′∈ℤN2 is replaced by the value V⟶,D,andpk in Game 2C. Since ℬ, a is invertible with overwhelming probability. Therefore, 2C is a uniform element from A and α′ is also a uniformly random element from α=α′ in Game ℬ. It follows that the two experiments are statistically indistinguishable.


### 4.3.6. Game2F

This game is the same as the previous one except that the generation way of secret keysk′ is different to the one of sk.(1)
The challenger flips a coinα⟵0,1 and runs u⟵AdmSample1λ,Q. Let mx=i:ui≠hxi. Then, the challenger runs N,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈Gp,v′∈Gq,w∈G2,a,γ∈ℤN, d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and e1,0,e1,1,…,en,0,en,1∈ℤN2, and sets sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1, sk′=v′,wγ,e1,0,e1,1,…,en,0,en,1, and pk=w,wγ,iOC3.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC4 and hx∗=b1∗,…,bn∗, sets y0=ev′∏j=1ndj,bj∗′,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 11.
Game2E and Game 2F are statistically indistinguishable.Proof.
The only difference between Game2E and Game 2F is the chosen way of the secret key sk and sk′. In Game 2E, the challenger chooses v∈Gp,v′∈Gq,w∈G2,γ,di,b∈ℤN and sets sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1 and sk′=v′,wγ,d1,0,d1,1,…,dn,0,dn,1. While the challenger chooses di,b,ei,b∈ℤN and sets sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1 and sk′=v′,wγ,e1,0,e1,1,…,en,0,en,1 in Game 2F. Using Chinese remainder theorem, the distributions xmodp,xmodq:x⟵ℤN and xmodp,ymodq:x,y⟵ℤN are statistically indistinguishable. Therefore, Game 2E and Game 2F are statistically indistinguishable.Lemma 12.
Assuming assumption 1 holds, Game2F and Game 3 are computationally indistinguishable.Proof.
The proof method is similar to Lemma 9.


## 4.3.1. Game2A

In this game, we modify the secret keydi,b for j∈1,…,nandb∈0,1. It is easy to verify that the two experiments are statistically indistinguishable. The detailed description is given as follows:(1)
The challenger flips a coinα⟵0,1 and runs u⟵AdmSample1λ,Q. Then, the challenger runs N,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,a,γ∈ℤN, and d1,0′,d1,1′,…,dn,0′,dn,1′∈ℤN2, sets di,b=di,b′ if ui=b, else di,b=a⋅di,b′, and sk=v,w,γ,d1,0,d1,1,…,dn,0,dn,1 and pk=w,wγ,iOC1.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0, if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC2 and hx∗=b1∗,…,bn∗, sets y0=ev∏j=1ndj,bj∗,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 6.
The outputs of Game 2 and Game2A are statistically indistinguishable.Proof.
We observe the difference between Game 2 and Game2A is the manner in which di,b are chosen. In Game 2, di,b are chosen randomly from ℤN, while in Game 2A, the challenger first chooses di,b′⟵ℤN and a⟵ℤN and sets di,b=di,b′, if ui=b, else di,b=di,b′⋅a. Since a∈ℤN, which is invertible with overwhelming probability, di,b=di,b′⋅a is a uniformly random element in ℤN. Therefore, the two experiments are statistically indistinguishable.


## 4.3.2. Game2B

This game is the same as the previous one except the hardwire of the circuit is changed. The domain is divided into two disjoint sets by the admissible hash function. WhenHux=0, all elements di,b used to compute function values y contain a factor a. Therefore, the related function values can be computed by v′=van. On the other hand, only some elements di,b used to compute function values y contain the factor a when Hux=1. Therefore, the related function values can only be computed by v,va,…,van−1.(1)
The challenger flips a coinα⟵0,1 and runs u⟵AdmSample1λ,Q. Let mx=i:ui≠hxi. Then, the challenger runs N,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈G1,w∈G2,a,γ∈ℤN, and d1,0′,d1,1′,…,dn,0′,dn,1′∈ℤN2, sets di,b=di,b′ if ui=b, else di,b=a⋅di,b′, and D=d1,0′,d1,1′,…,dn,0′,dn,1′, V⟶=v,va,…,van−1,v′=van, and pk=w,wγ,iOC7, where the description of C7 is given in Figure 7.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0, if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC8 and hx∗=b1∗,…,bn∗, sets y0=ev∏j=1ndj,bj∗,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A, where the description of C8 is given in Figure 8.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Figure 7
CircuitC7.Figure 8
CircuitC8.Lemma 7.
AssumingiO is a secure indistinguishability obfuscator, Game 2A and Game 2B are computationally indistinguishable.Proof.
The proof method is similar to Lemma 4.


## 4.3.3. Game2C

This game is the same as the previous one except thatv′ is chosen randomly from G1 in Step 1, and y0=ev′∏j=1ndj,bj∗′,wγ in Step 4.Lemma 8.
If there exists an adversaryA that distinguishes the Game 2B and Game 2C with advantage ϵ, then there exists an adversary ℬ that breaks assumption 2 with advantage ϵ.Proof.
We observe that the difference between Game2B and Game 2C is that the term van is replaced by a random element of G1. This proof is similar to the proof of Lemma 5.


## 4.3.4. Game2D

This game is the same as the previous one except thatv is chosen randomly from the subgroup Gp, and v′ is chosen randomly from the subgroup Gq in Step 1.Lemma 9.
Assuming assumption 1 holds, Game2C and Game 2D are computationally indistinguishable.Proof.
We introduce an intermediate experiment2C1 and show that Game 2C1 and 2C are computationally indistinguishable. Similarly, Game 2C1 and Game 2D are computationally indistinguishable.
Game2C1 is the same as Game 2C except that v is chosen from Gp. Suppose that there exists an adversary A which can distinguish Game 2C1 and 2C, we construct an adversary ℬ that breaks assumption 1. ℬ receives N,Gp,Gq,G1,G2,GT,e,T, where T⟵G1 or T⟵Gp. ℬ sets v=T, chooses v′⟵G1,w⟵G2,a,γ∈ℤN, and d1,0′,d1,1′,…,dn,0′,dn,1′∈ℤN2, and computes V⟶,D,andpk as in Game 2C. Then, ℬ runs the rest steps as in Game 2C. At last, A outputs α′, if α=α′ and ℬ guesses T∈G1, else ℬ guesses T∈Gp. Note that ℬ simulates exactly Game 2C when T∈G1, and ℬ simulates exactly Game 2C1 when T∈Gp. Therefore, if there exists an adversary A that distinguishes the outputs 2C and 2C1 with advantage ϵ, then there exists an adversary ℬ that breaks the assumption 1.


## 4.3.5. Game2E

This game is the same as the previous one except that the secret key is divided into two partssk and sk′. If Hux=0, the related function values are computed by sk′. Else, the related function values are computed by sk.(1)
The challenger flips a coinα⟵0,1 and runs u⟵AdmSample1λ,Q. Let mx=i:ui≠hxi. Then, the challenger runs N,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈Gp,v′∈Gq,w∈G2,a,γ∈ℤN, and d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and sets sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1, sk′=v′,wγ,d1,0,d1,1,…,dn,0,dn,1, and pk=w,wγ,iOC3.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC4 and hx∗=b1∗,…,bn∗, sets y0=ev′∏j=1ndj,bj∗′,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 10.
AssumingiO is a secure indistinguishability obfuscator, Game 2D and Game 2E are computationally indistinguishable.Proof.
We introduce two intermediate experiments2D1 and 2D2 and show that Game 2D and 2D1 are computationally indistinguishable, Game 2D1 and Game 2D2 are computationally indistinguishable, and Game 2D2 and Game 2E are computationally indistinguishable.
First, we define the experiments2D1 and 2D2. In experiment 2D1, the challenger samples v,v′,w,a,γ,anddi,b′ as in Game 2D, sets di,b=di,b′ if ui=b, else di,b=a⋅di,b′. Then, it answers the evaluation queries of A exactly as in Game 2D. For the challenge queries, it sets v″=v′1/an and computes y0=ev″∏j=1ndj,bj∗,wγandy1⟵GT. The public key pk is computed by the circuit C3, where sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1 and sk′=v″,wγ,d1,0,d1,1,…,dn,0,dn,1. The constrained key skx∗ is computed as in Game 2D.
Game2D2 is the same as the game 2D1, except that the constrained key skx∗ is computed by the circuit C4.Claim 1.
AssumingA is a secure indistinguishability obfuscator, Game α′ and Game α′=α are computationally indistinguishable.Proof.
We construct a PPT adversaryiO that uses 2A to break the security of 2B. 2C runs Step 1 and Step 3 as in Game v′. On receiving the challenge point G1, y0=ev′∏j=1ndj,bj∗′,wγ sets A and 2B as in 2C and constructs circuits ℬ and 2B. Then, he sends 2C to the van challenger and receives G1. 2D computes Gp as in Game v′ and sends Gq to 2C. 2D returns 2C1, if 2C1, 2C outputs 0, else outputs 1.
Next, we only show that the circuit2C1 and 2D have the identical functionality. For any 2C1 such that 2C. For any Gp such that A. Therefore, the two circuits are functionally equivalent. Hence, if there exists an adversary that can distinguish the two games, then we can construct an adversary 2C1 that breaks the 2C security.Claim 2.
Assumingℬ is a secure indistinguishability obfuscator, Game ℬ and Game N,Gp,Gq,G1,G2,GT,e,T are computationally indistinguishable.Proof.
The proof method is similar to the previous one.Claim 3.
GameT⟵G1 and Game T⟵Gp are statistically indistinguishable.Proof.
The difference between Gameℬ and Game v=T is the chosen way of v′⟵G1,w⟵G2,a,γ∈ℤN. In addition, d1,0′,d1,′,…,dn,0′,dn,′∈ℤN2 is replaced by the value V⟶,D,andpk in Game 2C. Since ℬ, a is invertible with overwhelming probability. Therefore, 2C is a uniform element from A and α′ is also a uniformly random element from α=α′ in Game ℬ. It follows that the two experiments are statistically indistinguishable.


## 4.3.6. Game2F

This game is the same as the previous one except that the generation way of secret keysk′ is different to the one of sk.(1)
The challenger flips a coinα⟵0,1 and runs u⟵AdmSample1λ,Q. Let mx=i:ui≠hxi. Then, the challenger runs N,Gp,Gq,G1,G2,GT,e⟵G1λ, chooses v∈Gp,v′∈Gq,w∈G2,a,γ∈ℤN, d1,0,d1,1,…,dn,0,dn,1∈ℤN2, and e1,0,e1,1,…,en,0,en,1∈ℤN2, and sets sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1, sk′=v′,wγ,e1,0,e1,1,…,en,0,en,1, and pk=w,wγ,iOC3.(2)
The adversaryA makes an evaluation query xi∈0,1ℓλ. The challenger checks if Huxi=1 (recall that Hux=0 if hxj≠uj for all j∈n). If not, the game aborts. Else, the challenger computes hxi=b1i,…,bni and outputs Fsk,xi,Psk,xi=ev∏j=1ndj,bji,wγ,v∏j=1ndj,bji.(3)
The adversaryA sends a challenge point x∗ such that x∗≠xi for all i∈Qλ.(4)
The challenger checks ifHux∗=0. If not, the game aborts. Else, the challenger computes skx∗⟵iOC4 and hx∗=b1∗,…,bn∗, sets y0=ev′∏j=1ndj,bj∗′,wγ and y1⟵GT, and returns pk,skx∗,yα to the adversary A.(5)
The adversaryA outputs a bit α′ and wins if α′=α.Lemma 11.
Game2E and Game 2F are statistically indistinguishable.Proof.
The only difference between Game2E and Game 2F is the chosen way of the secret key sk and sk′. In Game 2E, the challenger chooses v∈Gp,v′∈Gq,w∈G2,γ,di,b∈ℤN and sets sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1 and sk′=v′,wγ,d1,0,d1,1,…,dn,0,dn,1. While the challenger chooses di,b,ei,b∈ℤN and sets sk=v,wγ,d1,0,d1,1,…,dn,0,dn,1 and sk′=v′,wγ,e1,0,e1,1,…,en,0,en,1 in Game 2F. Using Chinese remainder theorem, the distributions xmodp,xmodq:x⟵ℤN and xmodp,ymodq:x,y⟵ℤN are statistically indistinguishable. Therefore, Game 2E and Game 2F are statistically indistinguishable.Lemma 12.
Assuming assumption 1 holds, Game2F and Game 3 are computationally indistinguishable.Proof.
The proof method is similar to Lemma 9.


## 5. Constrained Verifiable Random Function

In this section, we give our construction of constrained verifiable random function with polynomial size of the constrained set. We embed the puncturable VRFs in the constrained VRFs. Informally, our algorithm works as follows: The setup algorithm is the same as the puncturable VRFs. The constrained keyskS for the subset S is a circuit which has the secret key sk hardwired in it. On input a value x, the circuit computes the function value and proof by the puncturable VRFs if x∉S. The verifiable algorithm is the same as the puncturable VRFs. When proving the pseudorandomness, we translate puncturable VRFs into constrained VRFs with polynomial size of the constrained set by means of hybrid argument. Once the adversary queries the constrained key for the polynomial set S1, the challenger can guess the challenge point x∗ with a probability of 1/S1. Subsequently, the secret key sk can be replaced by a constrained key skx∗ of puncturable VRFs. Via a hybrid argument, we reduce pseudorandomness of puncturable VRFs to the pseudorandomness of constrained VRFs.LetF:K×X⟶Y be a puncturable VRF Setup,Puncture,Prove,and Verify, and P:K×X⟶G1 be a function of generation proof. We construct constrained VRFs F.Setup,F.Constrain,F.Prove,andF.Verify by invoking the puncturable VRFs:(i)
F.Setup1λ⟶pk,sk: Run the algorithm pk1,sk1⟵Setup1λ. Set pk=pk1 and sk=sk1.(ii)
F.Constrainsk,S⟶skS: This algorithm takes the secret key sk and the constrained set S as inputs, where S=poly and computes an obfuscation of a circuit Csk,S defined as in Figure 9. Csk,S has the secret key, the function descriptions F and P, and the constrained set S hardwired in it. Sets skS⟵iOCsk,S where Csk,S is padded to be of appropriate size.(iii)
F.ProveskS,x⟶y,π or ⊥,⊥: The constrained key skS is a program that takes x as the input. Define F.ProveskS,x=skSx.(iv)
F.Verifypk,x,y,π⟶0,1: This algorithm is the same as Verify.Figure 9
CircuitCsk,S.The provability and uniqueness follow from the puncturable VRFs. We omit the detailed description. Next, we show that this construction satisfies the pseudorandomness defined in Section3.Theorem 2.
AssumingiO is a secure indistinguishability obfuscator and Setup,Puncture,Prove,and Verify is a secure puncturable VRF. Then, the construction defined above satisfies the pseudorandomness.Proof.
Without loss of generality, we assume the adversary makesq1 evaluation queries and q2 constrained queries. We present a full description of each game and underline the changes from the presented one to the previous one.


### 5.1. Game 1

The first game is the original security game for our construction. Here, the challenger first chooses a pair constrained VRF keypk,sk. Then, A makes evaluation queries and constrained key queries and outputs a challenge point. The challenger responds with either a VRF evaluation or a random element.(i)
The challenger choosesb⟵0,1 and then generates pk,sk by running the algorithm F.Setup1λ(ii)
The adversary makes evaluation queries or constrained queries:(1)
IfA sends an evaluation query xi, then output Fsk,xi,Psk,xi(2)
IfA sends a constrained key query for Sj, output the constrained key skSj⟵iOCsk,Sj(iii)
A sends a challenge query x∗ such that x∗≠xi for all i≤q1 and x∗∈Sj for all j≤q2. Then, the challenger sets y0=Fsk,x∗andy1⟵Y and outputs yb,pk(iv)
A outputs b′ and wins if b=b′


### 5.2. Game 2

This game is the same as the previous one except that we introduce an abort condition. When the adversaryA makes the first constrained query S1, the challenger guesses a challenge query x′∈S1. If the last q2−1 queries Sj does not contain x′, the experiment aborts. In addition, the experiment aborts if x′≠x∗, where x∗ is the challenge query.(i)
The challenger choosesb⟵0,1 and then generates pk,sk by running the algorithm F.Setup1λ.(ii)
The adversary makes evaluation queries or constrained queries: For the first constrained queryS1, the challenger chooses x′⟵S1 and output skS1⟵iOCsk,S1. For all evaluation queries xi before the first constrained query, the challenger outputs Fsk,xi,Psk,xi. For all queries after the first constrained query, the challenger does as follows:(1)
IfA sends an evaluation query xi such that xi=x′, the experiment aborts. Else, if xi≠x′, output Fsk,xi,Psk,xi(2)
IfA sends a constrained key query for Sj such that xi∉Sj, the experiment aborts. Else, output skSj⟵iOCsk,Sj.(iii)
A sends a challenge query x∗ such that x∗≠xi for all i≤q1, and x∗∈Sj for all j≤q2. If x∗≠x′, the experiment aborts. Else, the challenger sets y0=Fsk,x∗andy1⟵Y and outputs yb,pk.(iv)
A outputs b′ and wins if b=b′.Lemma 13.
For any PPT adversaryA, if A wins with advantage ϵ in Game 1, then it wins with advantage ε/S1 in Game 2.Proof.
According the pseudorandomness defined in Section3, the challenge point belongs to the constrained set. The two experiments are equal if Game 2 does not abort. Since the challenger guesses correctly with probability 1/S1, if A wins with advantage ϵ in Game 1, then it wins with advantage ε/S1 in Game 2.


### 5.3. Game2i

For0≤i≤q2, the experiment is the same as the previous one except that the constrained queries use skx′ instead of sk in the first i experiment. We observe that the Game 20 is equal to the Game 2.(i)
The challenger choosesb⟵0,1 and then generates pk,sk by running the algorithm F.Setup1λ.(ii)
The adversary makes evaluation queries or constrained queries: For the first constrained queryS1. The challenger chooses x′⟵S1, computes skx′⟵iOCskx′,S1andπ′=Puncturesk,x′, and outputs skS1⟵iOCskx′,S1, where the description of the circuit Cskx′,S1 is given in Figure 10. For all evaluation queries xi before the first constrained query, the challenger outputs Fsk,xi,Psk,xi. For all queries after the first constrained query, the challenger does as follows:(1)
IfA sends an evaluation query xi such that xi=x′, the experiment aborts. Else, if xi≠x′, output Fsk,xi,Psk,xi=Proveskx′,xi(2)
IfA sends a constrained key query for Sj such that xi∉Sj, the experiment aborts. Else, if j≤i output skSj⟵iOCskx′,Sj, else output skSj⟵iOCsk,Sj, where the description of the circuit Cskx′,Sj is given in Figure 10.(iii)
A sends a challenge query x∗ such that x∗≠xi for all i≤q1 and x∗∈Sj for all j≤q2. If x∗≠x′, the experiment aborts. Else, the challenger sets y0=Fsk,x∗andy1⟵Y, computes, and outputs yb,pk.(iv)
A outputs b′ and wins if b=b′.Figure 10
CircuitCskx′,Sj.Lemma 14.
AssumingiO is a secure indistinguishability obfuscator, Game 2i−1 and 2i are computationally indistinguishable.Proof.
We observe that the difference between Game2i−1 and 2i respond to the i′th constrained query. In Game 2i−1, skSi⟵iOCsk,Si, while in Game 2i, skSi⟵iOCskx′,Si. In order to prove that the two games are indistinguishable, we only need to show that the circuit Csk,Si and Cskx′,Si are functionally identical.(i)
Ifx∈Si, both circuits output ⊥,⊥(ii)
For any inputx∉Si, Csk,Six=Provesk,x=Proveskx′,Si,x=Cskx′,Six
Therefore, by the security ofiO, the two experiments are indistinguishable.


### 5.4. Game 3

This game is the same as game2q2 except that y0 is replaced by a random element from Y.(i)
The challenger choosesb⟵0,1 and then generates pk,sk by running the algorithm F.Setup1λ.(ii)
The adversary makes evaluation queries or constrained queries: For the first constrained queryS1, the challenger chooses x′⟵S1 and output skS1⟵iOCsk,S1. For all evaluation queries xi before the first constrained query, the challenger outputs Fsk,xi,Psk,xi. For all queries after the first constrained query, the challenger does as follows:(1)
IfA sends an evaluation query xi such that xi=x′, the experiment aborts. Else, if xi≠x′, output Fsk,xi,Psk,xi(2)
IfA sends a constrained key query for Sj such that xi∉Sj, the experiment aborts. Else, output skSj⟵iOCsk,Sj(iii)
A sends a challenge query x∗ such that x∗≠xi for all i≤q1 and x∗∈Sj for all j≤q2. If x∗≠x′, the experiment aborts. Else, the challenger sets y0⟵Y and y1⟵Y and outputs yb,pk.(iv)
A outputs b′ and wins if b=b′.Lemma 15.
Assuming the puncturable VRFs are secure, Game2q2 and Game 3 are computationally indistinguishable.Proof.
We prove that if there exists an adversaryA that distinguishes the Game 2q2 and Game 3, then there exists another adversary ℬ that breaks the security of puncturable VRFs.
ℬ can simulate perfect experiment for A. For each evaluation query x before the first constrained key query, ℬ sends x to the puncturable VRFs′ challenger and returns y,π to A. When A queries the constrained key S1, ℬ chooses x′∈S1, sends x′ to the challenger, and receives skx′,pk,andy. Then, ℬ uses skx′ to respond the remaining queries. On receiving the challenge input x∗, ℬ checks x′=x∗ and outputs y. ℬ outputs the response of A. We observe that if y is chosen randomly, then ℬ simulates Game 3, else it simulates Game 2q2. Therefore, Game 2q2 and Game 3 are computationally indistinguishable.
We observe that bothy0 and y1 are chosen randomly from Y. Therefore, for any PPT adversary A, it has negligible advantage in Game 3. This completes the proof of Theorem 2.


## 5.1. Game 1

The first game is the original security game for our construction. Here, the challenger first chooses a pair constrained VRF keypk,sk. Then, A makes evaluation queries and constrained key queries and outputs a challenge point. The challenger responds with either a VRF evaluation or a random element.(i)
The challenger choosesb⟵0,1 and then generates pk,sk by running the algorithm F.Setup1λ(ii)
The adversary makes evaluation queries or constrained queries:(1)
IfA sends an evaluation query xi, then output Fsk,xi,Psk,xi(2)
IfA sends a constrained key query for Sj, output the constrained key skSj⟵iOCsk,Sj(iii)
A sends a challenge query x∗ such that x∗≠xi for all i≤q1 and x∗∈Sj for all j≤q2. Then, the challenger sets y0=Fsk,x∗andy1⟵Y and outputs yb,pk(iv)
A outputs b′ and wins if b=b′


## 5.2. Game 2

This game is the same as the previous one except that we introduce an abort condition. When the adversaryA makes the first constrained query S1, the challenger guesses a challenge query x′∈S1. If the last q2−1 queries Sj does not contain x′, the experiment aborts. In addition, the experiment aborts if x′≠x∗, where x∗ is the challenge query.(i)
The challenger choosesb⟵0,1 and then generates pk,sk by running the algorithm F.Setup1λ.(ii)
The adversary makes evaluation queries or constrained queries: For the first constrained queryS1, the challenger chooses x′⟵S1 and output skS1⟵iOCsk,S1. For all evaluation queries xi before the first constrained query, the challenger outputs Fsk,xi,Psk,xi. For all queries after the first constrained query, the challenger does as follows:(1)
IfA sends an evaluation query xi such that xi=x′, the experiment aborts. Else, if xi≠x′, output Fsk,xi,Psk,xi(2)
IfA sends a constrained key query for Sj such that xi∉Sj, the experiment aborts. Else, output skSj⟵iOCsk,Sj.(iii)
A sends a challenge query x∗ such that x∗≠xi for all i≤q1, and x∗∈Sj for all j≤q2. If x∗≠x′, the experiment aborts. Else, the challenger sets y0=Fsk,x∗andy1⟵Y and outputs yb,pk.(iv)
A outputs b′ and wins if b=b′.Lemma 13.
For any PPT adversaryA, if A wins with advantage ϵ in Game 1, then it wins with advantage ε/S1 in Game 2.Proof.
According the pseudorandomness defined in Section3, the challenge point belongs to the constrained set. The two experiments are equal if Game 2 does not abort. Since the challenger guesses correctly with probability 1/S1, if A wins with advantage ϵ in Game 1, then it wins with advantage ε/S1 in Game 2.


## 5.3. Game2i

For0≤i≤q2, the experiment is the same as the previous one except that the constrained queries use skx′ instead of sk in the first i experiment. We observe that the Game 20 is equal to the Game 2.(i)
The challenger choosesb⟵0,1 and then generates pk,sk by running the algorithm F.Setup1λ.(ii)
The adversary makes evaluation queries or constrained queries: For the first constrained queryS1. The challenger chooses x′⟵S1, computes skx′⟵iOCskx′,S1andπ′=Puncturesk,x′, and outputs skS1⟵iOCskx′,S1, where the description of the circuit Cskx′,S1 is given in Figure 10. For all evaluation queries xi before the first constrained query, the challenger outputs Fsk,xi,Psk,xi. For all queries after the first constrained query, the challenger does as follows:(1)
IfA sends an evaluation query xi such that xi=x′, the experiment aborts. Else, if xi≠x′, output Fsk,xi,Psk,xi=Proveskx′,xi(2)
IfA sends a constrained key query for Sj such that xi∉Sj, the experiment aborts. Else, if j≤i output skSj⟵iOCskx′,Sj, else output skSj⟵iOCsk,Sj, where the description of the circuit Cskx′,Sj is given in Figure 10.(iii)
A sends a challenge query x∗ such that x∗≠xi for all i≤q1 and x∗∈Sj for all j≤q2. If x∗≠x′, the experiment aborts. Else, the challenger sets y0=Fsk,x∗andy1⟵Y, computes, and outputs yb,pk.(iv)
A outputs b′ and wins if b=b′.Figure 10
CircuitCskx′,Sj.Lemma 14.
AssumingiO is a secure indistinguishability obfuscator, Game 2i−1 and 2i are computationally indistinguishable.Proof.
We observe that the difference between Game2i−1 and 2i respond to the i′th constrained query. In Game 2i−1, skSi⟵iOCsk,Si, while in Game 2i, skSi⟵iOCskx′,Si. In order to prove that the two games are indistinguishable, we only need to show that the circuit Csk,Si and Cskx′,Si are functionally identical.(i)
Ifx∈Si, both circuits output ⊥,⊥(ii)
For any inputx∉Si, Csk,Six=Provesk,x=Proveskx′,Si,x=Cskx′,Six
Therefore, by the security ofiO, the two experiments are indistinguishable.


## 5.4. Game 3

This game is the same as game2q2 except that y0 is replaced by a random element from Y.(i)
The challenger choosesb⟵0,1 and then generates pk,sk by running the algorithm F.Setup1λ.(ii)
The adversary makes evaluation queries or constrained queries: For the first constrained queryS1, the challenger chooses x′⟵S1 and output skS1⟵iOCsk,S1. For all evaluation queries xi before the first constrained query, the challenger outputs Fsk,xi,Psk,xi. For all queries after the first constrained query, the challenger does as follows:(1)
IfA sends an evaluation query xi such that xi=x′, the experiment aborts. Else, if xi≠x′, output Fsk,xi,Psk,xi(2)
IfA sends a constrained key query for Sj such that xi∉Sj, the experiment aborts. Else, output skSj⟵iOCsk,Sj(iii)
A sends a challenge query x∗ such that x∗≠xi for all i≤q1 and x∗∈Sj for all j≤q2. If x∗≠x′, the experiment aborts. Else, the challenger sets y0⟵Y and y1⟵Y and outputs yb,pk.(iv)
A outputs b′ and wins if b=b′.Lemma 15.
Assuming the puncturable VRFs are secure, Game2q2 and Game 3 are computationally indistinguishable.Proof.
We prove that if there exists an adversaryA that distinguishes the Game 2q2 and Game 3, then there exists another adversary ℬ that breaks the security of puncturable VRFs.
ℬ can simulate perfect experiment for A. For each evaluation query x before the first constrained key query, ℬ sends x to the puncturable VRFs′ challenger and returns y,π to A. When A queries the constrained key S1, ℬ chooses x′∈S1, sends x′ to the challenger, and receives skx′,pk,andy. Then, ℬ uses skx′ to respond the remaining queries. On receiving the challenge input x∗, ℬ checks x′=x∗ and outputs y. ℬ outputs the response of A. We observe that if y is chosen randomly, then ℬ simulates Game 3, else it simulates Game 2q2. Therefore, Game 2q2 and Game 3 are computationally indistinguishable.
We observe that bothy0 and y1 are chosen randomly from Y. Therefore, for any PPT adversary A, it has negligible advantage in Game 3. This completes the proof of Theorem 2.


## 6. Conclusion

In this work, we construct a novel constrained VRF for polynomial size set and give the proof of security under a new secure definition which is called semiadaptive security. Meanwhile, our construction is based on bilinear maps, which avoid the application of multilinear maps. Although it does not satisfy full adaptive security, it has solved some problems compared with selective security, which allows the adversary to query the evaluation oracle before it outputs the challenge point. To construct a fully adaptive security constrained VRFs is our future work.



---

*Source: 4187892-2019-11-03.xml*