Joe Kilian, Erez Petrank

We consider noninteractive zero-knowledge proofs in the shared random

string model proposed by Blum, Feldman and Micali \cite{bfm}. Until

recently there was a sizable polynomial gap between the most

efficient noninteractive proofs for {\sf NP} based on general

complexity assumptions \cite{fls} versus those based on specific

algebraic assumptions \cite{Da}. ...
more >>>

Jens Groth, Rafail Ostrovsky, Amit Sahai

Non-interactive zero-knowledge (NIZK) systems are

fundamental cryptographic primitives used in many constructions,

including CCA2-secure cryptosystems, digital signatures, and various

cryptographic protocols. What makes them especially attractive, is

that they work equally well in a concurrent setting, which is

notoriously hard for interactive zero-knowledge protocols. However,

while for interactive zero-knowledge we ...
more >>>

Jens Groth, Amit Sahai

Non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that non-interactive zero-knowledge proofs have been constructed for general NP-complete languages such as ... more >>>

Nir Bitansky

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 ... more >>>