Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR17-005 | 26th January 2017 23:25

Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs

RSS-Feed




Revision #3
Authors: Nir Bitansky
Accepted on: 26th January 2017 23:25
Downloads: 502
Keywords: 


Abstract:


{\em 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 $\pi$ 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 {\em non-interactive witness-indistinguishable proofs} (NIWIs).
This includes:
\begin{itemize}
\item
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.
\item
An adaptively-secure VRF assuming (polynomially-hard) NIWIs, non-interactive commitments, and {\em (single-key) constrained pseudorandom functions} for a restricted class of constraints.

\end{itemize}

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 {\em 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 {\em indistinguishability obfuscation}.


Revision #2 to TR17-005 | 26th January 2017 22:19

Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs





Revision #2
Authors: Nir Bitansky
Accepted on: 26th January 2017 22:19
Downloads: 166
Keywords: 


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 $\pi$ that $y$ is correct (relative to so), 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 cryptographic 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:
\begin{itemize}
\item
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.
\item
An adaptively-secure VRF assuming (polynomially-hard) NIWIs, non-interactive commitments, and (single-key) constrained pseudorandom functions for a restricted class of constraints.
\end{itemize}

The above primitives have known instantiations under various standard assumptions, which yields corresponding VRF instantiations, under different assumptions than were known. One notable example is a non-uniform construction of VRFs from subexponentially-hard trapdoor permutations, or more generally, 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.


Revision #1 to TR17-005 | 18th January 2017 07:58

Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs





Revision #1
Authors: Nir Bitansky
Accepted on: 18th January 2017 07:59
Downloads: 201
Keywords: 


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 $\pi$ that $y$ is correct (relative to so), 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 cryptographic 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:
\begin{itemize}
\item
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.
\item
An adaptively-secure VRF assuming (polynomially-hard) NIWIs, non-interactive commitments, and (single-key) constrained pseudorandom functions for a restricted class of constraints.
\end{itemize}

The above primitives have known instantiations under various standard assumptions, which yields corresponding VRF instantiations, under different assumptions than were known. One notable example is a non-uniform construction of VRFs from subexponentially-hard trapdoor permutations, or more generally, 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.


Paper:

TR17-005 | 10th January 2017 05:07

Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs


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 $\pi$ that $y$ is correct (relative to so), 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 cryptographic 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:
\begin{itemize}
\item
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.
\item
An adaptively-secure VRF assuming (polynomially-hard) NIWIs, non-interactive commitments, and (single-key) constrained pseudorandom functions for a restricted class of constraints.
\end{itemize}

The above primitives have known instantiations under various standard assumptions, which yields corresponding VRF instantiations, under different assumptions than were known. One notable example is a non-uniform construction of VRFs from subexponentially-hard trapdoor permutations, or more generally, 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.



ISSN 1433-8092 | Imprint