See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/220337087

A Verifiable Random Function With Short Proofs and Keys.

Article · January 2004

Source: DBLP

CITATIONS READS
153 178

2 authors, including:

Yevgeniy Dodis
New York University
173 PUBLICATIONS   12,042 CITATIONS   

SEE PROFILE

All content following this page was uploaded by Yevgeniy Dodis on 13 January 2015.

The user has requested enhancement of the downloaded file.

 A Verifiable Random Function
With Short Proofs and Keys

Yevgeniy Dodis1 and Aleksandr Yampolskiy2

1
Department of Computer Science, New York University, USA. dodis@cs.nyu.edu
2
Department of Computer Science, Yale University, USA.
aleksandr.yampolsky@yale.edu

Abstract. We give a simple and efficient construction of a verifiable ran-

dom function (VRF) on groups equipped with a bilinear mapping. Our
construction is direct; it bypasses an expensive Goldreich-Levin trans-
formation from a unique signature to a VRF in contrast to prior works
of Micali-Rabin-Vadhan [MRV99] and Lysyanskaya [Lys02]. Our proofs
of security are based on a decisional bilinear Diffie-Hellman inversion as-
sumption (DBDHI), previously used in [BB04a] to construct an identity
based encryption scheme. Our VRF’s proofs and keys have constant size
in contrast to proofs and keys of VRFs in [Lys02] and [Dod03], which are
linear in the size of the message. We operate over an elliptic group, which
is significantly shorter than the multiplicative group Z∗n used in [MRV99],
yet we achieve the same security. Furthermore, our scheme can be made
distributed and proactive.

Key words. Verifiable random functions, Unique signatures, Short keys

and proofs, Bilinear groups.

1 Introduction

The notion of a verifiable random function (VRF) was introduced by Micali,

Rabin, and Vadhan [MRV99]. A VRF is a pseudo-random function that provides
a non-interactively verifiable proof for the correctness of its output. Given an
input value x, the knowledge of the secret key SK allows one to compute y =
FSK (x) together with the proof of correctness πx . This proof convinces every
verifier that the value y = FSK (x) is indeed correct with respect to the public
key of the VRF. We can view VRFs as a commitment to an exponential number
of random-looking bits.
Since their introduction, VRFs have found useful applications in protocol
design. To give a few examples, VRFs were used in [MR01] to construct a one-
time sound RZK (resettable zero-knowledge) protocol in three rounds [MR01].
In [MR02], VRFs were used to construct a non-interactive lottery system em-
ployed in micropayments [MR02]. Recently, Jarecki and Shmatikov constructed
a verifiable transaction escrow scheme, which preserves users’ anonymity while
enabling automatic de-escrow, again with the help of VRFs [JS04].
 Unfortunately, despite their utility, VRFs are not very well studied. As of
this moment, there exist only a handful of constructions in the standard model
(viz., [MRV99, Lys02, Dod03]). With the exception of [Dod03], these works first
construct a verifiable unpredictable function (VUF) (also called a unique
signature), whose output is hard to predict but does not necessarily look ran-
dom. They use an expensive Goldreich-Levin hardcore bit [GL89] to convert a
VUF into a VRF; this loses a factor in security. The size of proofs and keys
of VRFs in [Lys02, Dod03] is linear in input size, which may be undesirable in
resource-constrained environments. VRF of [MRV99] operates over a large mul-
tiplicative group Z∗n which has to be very large to achieve reasonable security.
Furthermore, before the VRF can be computed, inputs have to be mapped to
primes in a complicated fashion.
In this paper, we construct a simple VRF on groups equipped with bilinear
maps. These groups, recently discovered by Joux and Nguyen [JN01], have the
property that decisional Diffie-Hellman (DDH) assumption (given g, g a , and g b ,
distinguish g ab from random) is easy, but computational Diffie-Hellman (CDH)
assumption (given g, g a , and g b , compute g ab ) seems to be hard. This fact gives
us many useful properties like verifiability. Our construction is direct; it does
not use a Goldreich-Levin hardcore bit, saving several factors in security. The
inputs need not be primes or codewords of some special encoding. Our VRF has
proofs and keys of constant size, regardless of the size of the message. It can also
be made distributed and proactive.
We begin in Section 2 by formalizing the notions of a verifiable random
function (VRF) and a verifiable unpredictable function (VUF). We also
review the definition of bilinear groups.
Our proofs of security rely on two assumptions, which we describe in Sec-
tion 3. Roughly, they are:

− q-Diffie-Hellman inversion assumption (q-DHI) states that no efficient

q

algorithm can compute g 1/x on input g, g x , . . . , g (x ) [MSK02];
− q-decisional Diffie-Hellman inversion assumption (q-DBDHI) states
that no efficient algorithm can distinguish e(g, g)1/x from random even after
x (xq )


seeing g, g , . . . , g [BB04a].

(Here e(·, ·) is a bilinear map, which we define later.)

In Section 4, we give our constructions and analyze their efficiency.
First, in Section 4.1, we show how to turn a signature due to Boneh and
Boyen [BB04b] into a VUF for messages of small length. On input x and a
secret key SK, the signature is SignSK (x) = g 1/(x+SK) . We could then use
the approach of prior works [MRV99, Lys02] to convert this VUF into a VRF
Specifically, we could use the Goldreich-Levin hardcore bit [GL89] to convert
this VUF into a VRF with output size 1, amplify the output size to match the
size of the input, and then follow a tree-based construction to get a VRF with
arbitrary input size.
Instead, we prefer to construct a VRF directly in Section 4.2, saving several
fators in security. We give a simple direct VRF construction for small inputs,
which is secure under the q-DBDHI assumption. On input x and a secret key
SK, our VRF computes (FSK (x), π(x)), where FSK (x) = e(g, g)1/(x+SK) is the
VRF value and π(x) = g 1/(x+SK) is the proof of correctness. We can apply
a collision-resistant hash function to large inputs to transform our VRF into
a VRF with unrestricted input length. By making the group size sufficiently
large, we can construct a VRF with inputs of size roughly 160 bits, which is
the length of SHA-1 digests. In theory, we do not have to assume existence
of collision-resistant functions, and could also apply a variant of a generic tree
transformation to amplify the input size. Even though keys and proofs no longer
have constant size, the resulting VRF still has shorter keys and proof sizes than
in [MRV99, Lys02] constructions. We analyze how large the group has to be and
how our VRF compares with other constructions in Section 4.4.
Evaluating the VRF at a single server is a performance bottleneck and a
single point of failure. Naturally, in Section 5, we sketch how to make our VRF
distributed and proactive [Dod03].
In Section 6, we analyze the q-DBDHI assumption in the generic group model
à la Shoup [Sho97]. We show that if the adversary can distinguish e(g, g)1/x
p from
random with probability 21 + ǫ, he will need to perform (at least) Ω( ǫp/q)
generic group operations in a group of size p.
Conclusions and suggestions for future work appear in Section 7.

2 Definitions
Before presenting our results, we review some basic definitions and assumptions.
Let k be a security parameter. We employ the standard cryptographic model
in which protocol participants are modeled by probabilistic Turing machines
(PPTMs), whose running time is polynomial in k. Hereafter, we use negl(k) to
refer to a negligible function in the security parameter k.3

2.1 VRFs and VUFs

Let a : N 7→ N ∪ {∗} and b, s : N 7→ N be any functions for which a(k), b(k), s(k)
are computable in poly(k) time (except when a takes tha value ∗).4

Definition 1. A function family F(·) (·) : {0, 1}a(k) 7→ {0, 1}b(k) is a family
of VRFs if there exist algorithms (Gen, Prove, Ver) such that Gen(1k ) out-

puts a pair of keys (P K, SK); ProveSK (x) outputs a pair FSK (x), πSK (x) ,
where FSK (x) is the function value and πSK (x) is the proof of correctness; and
VerP K (x, y, π) verifies that y = FSK (x) using the proof π. Formally, we require:

1. Uniqueness: no values (P K, x, y1 , y2 , π1 , π2 ) can satisfy VerP K (x, y1 , π1 ) =

VerP K (x, y2 , π2 ).
3
A function negl(k) : N 7→ (0, 1) is negligible if for every c > 0, for all sufficiently
large k, negl(k) < 1/kc . See any standard reference, such as [GB99], for details.
4
When a(k) takes the value of ∗, it means the VRF is defined for inputs of all length.
2. Provability: if (y, π) = ProveSK (x), then VerP K (x, y, π) = 1.
3. Pseudorandomness: for any PPT algorithm A = (AE , AJ ), which runs
for a total of s(k) steps when its first input is 1k , and does not query the
oracle on x,
Prove(·)
 
(P K, SK) ← Gen(1k ); (x, st) ← AE (P K);
 1
Pr  b = b′ y0 = FSK (x); y1 ← {0, 1}b(k) ;  ≤ +negl(k)

′ Prove (·) 2
b ← {0, 1}; b ← AJ (yb , st)

Intuitively, the definition says that no value of the function can be distin-
guished from random, even after seeing any other function values together with
corresponding proofs.
A close relative of a VRF is a verifiable unpredictable function (VUF). It can
be thought of as a signature scheme in which a unique (at most one) signature
is accepted by the verification algorithm for every message and public key.

Definition 2. A function family F(·) (·) : {0, 1}a(k) 7→ {0, 1}b(k) is a family of
VUFs, if there exist algorithms (Gen, Sign, Ver) which satisfy the uniqueness
and provability properties of Definition 1, but the pseudorandomness property is
replaced by a weaker property:

3’ . Unpredictability: for any PPT algorithm A, which runs for a total of

s(k) steps, and does not query the oracle on x,
h i
Pr y = FSK (x) (P K, SK) ← Gen(1k ); (x, y) ← ASign(·) (P K) ≤ negl(k)

For exact security bounds, we will occasionally say that F(·) (·) is an (s′ (k), ǫ′ (k))
secure VRF (resp., VUF) if no adversary A running in time s′ (k) (and therefore
making at most s′ (k) oracle queries) can break the pseudorandomness (resp.,
unpredictability) property with ǫ′ (k) advantage.

2.2 Bilinear groups

We shall use bilinear maps to construct a verification algorithm for our VRF.
We briefly review their properties below (see [DBS04] for a more comprehensive
treatment).
Consider two (multiplicative) cyclic groups G and G1 of prime order p. Let
g be a generator of G. Roughly speaking, a mapping is bilinear if it is linear
with respect to each of its variables:

Definition 3. An (admissible) bilinear map is a map e : G × G 7→ G1 with the

following properties:

1. Bilinear: for all u, v ∈ G and x, y ∈ Z, we have e(ux , v y ) = e(u, v)xy .

2. Non-degenerate: e(g, g) 6= 1.
3. Computable: there is an efficient algorithm to compute e(u, v) for all
u, v ∈ G.
 We say that a group G is bilinear if the group action in G is efficiently
computable and there exists a group G1 and an admissible bilinear map e :
G × G 7→ G1 . Henceforth, we shall use G∗ to stand for G\{1G }.
Note that an admissible bilinear map provides an algorithm for solving the de-
cisional Diffie-Hellman problem (DDH) in G. Specifically, to determine whether
(g, g x , g y , g z ) is a DDH tuple, we can check if e(g x , g y ) = e(g, g z ). Such maps
can be constructed from Weil and Tate pairings on elliptic curves or abelian
varieties [BF01, JN01, Gal01].

3 Complexity assumptions

We now state the hardness assumptions on which our constructions are based.
In what follows, we let G be a bilinear group of prime order p, and let g be its
generator.

3.1 Diffie-Hellman inversion assumption

Our VUF construction relies on the Diffie-Hellman inversion (DHI) assumption,

originally proposed in [MSK02]. The q-DHI problem on G asks: given the (q +
q

1)-tuple g, g x , . . . , g (x ) ∈ (G∗ )q+1 as input, to compute g 1/x . Formally, an
algorithm A has advantage ǫ in solving q-DHI in G if
h q
i
Pr A(g, g x , . . . , g (x ) ) = g 1/x ≥ ǫ,

where probability is taken over the coin tosses of A and the random choice of
x ∈ Z∗p .

Definition 4. (q-DHI assumption) We say that (t, q, ǫ)-DHI assumption holds

in G if, no t-time algorithm A has advantage at least ǫ in solving the q-DHI
problem in G.

Boneh and Boyen [BB04a] pointed out that the q-DHI assumption implies
the (q + 1)-generalized Diffie-Hellman assumption (GDH), on which many cryp-
tographic constructions are based (e.g., [NR97,BS02,STW96] as well as the VUF
by Lysyanskaya [Lys02]).

3.2 Decisional bilinear Diffie-Hellman inversion assumption

In order to construct a VRF directly, we need to make a decisional bilinear Diffie-

Hellman inversion assumption (DBDHI). It was previously used in [BB04a] to
construct a selective-ID secure identity based encryption scheme.

q
The q-DBDHI problem asks: given the tuple g, g x , . . . , g (x ) as input, to
distinguish e(g, g)1/x from random. Formally, an algorithm A has advantage ǫ
in solving the q-DBDHI problem if
 h q
i h q
i
 Pr A(g, g x , . . . , g (x ) , e(g, g)1/x ) = 1 − Pr A(g, g x , . . . , g (x ) , Γ ) = 1  ≤ ǫ,
 

where the probability is over the internal coin tosses of A and the choice of
x ∈ Z∗p and Γ ∈ G1 .

Definition 5. (q-DBDHI assumption) We say that the (t, q, ǫ)-DBDHI assump-

tion holds in G if no t-time algorithm A has advantage at least ǫ in solving the
q-DBDHI problem in G.

Clearly, q-DBDHI is a stronger assumption than q-DHI. To provide more

confidence in its validity, we analyze this assumption in the generic group model
in Section 6.

4 Our constructions

In Section 4.1, we begin by showing how a signature scheme due to Boneh and
Boyen [BB04b] can be turned into a VUF with small inputs. We forego an
expensive transformation from VUFs to VRFs using a Goldreich-Levin hardcore
bit. Instead, we construct our VRF directly in Section 4.2 on inputs of small
size. We show how input size can be extended in Section 4.3. We analyze our
constructions’ efficiency in Section 4.4.
Fix input length a(k), output length b(k), and security s(k). For notational
convenience, we will usually omit the security parameter k, writing, for example,
a or s, instead of a(k) or s(k). Let G (|G| = p) be a bilinear group, where p
is a k bit prime. Let g be a generator of G. Throughout, we shall assume that
messages can be encoded as elements of Z∗p .

4.1 A verifiable unpredictable function

In order to build the intuition for our next proof, we show how to construct a
simple VUF (Gen, Sign, Ver) with small (superlogarithmic) inputs.

Algorithm Gen(1k ): Chooses a secret s ∈r Z∗p and sets the secret key to
SK = s and a public key to P K = g s .
Algorithm SignSK (x): Outputs the signature SignSK (x) = g 1/(x+SK) . Note
that the proof is embedded in the output value so we do not need to include
it explicitly.
Algorithm VerP K (x, y): Outputs 1 if e(g x · P K, y) = e(g, g); otherwise, out-
puts 0. Indeed, if the VRF value y was correctly computed, we have:

e(g x · P K, y) = e(g x g s , g 1/(x+s) ) = e(g, g).

 Boneh and Boyen proved this signature scheme to be existentially unforgeable
under weak chosen message attacks (i.e., the adversary is non-adaptive). To do
q

so, they used a q-SDH assumption which claims that on input g, g x , . . . , g (x ) ,
no efficient algorithm can compute c, g 1/(x+c) for any c ∈ Z∗p . In our proof, we

use a weaker q-DHI assumption (which implies the q-SDH assumption) to prove
the scheme’s security against adaptive adversaries. We use a trick of Micali-
Rabin-Vadhan [MRV99], which restricts messages to be of slightly superloga-
rithmic size (in security parameter k). This enables us to enumerate all possible
messages and to respond to adversary’s queries adaptively.

Theorem 1. Suppose the (s(k), 2a(k) , ǫ(k))-DHI assumption holds in a bilin-

ear group G (|G| = p). Let the input size be a(k) and output size be b(k) =
log2 p. Then (Gen, Sign, Ver) is a (s′ (k), ǫ′ (k)) unique signature, where s′ (k) =
s(k)/(2a(k) poly(k)) and ǫ′ (k) = ǫ(k) · 2a(k) .

Proof. It is easy to see that uniqueness and provability properties of Definition 2

are satisfied. We thus concentrate on residual unpredictability.
We shall use a shortcut and write q = 2a(k) . Suppose there exists an adversary
A, running in time s′ (k), which guesses the value of the function at an unseen
point with non-negligible probability ǫ′ (k). We shall construct an algorithm B
that by interacting with A breaks the q-DHI assumption with non-negligible
probability.
q

Input to the reduction: Algorithm B is given a tuple g, g α , . . . , g (α ) ∈
(G∗ )q+1 , for some unknown α ∈ Z∗p . Its goal is to compute g 1/α .
Key generation: We guess that A will output a forgery on message x0 ∈r
{0, 1}a(k) . We are right with probability 1/2a(k) ; error probability can be
decreased by repeating the algorithm sufficiently many times. Let β = α −
x0 .5 We don’t know what β is because α is secret. However, we can use the
q
q

Binomial Theorem to compute g β , . . . , g (β ) from g α , . . . , g (α ) . Because
a(k) = log(s(k)), we can enumerate all possible inputs in s(k) time. Let f (z)
be the polynomial

Y q−1
X
f (z) = (z + w) = cj z j (for some coefficients c0 , . . . , cq−1 ).
w∈{0,1}a ,w6=x0 j=0

We can compute
q−1
Y  cj q  cj−1
j Y
h = g f (β) = g (β )
and hβ = g (βj ) .
j=0 j=1

Finally, we set h to be the generator and give P K = hβ to A. The secret

key is SK = β, which we don’t know ourselves.
5
We should really have written β = α − ψ(x0 ), where ψ : {0, 1}a 7→ Z∗p . For sake of
readability, we shall abuse the notation.
Responding to oracle queries: Without loss of generality, we assume that A
never repeats a query. Consider the ith query (1 ≤ i < q) on message xi . If
xi = x0 , then we fail. Otherwise, we must compute SignSK (xi ) = h1/(xi +β) .
Let fi (z) be the polynomial

q−2
X
fi (z) = f (z)/(z + xi ) = dj z j (for some coefficients d0 , . . . , dq−2 ).
j=0

We can compute

q−2
Y dj
j
g fi (z) = g (β )
= h1/(xi +β)
j=0

and return it as the signature.

Outputting the forgery: Eventually, A outputs a forgery (x∗ , σ ∗ ). If x∗ 6= x0 ,
then our simulation failed. Because the signature is unique, we must have
σ ∗ = h1/(x0 +β) = g f (β)/(x0 +β) . Compute

q−2
X γ−1
f (z)/(z + x0 ) = γj z j + ,
j=0
z + x0

where γ−1 6= 0. Hence,

 1/γ−1
q−2
Y −γi
i
σ ∗ · g (β )  = g 1/(x0 +β) = g 1/α .
j=0

Let ǫ′ (k) = ǫ(k) · 2a(k) and s′ (k) = s(k)/(2a(k) · poly(k)). To finish the
proof, note that algorithm B succeeds with probability ǫ′ (k)/2a(k) = ǫ(k).
Its running time is dominated by answering oracle queries, and each query
takes (2a(k) − 2) · poly(k) time to answer. Therefore, B will run in roughly
s′ (k) · 2a(k) poly(k) = s(k) time.
⊓
⊔

Remark 1. The security reduction of Theorem 1 is not tight. It allows to con-

struct VUFs with input roughly a(k) = Ω(log s(k)). In theory, this means that
the input size we can achieve might be only slightly superlogarithmic in k (similar
to [MRV99]). First, it might be reasonable to assume subexponential hardness
of the q-DHI assumption which will immediately allow one to support input of
size k Ω(1) . Also, by utilizing a collision-resistant hash function, we will anyway
only need to construct VUFs with relatively small input size such as 160 bits.
Indeed, in Section 4.4, we show that our construction seems to yield practical
and secure VUF for inputs of arbitrary length already when k = 1000 bits.
4.2 A verifiable random function
Our main contribution is a direct construction of a verifiable random function
from a slightly stronger q-DBDHI assumption. The VRF (Gen, Prove, Ver) is
as follows.
Algorithm Gen(1k ): Selects a random s ∈ G and sets the secret key to SK = s
and the public key to P K = g s .

Algorithm ProveSK (x): We let ProveSK (x) = FSK (x), πSK (x) where
FSK (x) = e(g, g)1/(x+SK) is the VRF output and πSK (x) = g 1/(x+SK) is
the proof of correctness.
Algorithm VerP K (x, y, π): To verify whether y was computed correctly, check
if e(g x · P K, π) = e(g, g) and whether y = e(g, π). If both checks succeed,
output 1; otherwise, output 0.
We can prove this scheme to be secure (in the sense of Definition 1) for small
inputs (superlogarithmic in k). We then show how to convert it into a VRF with
unrestricted input size.
Theorem 2. Suppose the (s(k), 2a(k) , ǫ(k))-decisional BDHI assumption holds
in a bilinear group G (|G| = p). Let the input size be a(k) and output size
be b(k) = log2 p. Then (Gen, Prove, Ver), as defined above, is a (s′ (k), ǫ′ (k))
verifiable random function with s′ (k) = s(k)/(2a(k) · poly(k)) and ǫ′ (k) = ǫ(k) ·
2a(k) .
Proof. It is trivial to show that uniqueness and provability properties of Defini-
tion 1 are satisfied. We thus concentrate on the pseudorandomness property.
We shall use q = 2a(k) as a shortcut. For sake of contradiction, suppose there
exists an algorithm A = (AE , AJ ), which runs in time s′ (k), and can distinguish
between FSK (x) = e(g, g)1/(x+s) (for some x) and a random element in G1 with
probability at least 1/2 + ǫ′ (k). We shall construct an algorithm B that uses A
to break the q-DBDHI assumption in G.
q
Input to the reduction: Algorithm B is given a tuple (g, g α , . . . , g (α ) , Γ ) ∈
(G∗ )q+1 × G1 , where Γ is either e(g, g)1/α ∈ G1 or a random element in G1 .
Its goal is to output 1 if Γ = e(g, g)1/α and 0 otherwise.
Key generation: We guess that A will choose to distinguish the VRF value
on message x0 ∈ {0, 1}a(k). Let β = α − x0 (see footnote 5). We generate the
public and private keys for algorithm A as in the proof of Theorem 1. Using
q

the Binomial Theorem, we compute the tuple g β , . . . , g (β ) . We define

Y q−1
X
f (z) = (z + w) = cj z j .
w∈{0,1}a ,w6=x0 j=0

This enables us to compute the new base

q−1
Y  cj
j
h = g f (β) = g (β )
.
j=0
  j cj−1
Finally, we give P K = hβ = qj=1 g (β )
Q
as the public key to A. The
secret key is SK = β, which we don’t know.
Remark 2. We can pre-compute e(g, g) and e(h, h) to speed up subsequent
computation.
Responding to oracle queries: Consider the ith query (1 ≤ i < q) on mes-
sage xi . If xi = x0 , we fail. Otherwise, we must respond with the correspond-
ing proof πSK (xi ) and a VRF value FSK (xi ).
As in Theorem 1, we define
q−2
X
fi (z) = f (z)/(z + xi ) = dj z j (for some coefficients d0 , . . . , dq−2 ).
j=0

We can thus compute

q−2
Y dj
j
πSK (xi ) = g (β )
= h1/(β+xi )
j=0

and
FSK (xi ) = e(h, πSK (xi )) = e(h, h)1/(β+xi ) ,
and return them to algorithm A.
Challenge: Eventually, A outputs a message x∗ on which it wants to be chal-
lenged. If x∗ 6= x0 , then we fail. Otherwise, A claims to be able to distinguish
e(h, h)1/(β+x0 ) = e(h, h)1/α from a random element in G1 . Recall that
q−1
X
f (z) = ci z i .
i=0

Because f (z) is not divisible by (z + x0 ), we have:

γ
f ′ (z) = f (z)/(z + x0 ) −
z + x0
q−2
X
= γj z j (for some γ 6= 0 and coefficients γ0 , . . . , γq−2 ).
j=0

Let Γ0 be
 
Y q−2
q−1 q−2
!
Y  i j
 c i γ j Y  t
γ· γm
Γ0 =  e g (β ) , g (β ) · e g, g (β )
i=0 j=0 m=0
 ′
  ′

= e g f (β) , g f (β) · e g γ , g f (β) (1)
2
− γ 2 )/α
= e(g, g)(f (β) .
2
Set Γ ∗ = Γ (γ ) ·Γ0 . Notice that if Γ = e(g, g)1/α , then Γ ∗ = e(g f (β) , g f (β)/α ) =
e(h, h)1/α . Meanwhile, if Γ is uniformly distributed, then so is Γ ∗ . We give
Γ ∗ to algorithm A.
 Remark 3. We can see from Equation (1) that it takes only two bilinear map
evaluations to compute Γ0 .

Guess: Algorithm A makes some more queries to which we respond as before.

Finally, A outputs a guess b ∈ {0, 1}. We return b as our guess as well.

The running time of the reduction is dominated by simulating oracle queries.

Per every query, we must perform one bilinear map evaluation (this takes poly(k)
time) and (2a − 2) multiplications and exponentiations (this takes 2a · poly(k)
time). Because A can make at most s′ (k) queries, the running time of B is alto-
gether s′ (k)(2a(k) ·poly(k)). The advantage of B in this experiment is ǫ′ (k)/2a(k) .
Setting s′ (k) = s(k)/(2a(k) · poly(k)) and ǫ′ (k) = ǫ(k) · 2a(k) completes the proof.
⊓
⊔

4.3 Extending the input size

Hashing the input. We constructed a VRF (Gen, Prove, Ver) with inputs of
small size a(k) = Ω(log(k)) and output size b(k). We point out a trivial ob-
servation that if we have an unpredictable or verifiable random function func-
tion ProveSK (·) : {0, 1}a 7→ {0, 1}b and a collision-resistant hash function
H(·) : {0, 1}c 7→ {0, 1}a (c > a), then their composition ProveSK (H(·)) :
{0, 1}c 7→ {0, 1}b is secure. Although our security reduction is relatively loose,
we can make the size of bilinear groups large enough (we give precise numbers
in Section 4.4) to have inputs of length roughly a(k) = 160 bits, the length of
SHA-1 digests. Restriction to small inputs is therefore not limiting because we
can always hash longer inputs.

Tree construction. Although, we recommend using the previous construction

(by making the group large enough), in theory, we could always use the generic
tree construction (which is inefficient) to extend the input length. Then, we do
not have to assume the existence of a collision-resistant hash function; having a
universal hash function suffices:

Proposition 1 ([MRV99]). If there is a VRF with input length a(k), output

length 1, and security s(k), then there is a VRF with unrestricted input length,
output length 1 and security at least min(s(k)1/5 , 2a(k)/5 ).

The proof begins by converting a VRF with output length 1 into a VRF with
output length (a− 1). This transformation loses a factor of a in security. Because
our VRF has output length much larger than 1, we can omit this step. Instead,
we apply a universal hash function to VRF’s output and let the VRF’s value be
the first (a − 1) bits of hash function’s output (it is easily seen that these bits
will be pseudo-random as well).
The rest of the transformation proceeds as usual: The root of the binary
tree is labeled with 0a−1 and children of node y are labeled with short VRF’s
values on inputs (y ◦ 0) and (y ◦ 1). The tree’s depth is precisely the input size
|x|. Computing the VRF value on input x (of unrestricted length) amounts to
computing labels of nodes on the path from the root of the tree to the leaf
corresponding to x. The proof of correctness is the tuple of short VRF’s proofs,
one proof per each node on the path traced by x.6
We note that both of the aforementioned techniques can be used to convert
the VUF in Section 4.1 into a VUF with unrestricted input length.

4.4 Efficiency
We now compare efficiency of our construction with efficiency of prior VRF
constructions. Fix inputs to be a(k) = 160 bits, the length of SHA-1 digests,
and let q = 2a(k) .

Our VRF. According to Theorem 2, if (s(k), q, ǫ(k))-DBDHI holds on G, then

our VRF is secure against adversaries running in time s′ (k) = s(k)/(2a(k) ·
poly(k)) that have advantage ǫ′ (k) = ǫ(k) · 2a(k) . To be generous, we instantiate
ǫ′ (k) = 2−80 , s′ (k) = 280 , and poly(k) = 230 . Then, we have: ǫ(k) = 2−240 and
s(k) = 2270 . Suppose there is no better algorithm for breaking the q-DBDHI
assumption than a generic group algorithm. Then, by Theorem 3 (which we
prove in Section 6), for these security parameters, a bilinear group must have
size:
2(s(k) + q + 3)2 q
p≥
ǫ(k)

2
2 2270 + 2160 + 3 2160
=
2−240
940
≈2 .
Therefore, making the group size be a 1,000 bit prime seems sufficient to guar-
antee security of the VRF that takes 160 bit inputs. Proofs and keys consist of a
single group element and will roughly be 125 bytes each. We can generate such
groups using the standard parameter generator of [BF01].

VRF by [MRV99]. Micali-Rabin-Vadhan VRF operates over a multiplicative

group Z∗n , where n = pq is a k-bit RSA modulus. The fastest general-purpose fac-
toring
 algorithm todayis the number field sieve [BLZ94]; it takes approximately
1/3
(log k)2/3 )
O e1.9223(k time to factor a k bit number. The RSA based VUF (not
even a VRF) constructed in [MRV99] has security s′ (k) = s(k)/(2a(k) · poly(k))
where s(k) is hardness of RSA. Letting s′ (k) = 280 and poly(k) = 230 as before,
we obtain RSA security lower bound s(k) = 280 · (2160 · 230 ) = 2270 . Because
RSA is only secure as long as we cannot factor n, to get 270 bits of security, we
need n to be a k-bit number, where
1.9223k 1/3(log k)2/3 = 270.
6
The inputs have to be prefix-free for this tree construction to work; this can be
accomplished using techniques of [MRV99].
 Hence, n must be at least 14, 383 bits long if we want to use this VUF on
160 bit inputs. After following the tree construction, proofs for 160 bit inputs
will have size 280 kilobytes.

VRF by [Dod03] and VUF by [Lys02]. These constructions work on elliptic

curve groups, whose size is usually a 160 bit prime. At the bare minimum, 160
bit messages yield keys and proofs of size 160 · 160 = 25, 600 bits, which is
about 3.2 kilobytes. In fact, they will probably have larger size due to use of
error-correcting codes and other encoding expansions.
To summarize, none of the prior VRF constructions come close to the 1,000
bit proofs and keys of our construction. Even if our VRF is used with the generic
tree construction, the keys and proofs contain only one group element per bit of
the input (|x| elements altogether). This is less than |x| group elements per bit
of the input (|x|2 elements altogether) contained by keys and proofs of a VRF
in (Section 5, [Lys02]).

5 Distributed VRF
We point out that our VUF/VRF constructions can be easily made distributed
(or even proactive). Indeed, both of the constructions simply amount to a secure
computation of the function πs (x) = g 1/(x+s) when the servers have shares of
the secret s. Since it is well known how to do multiparty addition, inversion,
and exponentiation [BIB89, BoGW88], this extension follows immediately. We
notice however that unlike the construction of Dodis [Dod03], our distributed
VUF/VRF is interactive.

6 Generic Security of the q-DBDHI Assumption

In this section, we examine the q-DBDHI assumption in the generic group
model [Sho97].
In the generic group model, elements of G and G1 are encoded as unique
random strings. We define an injective function θ : Zp 7→ {0, 1}∗, which maps
a ∈ Zp to the string representation θ(g a ) of g a ∈ G. Similarly, we define θ1 :
Zp 7→ {0, 1}∗ for G1 . The encodings are such that non-group operations are
meaningless. There exist three oracles which compute the group action in G, the
group action in G1 , and the bilinear pairing e : G × G 7→ G1 from elements’
encodings.
Theorem 3. Let A be an algorithm that solves the q-DBDHI problem. Suppose
that x ∈ Z∗p and encoding functions θ, θ1 are chosen at random. If A makes at
most qG queries to oracles computing the group action in G, G1 and the bilinear
mapping e : G × G 7→ G1 , then
 " # 
r

A p, θ(1), θ(x), . .
. , θ(xq ), b ← {0, 1}; 1  2(qG + q + 3)2 q
Pr − ≤ .

r
 θ1 (Γ0 ), θ1 (Γ1 ) = b Γb ← 1/x; Γ1−b ← Z∗p 2 p
Proof. Instead of letting A interact with the actual oracles, we play the following
game.
We maintain two lists: L = { (Fi , si ) : i = 0, . . . , t − 1} and L′ = { (Fi′ , s′i ) :
i = 0, . . . , t′ − 1}. Here si , s′i ∈ {0, 1}∗ are encodings and Fi , Fi′ ∈ Zp [X, Γ0 , Γ1 ]
are multivariate polynomials in X, Γ0 , and Γ1 . The total length of lists at step
τ ≤ qG in the game must be

t + t′ = τ + q + 3. (2)

At the beginning of the game, we initialize the lists to F0 = 1, F1 = X, . . . , Fq =

X q and F0′ = Γ0 , F1′ = Γ1 . The corresponding encodings are set to arbitrary
distinct strings in {0, 1}∗. The lists have length t = q + 1 and t′ = 2.
We start the game by providing A with encodings (s0 , . . . , sq , s′0 ). Algorithm
A begins to issue oracle queries. We respond to them in the standard fashion:

Group action: Given a multiply/divide bit and two operands si and sj (0 ≤

i, j < t), we compute Ft = Fi ± Fj accordingly. If Ft = Fl for some l < t, we
set st = sl . Otherwise, we set st to a random string in {0, 1}∗ \{s0 , . . . , st−1 },
and increment t by 1. Group action in G1 is computed similarly, except we
operate on list L′ .
Bilinear pairing: Given two operands si and sj (0 ≤ i, j < t), we compute the
product Ft′ = Fi Fj . If Ft′ = Fl for some l < t′ , we set st′ = sl . Otherwise
we set it to a random string in {0, 1}∗\{s0 , . . . , st′ −1 }. We then increment t′
by 1.

After making at most qG queries, A halts with a guess b̂ ∈ {0, 1}. We now
r
choose x, y ← Z∗p and consider Γb ← 1/x, Γ1−b = y for both choices of b. Our
simulation is perfect and reveals nothing to A about b unless the values that we
chose for indeterminates give rise to some non-trivial equality relation. Specifi-
cally, algorithm A wins the game if for any Fi 6= Fj or any Fi′ 6= Fj′ , either of
these hold:

1. Fi (x, 1/x, y) − Fj (x, 1/x, y) = 0

2. Fi (x, y, 1/x) − Fj (x, y, 1/x) = 0
3. Fi′ (x, 1/x, y) − Fj′ (x, 1/x, y) = 0
4. Fi′ (x, y, 1/x) − Fj′ (x, y, 1/x) = 0

Notice that A can never engineer an encoding of an element whose cor-

responding polynomial would have a 1/X term unless he is explicitly given it.
Therefore, we can only get a non-trivial equality relation as a result of numerical
cancellation.
For all i, we have: deg(Fi ) ≤ q and deg(Fi′ ) ≤ 2q. We can use the Schwartz-
Zippel Theorem [Sch80] to bound the probability of a cancelation. It tells us
that for all i, j, Pr[Fi − Fj = 0] ≤ q/p and Pr[Fi′ − Fj′ = 0] ≤ 2q/p. Thus A’s
advantage is
   ′ 
t q t 2q
ǫ≤2· +
2 p 2 p
q
< 2(qG + q + 3)2 (using Equation (2))
p
 2 3

q q+q
=O G .
p
⊓
⊔

It turns out that in a generic group model algorithm A that solves the q-
DBDHI problem has advantage, which is roughly twice as much as an advantage
of an algorithm solving the q-SDH problem (see [BB04b], Section 5); the asymp-
totic complexities are the same.
The following corollary is immediate.

Corollary 1. Any adversary that breaks the q-DBDHI assumption with proba-
√
bility ν = 21 + ǫ (0 < ǫ < 1/2) in generic groups of order p such that q < o( 3 p)
p
requires Ω( ǫp/q) generic group operations.

7 Conclusion
We have presented a simple and efficient construction of a verifiable random
function. Our VRF’s proofs and keys have constant size regardless of the size of
the input. Our proofs of security are based on a bilinear Diffie-Hellman inversion
assumption, which seems reasonable given current state of knowledge. We also
demonstrated that our scheme can be instantiated with elliptic groups of very
reasonable size which makes our constructions quite practical.

References
[BB04a] Dan Boneh and Xavier Boyen. Efficient selective-ID secure identity
based encryption without random oracles. In Advances in Cryptology—
EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science,
pages 223–238. Berlin: Springer-Verlag, 2004.
[BB04b] Dan Boneh and Xavier Boyen. Short signatures without random oracles.
In Advances in Cryptology—EUROCRYPT 2004, volume 3027 of Lecture
Notes in Computer Science, pages 56–73. Berlin: Springer-Verlag, 2004.
[BF01] Dan Boneh and Matt Franklin. Identity-based encryption from the Weil
pairing. Lecture Notes in Computer Science, 2139:213–229, 2001.
[BIB89] Judit Bar-Ilan and Donald Beaver. Non-cryptographic fault-tolerant com-
puting in a constant number of rounds. In Proceedings of the ACM Sympo-
sium on Principles of Distributed Computation, pages 201–209, 1989.
[BLZ94] Johannes A. Buchmann, J. Loho, and J. Zayer. An implementation of the
general number field sieve. Lecture Notes in Computer Science, 773:159–166,
1994.
 [BoGW88] Michael Ben-or, Shafi Goldwasser, and Avi Wigderson. Completeness the-
orems for non-cryptographic fault-tolerant distributed computing. In Pro-
ceedings of the 20th Annual ACM Symposium on the Theory of Computing,
pages 1–10, 1988.
[BS02] Dan Boneh and Alice Silverberg. Application of multilinear forms
to cryptography. Cryptology ePrint Archive, Report 2002/080, 2002.
http://eprint.iacr.org/2002/080/.
[DBS04] Ratna Dutta, Rana Barua, and Palash Sarkar. Pairing-based cryptographic
protocols : a survey. Cryptology ePrint Archive, Report 2004/064, 2004.
http://eprint.iacr.org/2004/064/.
[Dod03] Yevgeniy Dodis. Efficient construction of (distributed) verifiable random
functions. In Proceedings of 6th International Workshop on Theory and
Practice in Public Key Cryptography, pages 1–17, 2003.
[Gal01] Steven D. Galbraith. Supersingular curves in cryptography. Lecture Notes
in Computer Science, 2248:495–513, 2001.
[GB99] S. Goldwasser and M. Bellare. Lecture notes on cryptography. Summer
Course “Cryptography and Computer Security” at MIT, 1996–1999, 1999.
[GL89] Oded Goldreich and Leonid Levin. A hard-core predicate for all one-way
functions. In Proceedings of the 21th Annual ACM Symposium on the The-
ory of Computing, pages 25–32, 1989.
[JN01] Antoine Joux and Kim Nguyen. Separating Decision Diffie-Hellman from
Diffie-Hellman in cryptographic groups. Cryptology ePrint Archive, Report
2001/003, 2001. http://eprint.iacr.org/2001/003/.
[JS04] Stanislaw Jarecki and Vitaly Shmatikov. Handcuffing big brother : an abuse-
resilient transaction escrow scheme. In Advances in Cryptology - Proceedings
of EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science,
pages 590–608. Springer-Verlag, 2004.
[Lys02] Anna Lysyanskaya. Unique signatures and verifiable random functions from
DH-DDH separation. In Proceedings of the 22nd Annual International Cryp-
tology Conference on Advances in Cryptology, pages 597–612, 2002.
[MR01] Silvio Micali and Leonid Reyzin. Soundness in the public-key model. Lecture
Notes in Computer Science, 2139:542–565, 2001.
[MR02] Silvio Micali and Ronald L. Rivest. Micropayments revisited. In CT-RSA,
pages 149–163, 2002.
[MRV99] Silvio Micali, Michael O. Rabin, and Salil P. Vadhan. Verifiable random
functions. In Proceedings of the 40th IEEE Symposium on Foundations of
Computer Science, pages 120–130, 1999.
[MSK02] Shigeo Mitsunari, Ryuichi Sakai, and Masao Kasahara. A new traitor trac-
ing. IEICE Trans. Fundamentals, pages 481–484, 2002.
[NR97] Moni Naor and Omer Reingold. Number-theoretic constructions of efficient
pseudo-random functions. In Proceedings of the 38th IEEE Symposium on
Foundations of Computer Science, pages 458–467, 1997.
[Sch80] Jacob T. Schwartz. Fast probabilistic algorithms for verification of poly-
nomial identities. Journal of the Association for Computing Machinery,
27:701–717, 1980.
[Sho97] Victor Shoup. Lower bounds for discrete logarithms and related problems.
Lecture Notes in Computer Science, 1233:256–266, 1997.
[STW96] Michael Steiner, Gene Tsudik, and Michael Waidner. Diffie-Hellman key
distribution extended to group communication. In Proceedings of the 3rd
ACM Conference on Computer and Communications Security, pages 31–37,
1996.

View publication stats