Verifiable Random Function (VRF)

We present an overview of verifiable random functions (VRF) and describe a construction a VRF based on elliptic curves in PWHVNRG17.

Informally speaking, a VRF is a function that generates values that looks indistinguishable from random, and these values can be verified if they were computed correctly. Later, we discuss a few cryptographic applications that VRF possibly plays an important building blocks in constructing them.

The chapter is separated into $2$ two major parts. In the first part, we state the formal definition of VRF including its syntax and security properties. Then we talk about the history of VRFs to see its development. In the second major part, we describe the VRF based on elliptic curve and our implementation of the VRF.

Author(s): phamnhatminh1292001

Overview of VRF

In this chapter, we present an overview of VRFs. First, we give a short introduction of VRF including its intuition and importance in cryptography. After that, we discuss the formal definition of VRF and its security requirements. Finally, we talk about the history of VRF to see its development.

Introduction

In cryptography, a verifiable random function (VRF) is a public key version of a pseudorandom function. It produces a pseudorandom output and a proof certifying that the output is computed correctly.

A VRF includes a pair of keys, named public and secret keys. The secret key, along with the input is used by the holder to compute the value of a VRF and its proof, while the public key is used by anyone to verify the correctness of the computation.

The issue with traditional pseudorandom functions is that their output cannot be verified without the knowledge of the seed. Thus a malicious adversary can choose an output that benefits him and claim that it is the output of the function. VRF solves this by introducing a public key and a proof that can be verified publicly while the owner can keep secret key to produce numbers indistinguishable from randomly chosen ones.

VRF has applications in various aspects. Among them, in internet security, it is used to provide privacy against offline enumeration (e.g. dictionary attacks) on data stored in a hash-based data structure irtf-vrf15. VRF is also used in lottery systems MR02 and E-cashes BCKL09.

VRF Algorithms

Formally, a Verifiable random function consists of three algorithms $(\mathsf{Gen}, \mathsf{Eval}, \mathsf{Verify})$ where:

$(pk,sk) \leftarrow \mathsf{Gen}(1^{\lambda})$: This algorithm takes as input as a security parameter $\lambda$ and outputs a key pair $(pk,sk)$.

$(Y,\pi) \leftarrow \mathsf{Eval}(X,sk)$: This algorithm takes as input a secret key $sk$ and a value $X$ and outputs a value $Y \in {0,1}^{out(\lambda)}$ and a proof $\pi$.

$b \leftarrow \mathsf{Verify}(pk,X,Y,\pi)$: This algorithm takes an input a public key $pk$, a value $X$, a value $Y$, a proof $\pi$ and outputs a bit $b$ that determines whether $Y=\mathsf{Eval}(X,sk)$.

VRF Security Properties

We need a VRF to satisfy the following properties:

Correctness: If $(Y,\pi)=Eval(sk,X)$ then $Verify(pk,X,Y,\pi)=1$

Uniqueness: There do not exist tuples $(Y,\pi)$ and $Y',\pi'$ with $Y \ne Y'$ and: $\mathsf{Verify}(pk,X,Y,\pi)=\mathsf{Verify}(pk,X,Y',\pi')=1$

Pseudorandomess: For any adversary $\mathcal{A}$ the probability $|Pr[ExpRand^A_{VRF}(\lambda)=1]-\dfrac{1}{2}|$ is negilible where $ExpRand_{VRF}^{\mathcal{A}}(1^\lambda)$ is defined as follows:

$ExpRand_{VRF}^{\mathcal{A}}(1^\lambda)$:

• $(sk,pk) \leftarrow \mathsf{Gen}(1^{\lambda})$
• $(X^*,st) \leftarrow \mathcal{A}^{\mathcal{O_{VRF}}(.)}(pk)$
• $Y_0 \leftarrow \mathsf{Eval}(X*,sk)$
• $Y_1 \leftarrow \\{0,1\\}^{out(\lambda)}$
• $b {\stackrel{\$}{\leftarrow}} \\{0,1\\}$
• $b' \leftarrow \mathcal{A}(Y_b,st)$
• Return $b=b'$

The oracle $\mathcal{O_{VRF}}(.)$ works as follow: Given an input $x$, it outputs the VRF value computed by $x$ and its proof.

In the paper of PWHVNRG17, the authors stated that a VRF must also be collision resistant. This property is formally defined below:

Collision Resistant: Collision Resistant: For any adversarial prover $\mathcal{A}=(\mathcal{A_1},\mathcal{A_2})$ the probability $Pr\left[ExpCol_{VRF}^\mathcal{A}(1^\lambda)=1\right]$ is negligible where $ExpCol_{VRF}^\mathcal{A}(1^\lambda)$ is defined as follows:

$ExpCol_{VRF}^\mathcal{A}(1^\lambda)$:

• $(pk,sk) \leftarrow \mathcal{A_1}(\mathsf{Gen}(1^{\lambda}))$
• $(X,X',st) \leftarrow \mathcal{A_2}(sk,pk)$
• Return $X \ne X'$ and $\mathsf{Eval}(X,sk)=\mathsf{Eval}(X',sk)$

It is interesting to see that, VRF can be used for signing messages. However, several signing algorithms such as ECDSA cannot be used to build a VRF. For a given message and a secret key, there can be multiple valid signatures, thus an adversiral prover could produce different valid outputs from a given input, and chooses the one that benefits him. This contradicts the uniqueness property of VRF.

History of Verifiable Random Function

Verifiable Random Function is introduced by Micali, Rabin and Vadhan MRV99. They defined a Verifiable Unpredictable Function (VUF) and gave a construction based on the RSA assumption MRV99, then proved that a VRF can be constructed from a VUF MRV99.

In 2002, Lysyanskaya Lysyanskaya02 also followed the same path by constructing a VUF instead VRF. However, Lysyanskaya's VUF is based on Diffie-Hellman assumption instead, and it is the first construction that is based on Diffie-Hellman assumption.

In 2005, Dodis and Yampolsky DY05 gave a direct and efficient construction using bilinear map, then improved. Later, during the 2010s, many constructions HW10,BMR10,Jag15 also used bilinear map, all of them used non standard assumptions to prove the security of their VRF.

In 2015, Hofheinz and Jager HJ15 constructed a VRF that is based on a constant-size complexity assumption, namely the $(n-1)$-linear assumption. The $(n-1)$-linear assumption is not easier to break as $n$ grows larger, as opposed to all the assumptions used by previous constructions HS07.

In 2017, PWHVNRG17 construct an efficient VRF based on elliptic curve that does not use bilinear map to produce output and verify, instead they only use hash functions and elliptic curve operations. In the other hand, their hash function is viewed as random oracle model in the construction.

In 2019, Nir Bitansky Bit19 showed that VRF can be constructed from non-interactive witness-indistinguishable proof (NIWI).

In 2020, Esgin et al EKSSZSC20 was the first to construct a VRF based on lattice based cryptography, which is resistant to attack from quantum computers. Thus, VRF remains as a good candidate for generating randomness in the future.

VRF Based on Elliptic Curves (ECVRF)

In this chapter, we describe a VRF Based on Elliptic Curves in the paper of PWHVNRG17. The Internet Research Task Force (IRTF) also describes this VRF in their Internet-Draft irtf-vrf15. The security proof of the VRF is in PWHVNRG17, we do not present it here. Then we will present our implementation of the VRF.

Why using ECVRF

There are many VRF constructions, as listed in the history of VRF. However, ECVRF is chosen because its efficient in both proving and verification complexity, and can be make distributed.

For example, in the construction of Hohenberger and Waters HW10, the proof of the VRF contains $\Theta(\lambda)$ group elements. The number of evaluation steps is $\Theta(\lambda)$, because we need to compute $\Theta(\lambda)$ group elements. Verification require $\Theta(\lambda)$ computations using bilinear map, where $\lambda$ is the security parameter. It is unknown whether this VRF can be made distributed or not.

On the other hand, the proof size and the number of evaluation and verification steps of ECVRF are all constant and can be make distributed, as in the paper of Galindo et al GLOW20. The VRF construction of DY05 also have constant proof size, evaluation and verification steps, and can be make distributed. However, in their paper, they require a cyclic group whose order is a 1000 bit prime, while ECVRF require a cyclic group whose order is a 256 bit prime such that the Decisional Diffie-Hellman (DDH) assumption holds. Hence, we can implement the VRF using Secp256k1, a curve used by Ethereum for creating digital signature. The embeeding degree of Secp256k1 is large, thus the DDH assumption is believed to be true.

ECVRF construction

Public Parameters

Let $\mathbb{G}$ be a cyclic group of prime order $p$ with generator $g$. Denote $\mathbb{Z}_p$ to be the set of integers modulo $p$. Let $\mathsf{EncodeToCurve}$ be a hash function mapping a bit string to an element in $\mathbb{G}$. Let $\mathsf{ChallengeGeneration}$ be a hash function mapping arbitary input length to a $256$ bit integer.

Note that, in the paper of PWHVNRG17, the functions $\mathsf{EncodeToCurve}$ and $\mathsf{ChallengeGeneration}$ are modeled as random oracle model. This is used to prove the security of the VRF.

The cofactor parameter mentioned in the irtf draft is set to $1$.

The $\mathsf{Eval}$ function is split into 2 functions: $\mathsf{Prove}$ and $\mathsf{ProofToHash}$. The $\mathsf{Prove}$ function returns the proof of the ECVRF, and the $\mathsf{ProofToHash}$, returns the ECVRF output.

ECVRF Construction

$\mathsf{KeyGen}(1^{k})$: Choose a random secret value $sk \in \mathbb{Z}_p$ and the secret key is set to be $sk$. The public key is $pk=g^{sk}$.

$\mathsf{Prove}(sk,X)$: Given the secret key $sk$ and an input $X$, the proof $\pi$ of ECVRF is computed as follow:

1. Compute $h=\mathsf{EncodeToCurve}(X,pk)$.

2. Compute $\gamma=h^{sk}$.

3. Choose a value $k$ uniformly in $\mathbb{Z}_p$.

4. Compute $c=\mathsf{ChallengeGeneration}(h,pk,gamma,g^k,h^k)$.

5. Compute $s \equiv k-c.sk \pmod{q}$.

6. The proof $\pi$ of the VRF is computed as $\pi=(\gamma,c,s)$.

$\mathsf{ProofToHash}(gamma)$: Given input $\gamma$ that is calculated during the $\mathsf{Prove}$ function, this function returns the output of ECVRF.

1. Compute $gammastr=\mathsf{PointToString}(\gamma)$.

2. Let $gammastr=PointToString(\gamma)$.

3. Let $suite-string$="0x01".

4. Let $separator-front$="0x03".

5. Let $separator-back$="0x00".

6. Let $Y=\mathsf{keccak}(suite-string || seperator-front || gammastr || seperator-back)$.

7. Return $Y$.

$\mathsf{Verify}(pk,X,Y,\pi)$: Given the public key $pk$, the VRF input $X$, the VRF output $Y$ and its proof $\pi=(\gamma,c,s)$, the verification step proceeds as follow:

1. Check if $\gamma$ and $pk$ is on the curve.

2. Compute $u=pk^cg^s$.

3. Compute $h=\mathsf{EncodeToCurve}(X,pk)$.

4. Compute $v=\gamma^ch^s$.

5. Check if $c=\mathsf{ChallengeGeneration}(h,pk,gamma,g^k,h^k)$. If the check is valid, output $Y=\mathsf{ProofToHash}(\gamma)$, otherwise output $Invalid$.

ECVRF Auxiliary Functions

In this section, we describe the construction of $HashToCurve$ and $HashPoint$ in the Internet-Draft of irtf. More details can be found in irtf-vrf15.

$\mathsf{EncodeToCurve}(X,pk)$: Given two group elements $X, pk \in \mathbb{G}$, the function output a hash value in $\mathbb{Z}_p$ as follows:

1. Let $ctr=0$.

2. Let $suite-string$="0x01".

3. Let $seperator-front$="0x01".

4. Let $seperator-back$="0x00".

5. Compute $pkstr=\mathsf{PointToString}(pk)$.

6. Define $H$ to be "INVALID".

7. While $H$ is "INVALID" or $H$ is the identity element of the group:

   • Compute $ctrstr=\mathsf{IntToString}(ctr)$.

   • Compute $hstr=\mathsf{keccak}( suite-string || seperator-front || pkstr || X || ctrstr || seperator-back)$.

   • Compute $H$=$\mathsf{StringToPoint}(hstr)$.

   • Increment $ctr$ by $1$.

8. Output $H$.

$\mathsf{ChallengeGeneration}(P_1,P_2,...,P_n)$: Given n elements in $\mathbb{G}$, the hash value is computed as follows:

1. Let $suite-string$="0x01".

2. Let $seperator-front$="0x02".

3. Initialize $str=suite-string || seperator-front$.

4. For $i=1,2,...,n$:

   • Update $str= str || \mathsf{PointToString}(P_i)$.

5. Let $separator-back$="0x00".

6. Update $str=str || separator-back$.

7. Update $str=\mathsf{keccak}(str)$.

8. Compute $c=\mathsf{StringToInt}(str)$.

9. Output $c$.

The function $\mathsf{PointToString}$ converts a point of an elliptic curve to a string. Many programming supports this function. For example, in python, we can use $str(G)$ to return the string representation of a point$G$.

The function $\mathsf{StringToPoint}$ converts a string to a point of an elliptic curve. It is specified in section 2.3.4 of SECG1.

Implementation

We implement the ECVRF described above in python and rust. We choose the curve secp256k1 instead of the curve P-256 recommended in [irtf-vrf08]. We also use the keccak hash instead of SHA256 as in [irtf-vrf08]. The functions $\mathsf{StringToCurve}$ and $\mathsf{StringToField}$ in SECG01 are used. The paper SECG01 implement these functions for a general curve, therefore it will contain many steps. However, we only need to implement some of them, since we are using the curve secp256k1.

ECVRF implementation in Python

The implememtation of the ECVRF in python. The steps and details are written on the comments of the implementation. Below are the global variables. We use the ecdsa library, but the curve curve_256 of the library is replaced with the curve secp256k1. Instead of using SHA256 as in irtf-vrf15, we use the keccak hash function.

G = generator_256
ORDER = G.order()
order_minus_one=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140
INFINITY=Point(None,None,None)
suite_string=b"0x01"

ECVRF main functions

The main functions of the ECVRF.

The Key generation function

We create an ECVRF class and use the key generation function as the constructor of the class.

class ECVRF():

    def __init__(self,sk=None):
    if sk==None:
            self.sk = random.randint(0,order_minus_one)
            self.pk = G*self.sk
    else:
        self.sk = sk
        self.pk = G*self.sk

The Prove function

The prove function of the ECVRF. The function closely follow the steps in Section 5.1 of irtf-vrf15

def prove(self, x):
        # the evaluation function, based on the paper [PWHVNRG17]
        # step 1 compute h

        H = ECVRF_encode_to_curve_try_and_increment(self.pk,x,suite_string)

        #step 2 let gamma=h^self.sk

        gamma = H*self.sk

        #step 3 choose a random k

        k = random.randint(0,order_minus_one)

        #step 4 compute c=Hash_point(g,h,g^sk,h^sk,g^k,h^k)

        point_list=[H, self.pk, gamma, G*k, H*k]
        c = ECVRF_challenge_generation(point_list)

        #step 5 compute s=k-c*sk (mod order)
        s = (k - c*sk)% ORDER

        # the proof consists of gamma, c and s
        pi = {'gamma': gamma, 'c': c,  's': s}

        # the output is the keccak hash of gamma
        y=proof_to_hash(gamma)

        return {'output': y, 'proof': pi, 'public key': self.pk}

The ProofToHash function

The prove function of the ECVRF. The function closely follow the steps in Section 5.2 of irtf-vrf15

def proof_to_hash(gamma):

        # the output is the keccak hash of gamma
        hash = keccak.new(digest_bits=256)
        hash.update(b"\x01")
        hash.update(b"\x03")
        hash.update(str(gamma).encode())
        hash.update(b"\x00")
        y = int(hash.hexdigest(), 16)

The Verify function

The verify function of the ECVRF. The function closely follow the steps in Section 5.3 of irtf-vrf15

def verify(self, x, y, pi, pk):
        # this function, given an input x, a value y, a proof pi and 
        # the public key pk,
        # verify if the output y was calculated correctly from x

        gamma = pi['gamma']
        c = pi['c']
        s = pi['s']

        #step 1 compute U=c*pk+G*s

        U = c*pk + G*s

        #step 2 compute V=c*gamma+H*s

        H = ECVRF_encode_to_curve_try_and_increment(pk,x,suite_string)

        #step 3 compute V=c*gamma+h*s

        V = c*gamma + H*s

        #calculate the value Hash_point(G,H,pk,gamma,U,V)

        point_list=[H,pk,gamma,U,V]
        c2 = ECVRF_challenge_generation(point_list)

        #calculate the keccak hash of gamma

        hash = keccak.new(digest_bits=256)
        hash.update(str(gamma).encode())

        #step 4 check if c=Hash_point(g,h,pk,gamma,u,v) and y=keccak(gamma)

        return c == c2 and y == hash_to_proof(gamma)

ECVRF auxiliary functions

The auxiliary functions of the ECVRF.

The HashToCurve function

The HashToCurve of the converts a 256 bit integer into a point of the curve secp256k1. We ignore the cofactor check in irtf-vrf08, since the cofactor value is set to be 1.

def ECVRF_encode_to_curve_try_and_increment(pk, x, suite_string):
    #follow the ecvrf irtf draft

    ctr=0
    pk_string=str(pk).encode()
    one_string=int(0).to_bytes(1,'big')
    zero_string=int(1).to_bytes(1,'big')

    #because the == operation in the elliptic curve class only compare
    #two Points, we cannot use H=="INVALID" (can't compare a Point and a
    # string) but instead use H==INFINITY
    #because if H==INFINITY is also an invalid condition and it does not
    #change anything.

    H=INFINITY
    while  H==INFINITY:
        hash=keccak.new(digest_bits=256)
        ctr_string=str(ctr).encode()
        hash.update(suite_string)
        hash.update(one_string)
        hash.update(pk_string)
        hash.update(str(x).encode())
        hash.update(ctr_string)
        hash.update(zero_string)
        ctr+=1
        hash=hash.digest()
        H=string_to_curve(hash)
    return H

The HashPoint function

The HashPoint function converts a list of point into a 256 bit integer. The function closely follow the steps in Section 5.4.3 of irtf-vrf08

def ECVRF_challenge_generation(point_list):
        # based on the irtf internet draft
        #we use the keccak instead of sha256

        hash = keccak.new(digest_bits=256)
        hash.update(b"\x02")
        for i in point_list:
            hash.update(str(i).encode())
        hash.update(b"\x00")
        return int(hash.hexdigest(), 16) % ORDER

The StringToCurve function

The StringtoCurve converts a string into a point of secp256k1. We only need to implement Step 1, Step 2.2 and Step 2.4.1 in SECG1, since we use the curve secp256k1.

def string_to_curve(string):
    #specified in 2.3.4 of https://www.secg.org/sec1-v2.pdf
    #since the curve is secp256k1, then q=p is an odd prime
    #we want to implement for secp256k1 therefore we will just implement step 1, 
    # 2.2 and 2.4.1

    #Step 1

    if string==int(2).to_bytes(1,'big'):
        return INFINITY

    #Step 2.2

    x=string_to_field(string)
    if x=="INVALID":
        return INFINITY
    p=secp256k1._CurveFp__p

    #Step 2.4.1
    # let t=x^3+7 (mod p) 

    t=(pow(x,3,p)+secp256k1._CurveFp__a*x+secp256k1._CurveFp__b)%p
    QR=pow(t,(p-1)//2,p)
    if QR==(p-1):
        return INFINITY

    # because p=3 (mod 4), we see that y=t^((p+1)/4)

    beta=pow(t,(p+1)//4,p)
    if beta%2==0:
        return Point(secp256k1,x,beta)
    else:
        return Point(secp256k1,x,p-beta)

The StringToField function

The StringtoCurve converts a string into an element in $\mathcal{Z}_p$, where $p=2^{256}-2^{32}-977$. We only need to implement Step 1 and Step 2.3.6 in SECG1.

def string_to_field(string): 
    #specified in 2.3.6 of https://www.secg.org/sec1-v2.pdf
    #since i just want to implement for secp256k1, i will just implement step 1
    #in fact, step 1 is just the function string_to_integer in part 2.3.8 of the
    #same paper

    x=0
    for i in range (0,len(string)):
        x+=pow(256,len(string)-1-i)*int(hex(string[i]),16)
    if x<secp256k1._CurveFp__p:
        return x
    return "INVALID"