## Abstract

Verifiable random functions (VRFs) are pseudorandom functions where the owner of the seed, in addition to computing the function’s value y at any point x, can also generate a non-interactive proof π that y is correct, without compromising pseudorandomness at other points. Being a natural primitive with a wide range of applications, considerable efforts have been directed towards the construction of such VRFs. While these efforts have resulted in a variety of algebraic constructions (from bilinear maps or the RSA problem), the relation between VRFs and other general primitives is still not well understood. We present new constructions of VRFs from general primitives, the main one being non-interactive witness-indistinguishable proofs (NIWIs). This includes: A selectively-secure VRF assuming NIWIs and non-interactive commitments. As usual, the VRF can be made adaptively-secure assuming subexponential hardness of the underlying primitives.An adaptively-secure VRF assuming (polynomially-hard) NIWIs, noninteractive commitments, and (single-key) constrained pseudorandom functions for a restricted class of constraints. The above primitives can be instantiated under various standard assumptions, which yields corresponding VRF instantiations, under different assumptions than were known so far. One notable example is a non-uniform construction of VRFs from subexponentially-hard trapdoor permutations, or more generally, from verifiable pseudorandom generators (the construction can be made uniform under a standard derandomization assumption). This partially answers an open question by Dwork and Naor (FOCS ’00). The construction and its analysis are quite simple. Both draw from ideas commonly used in the context of indistinguishability obfuscation.

Original language | English (US) |
---|---|

Title of host publication | Theory of Cryptography - 15th International Conference, TCC 2017, Proceedings |

Editors | Yael Kalai, Leonid Reyzin |

Publisher | Springer Verlag |

Pages | 567-594 |

Number of pages | 28 |

ISBN (Print) | 9783319705026 |

DOIs | |

State | Published - 2017 |

Event | 15th International Conference on Theory of Cryptography, TCC 2017 - Baltimore, United States Duration: Nov 12 2017 → Nov 15 2017 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10678 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 15th International Conference on Theory of Cryptography, TCC 2017 |
---|---|

Country/Territory | United States |

City | Baltimore |

Period | 11/12/17 → 11/15/17 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science