Cryptology ePrint Archive: Report 2015/1048

Verifiable Random Functions from Standard Assumptions

Dennis Hofheinz; Tibor Jager

Abstract: The question whether there exist verifiable random functions with exponential-sized input space and full adaptive security based on a non-interactive, constant-size assumption is a long-standing open problem. We construct the first verifiable random functions which simultaneously achieve all these properties.

Our construction can securely be instantiated in symmetric bilinear groups, based on any member of the (n-1)-linear assumption family with n >= 3. This includes, for example, the 2-linear assumption, which is also known as the decision linear (DLIN) assumption.

Category / Keywords: Verifiable random functions, standard assumptions, decision-linear assumption, Q-type assumptions.

Original Publication (in the same form): IACR-TCC-2016

Date: received 28 Oct 2015, last revised 30 Oct 2015

Contact author: dennis hofheinz at kit edu, tibor jager@rub de

Available format(s): PDF | BibTeX Citation

Version: 20151030:131403 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]