Verifiable Random Functions from Standard Assumptions

Dennis Hofheinz; Tibor Jager

Paper 2015/1048

Verifiable Random Functions from Standard Assumptions

Dennis Hofheinz and 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.

Metadata

Available format(s): PDF
Publication info: Published by the IACR in TCC 2016
Keywords: Verifiable random functions standard assumptions decision-linear assumption Q-type assumptions.
Contact author(s): dennis hofheinz @ kit edu
tibor jager @ rub de
History: 2015-10-30: revised; 2015-10-29: received; See all versions
Short URL: https://ia.cr/2015/1048
License: CC BY

BibTeX

@misc{cryptoeprint:2015/1048,
      author = {Dennis Hofheinz and Tibor Jager},
      title = {Verifiable Random Functions from Standard Assumptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/1048},
      year = {2015},
      url = {https://eprint.iacr.org/2015/1048}
}