Verifiable Random Functions

From CryptoWiki
Jump to: navigation, search



Modern information systems solve different and important tasks: automated process control and industrial enterprises, automation of banks, financial exchanges, insurance companies, trading companies, etc. The problem of information security for any system that works with the flow of information is one of the most important. The requirements of information security should be designed to ensure optimal functioning of the information system in common. Information of organization, equipment used in the handling of information flows are treated as assets of the organization. They all may be suffered from information security threats, which can lead to breach of the functioning of the whole system, disabling strategically important parts of the system, and great financial loss. In this case, the system faces a crisis or even a crash. In order to avoid this outcome, the first thing you need to consider the information security of the automated system. In order to make the necessary list of cryptographic techniques for information security in the automated system, consider the threats of information security. According to the classical approach to information in general stand out various information security threats connected with its main properties - the confidentiality, integrity and availability. In addition, information security threats are accidental and intentional, external and internal, causing unauthorized actions, physical damage or equipment failure. They can cause damage to the information, processes, systems and organization. Some of the threats to information security can relate to multiple assets, and for one asset may be several different classes of threats.

Back to table of contents

General concept

Verifiable random functions (VRF) were developed by Silvio Micali, Michael Rabin and Salil Vadhan. Then work on the functions continues Alexander Yampolskiy and Evgeniy Dodis [2]. VRF behave like pseudo-random functions - the attacker is not able to distinguish between the value of the pseudo-random number function, even under the condition that he knows it's value elsewhere. However, the VRF have the additional property: the input data can not be calculated only by the owner of the entropy pool. Also, it is guaranteed that the input value of the function is unique and correctly. The proof can be verified by anyone who knows the public key corresponding to the entropy pool. Any verifiable random function is four functions.


● Function VRFGEN generates pair of keys (VRFSK, VRFPK).

● Function VRFVAL (VRFSK, x) generates pseudorandom value val.

● Function VRFPROVE (VRFSK, x) calculates pr(x), confirming that val is correct.

● Function VRFVER(VRFPK, x, val, pr(x)) is for anyone who has VRFPK could verify the proof pr(x).

Properties of verifiable random functions:

● Correctness — if VRFPROVE (VRFSK, x) = (val, pr(x)) then VRFVER(VRFPK, x, val, pr(x)) = 1.

● Justification — no one value (VRFPK, x, val1, pr1(x), val2, pr2(x)) with different val1 and val2, pr1(x) and pr2(x) could not satisfy the equality VRFVER(VRFPK, x, val1, pr1(x)) = VRFVER(VRFPK, x, val2, pr2(x)) = 1.

● Pseudorandomness - using previous values of val you can't predict next values.

Example: Suppose we have the input value x. Knowledge of the secret key S allows you to calculate proof. Proof allows each reviewer who has public key P to ensure that value was calculated correctly.

Example of constructing of the VRF

Consider the example of the construction of the verifiable random function [3]. 1) Key generation. The first step is key generation algorithm selects a group G and order p. Then we set a pseudorandom number generators Generators.png. With them we generate random variables Sluchvel.png and calculate Vi4isl.png The keys have the following values:Sledzna4.png

2) Generation of pseudorandom values. For Xprin.png function FSK.png calculates value Xravn.png as FSKravn.png

3) Proof calculation. This algorithm outputs the proof Pi.png. To calculate it we have to precalculate values Iravn.png The resulting value is calculated as Pipo.png

4) Calculating the verifying function.

Pr1.png if Pr2.png

else Pr3.png.

For Pr4.png Pr5.png

if Pr6.png

Pr7.png else.

Then verify that Pr8.png and Pr9.png

Verifiable random functions cryptostrength

Verifiable random functions cryptostrength [4] is based on Bilinear Desicional Diffie Hellman Inversion (BDDHI). Strength of all schemes based on verifiable random functions is based on this issue. Often with Verifiable Random Functions notice Verifiable Unpredictable Functions, abbreviated VUF. They can be seen as a signature scheme, which is a unique (not more than one value) is accompanied by the signature verification algorithm for each message and the public key. Any verifiable random function is four functions.

● Function VRFGEN generates key pair (VRFSK, VRFPK).

● Function VRFVAL (VRFSK, x) generates pseudorandom value val.

● Function VRFPROVE (VRFSK, x) calculates pr(x) confirming that val is correct.

● Function VRFVER(VRFPK, x, val, pr(x)) is made to verify pr(x) for everyone who has VRFPK.

These functions are also proofable, but their pseudorandomness replaced by unpredictability. Unpredictable value can be calculated using an algorithm in contradistinction to verifiable random functions.

Verifiable Random Functions application

Today VRF can be used in different areas of cryptography:

- In the mechanisms of digital signatures;

- For generating keys from a secret value (e.g., master key);

- In the mechanisms of micropayments.

VRF can solve the following problems of information security:

- integrity;

- authenticity;

- Non-repudiation of authorship;

- Authentication.

One of the purposes of the VRF is its application to implement protocols with zero knowledge. The core of this protocol is that it allows one part (the examiner) to check the accuracy of any statements (usually mathematical), while not having received any other information from the second side (to prove). Thus, when the opportunity to prove the assertion requires some secret information by proving, it is understood that the inspection would not be able to prove the statement to someone else.

VRF can be considered as a condition specifying the exponential number of seemingly random bits, which can occur in the protocol. For example, using the VRF can reduce the number of rounds for relieving zero knowledge protocol to 3 in the original model. Verifiable random functions in their operations may be compared with digital signatures. Consider the comparison of verifiable random functions with the basic approaches to the construction of digital signatures.


Basic cryptographic primitives based on Verifiable Random Functions

One-Time Sound Resettable Zero Knowledge Protocol in Three Rounds

One-Time Sound Resettable Zero Knowledge (RZK) Protocol in Three Rounds is based on Verifiable Random Functions was developed by Evgeniy Dodis. This protocol provides data transfer [1, 5]. This protocol is based on 3 components:

1. Pseudorandom functions a.k.a. PRF

2. Verifiable random functions a.k.a. VRF

3. Non-interactive zero knowledge a.k.a. NIZK

Protocol works for any language L(∈ NP), for which there is a non-interactive proof system. Demonstration of the protocol for A, B.

Protocol: for n B generates keypair of length n and parameter Kne.png Then VRFSK is a secret key of B, VRFPK — public key of B.

Opened file: A set of records F, (ID, VRFPKID), where VRFPKID is output of VRFGEN (generates VRFPK and VRFSK).

Input data: element x∈L.

A input data: y(∈ NP) for x; id and F for B; random string rstr.

B input data: secret key SK.

Step 1(A):

1. Using string rstr as entropy pool(seed) for PRF generate string Na of length l(n) with input x, y, id.

2. Na → B.

Step 1(B):

1. Calculates string Nb=VRFVAL(VRFSK, x) and proof pr=VRFPROVE(VRFSK,x).

2. Nb, pr → A.

Step 2(A):

1. Check that Nb is correct using VRFVER(VRFPK, x, t, pr). If not, receiving data interrupts.

2. Let N = Na ⊕ Nb. Using NIP(N, x, y) calculate and send A proof that x ∈ L.

Step 2(B):

1. Let N = Na ⊕ Nb. Using NIV(N, x, П) check correctness of П. If everything is correct, continue receiving data, else, end the connection.

Non-interactive lottery

Another application of VRF developed by Micali and Rivest [3] is non-interactive lottery system. The organizer of the lottery haspublic key PK and secret key SK generated by VRFGEN. Member creates his own lottery ticket t for and sends it to the organizer. Organizer calculates the value of y = VRFVALSK (t) on the lottery ticket and the corresponding proof M = VRFPROVESK (t). Winning value y is determined by random selection. The value y determines whether the user wins, and the proof M ensures that the organizer can not deceive. It is difficult for user to determine how close he is to win. And the organizer selects the winning ticket among the random numbers. It is difficult to forge the results. This development is also used for micropayments.

Unique signatures

On the basis of the verifiable unpredictable functions Goldwasser and Ostrovsky developed a unique digital signature. [6] The essence of this scheme is that we apply VUF as an digital signature.

Signature algorithm

1. Keypair generation

● Function VUFGEN generates keypair (VUFPK, VUFSK).

2. Signature and proof generation

● Function VUFVAL(VUFSK, m) generates pseudorandom value val.

● Function VUFPROVE(VUFSK, m) calculates pr(m) confirming that val is correct.

3. Signature verification

● Function VUFVER(VUFPK, m, val, pr(m)) is made to verify pr(m) for everyone who has VUFPK.


VRF Authentication algorithm

This protocol [7] contain four functions. Every function is part of pseudorandom verifiable function.

Step 1. When a user with the ID wishes to become part of the system, the distributor (trustee) sends him some value m length of 256 bits.

Шаг 2. User calculates the value using his secret key VRFVAL (SK, m) and VRFPROVE (SK, m).

Шаг 3. User sends calculated value to the server. Then server verifies values using the public key VRFVER (VRFPK, m, val, pr (m)). If the evidence shows that the calculated value is true. It means that user is already registered and has an ID.

Selectively Convertible Undeniable Signatures

Selectively convertible undeniable signature (SCUS) was introduced by Boyar, Pedersen and Schaum. In 1990, the concept of undeniable signature was expanded by Schaum and Antwerp [6]. A selectively convertible US scheme allows the signer to convert an undeniable signature τ into a regular signature by releasing a piece of information α at a later time. All conversion means that the signer can convert all undeniable signatures into regular ones. They showed that if there exists a digital signature (DS) scheme, then there exists a convertible US scheme. However, this construction is not practical. Damgard and Pedersen showed two selectively convertible US scheme schemes based on ElGamal signature scheme. In their schemes, a part of the ElGamal signature is encrypted by Rabin encryption scheme or by ElGamal encryption scheme. However, invisibility is not proved in these schemes, where the invisibility means that we cannot decide if (m,τ) is a valid (message, undeniable signature) pair. Note that the invisibility is an essential property required for US schemes from the definition. Gennaro-Krawczyk-Rabin proposed an RSA-based US scheme which allows all conversion efficiently. They also showed a method of selective conversion such that the signer releases a non-interactive proof which shows that (m,τ) is a valid (message, undeniable signature) pair. The verification of signatures is controlled by the signatory. Any verificating is required to run an interactive protocol from the signer to verify that the signature is valid. However SCUS checking signatures can optionally be carried out non-interactively: the signer can release information called a converter to open a process of signature verifying. The feature is that verify the signature can only one person.

The main concept:

1. A sends B digital signature.

2. B generates random value and sends it to A.

3. On the basis of received from B of a random number and a private function A generates the result of some calculations and sends B. A confirms his signature with the values of a signature belongs to him, and, on the other hand, denies his authorship.

SCUS shcheme contains:

-KGen: Generates PK and SK.

-USignSK(m): Outputs signature σ with input m.

–ConvertSK(m, σ): outputs cvt if (m, σ) is correct.

–VerifyPK(m, σ, cvt): if (m, σ) calculated correct outputs 1, else - 0.

– Confirm: protocol between signer and verifier, inputs (pk, m, σ), signer with SK proves that (m, σ) is correct pair. Message is a zero-condition signature.

– Disavowal: protocol between signer and verifier, inputs (pk, m, σ), signer with SK proves that (m, σ) is incorrect pair. Message is a zero-condition signature.

The signature based on verifiable random functions has the following components:

– KGen: returns (pk, sk) ← Gen.

– USignSK(m): returns σ = VRFVAL(VRFSK, m) as undeniable signature.

– ConvertSK(m, σ): Calculates VRFPROVE(VRFSK, m) = pr(m). With correct proof outputs 1, else - 0.

–VerifyPK(m, σ, pr(m)): Outputs value VRFVER(VRFPK, m, σ, pr(m)), allows any user with PK verify correctness of pr(m).

– Confirm: protocol with input (pk, m, σ). Signer with SK proves with zero-condition that σ = VRFVAL(VRFSK, m).

– Disavowal: protocol between signer and verifier, inputs (pk, m, σ). Signer with SK proves with zero-condition that σ и VRFVAL(VRFSK, m) aren't equal.

One of the main criteria of safety for the signature scheme is indisputabless and uniqueness. The concept of uniqueness ensures that if one signer starts converting the signature, then no one can convert this signature. The reciever of the message can verify whether it was changed during delivery, an attacker can not substitute the right message. Non-repudiation of authorship. The sender will not be able to falsely deny sending the message.

Digital Voting scheme

These schemes are designed to ensure that every voter could openly see that his voice is counted accurately (often referred to as the individual verifiability) and that all the recorded votes were correctly counted. In anonymous voting schemes pseudorandomness obtained values ​​is very important. The two main ways to obtain unbiased results - to ensure a randomness through a voting machine or the voter. However, it is problematic to trust the voting the machine for several reasons. We can not guarantee that random values ​​are unpredictable, and even if they could, non-determinism of output creates potential covert channels. On the other hand, the randomness may be derived from voters who can enter the random number in the voting process. This method is also undesirable because it puts an unnecessary burden on the voter and can cause confusion. People are also not known to be original in selection of random numbers. Therefore in anonymous voting the role of generators of random numbers assigned to pseudorandom functions.

Internet voting must satisfy the following requirements::

● Only those who has rights to vote may vote.

● No one can know about another participant's vote.

● No one can vote instead of another.

● No one can secretly change a voice.

● Each voter can verify that his voice is counted.

In addition, some voting schemes may need the following requirement:

● Everyone can not vote more than once.

We can definitely conclude that a vote is required to satisfy the main properties such as:

● Registration

● Secrecy

● Anonymity

● Full control of your voice

● Full trust

Consider the scheme of digital voting based on verifiable random functions [8].


Before the start of voting registration server sends via covert channels for each user private key UserVoteKey (UVK), which is known only to the server and user. After that all the keys on the server registration are destroyed. There is also a verification public key VRFPK generated and stored on the server.


The server generates the voting options Xi. To begin voting server sends the user-generated voting options as Golosa.png. The user makes the choice Xc, then sends values (Xc, VRFVAL (UVK, Xc), VRFPROVE (UVK, Xc)) to the server anonymously. Server calculates proof VRFVER (VRFPK, Xc, val, pr (Xc)) defining correctness of the values. If everything is correct the user is already registered and got the secret key.

Votes counting

The vote results have to be published in the form of a pair of VRFVAL (UVK, XC), VEPROVE (UVK, Xc), so each user can make sure that his vote was counted and can not give up his voice, as in this case, the server publishes the calculated proof VRFVER (VRFPK , Xc, val, pr (Xc)).

Analysis of the possibility of using cryptographic schemes based on verifiable random functions

So we covered the basic cryptographic primitives using verifiable random functions. With their help, we can ensure the authenticity, integrity and confidentiality of information transmitted in the automated system. This is done as follows.




Go to bibliography

Бурмистров Роман Валерьевич, 2015