Complexity theory is built fundamentally on the notion of efficient
reduction among computational problems. Classical
reductions involve gadgets that map solution fragments of one problem to
solution fragments of another in one-to-one, or
possibly one-to-many, fashion. In this paper we propose a new kind of
reduction that allows for gadgets ...
more >>>
We highlight a common theme in four relatively recent works
that establish remarkable results by an iterative approach.
Starting from a trivial construct,
each of these works applies an ingeniously designed
sequence of iterations that yields the desired result,
which is highly non-trivial. Furthermore, in each iteration,
more >>>
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 >>>