Nir Bitansky: Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs

Speaker: Nir Bitansky, MIT

Date: Friday, April 14, 2017

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: Hewlett, G882

Event Type:

Room Description:

Host: Vinod Vaikuntanathan

Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu

Reminder Subject: TALK: Nir Bitansky: Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs

Abstract: Verifiable random functions (VRFs), introduced by Micali, Rabin, and Vadhan (FOCS 99), are pseudorandom functions where the owner of the seed, in addition to computing the function's value at any point, can also generate a non-interactive proof that the value 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 the RSA problem or bilinear maps), 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 {\em (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. 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.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Seminar (CIS) 2017.

Created by Deborah Goodwin at Monday, April 10, 2017 at 6:51 AM.