Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR05-097 | 31st August 2005
Jens Groth, Rafail Ostrovsky, Amit Sahai

Perfect Non-Interactive Zero Knowledge for NP

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


TR05-096 | 26th August 2005
Boaz Barak, Amit Sahai

How To Play Almost Any Mental Game Over The Net --- Concurrent Composition via Super-Polynomial Simulation

We construct a secure protocol for any multi-party functionality
that remains secure (under a relaxed definition of security) when
executed concurrently with multiple copies of itself and other
protocols. We stress that we do *not* use any assumptions on
existence of trusted parties, common reference string, honest
majority or synchronicity ... more >>>


TR05-095 | 26th August 2005
Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolay Vereshchagin

Partitioning multi-dimensional sets in a small number of ``uniform'' parts

Our main result implies the following easily formulated statement. The set of edges E of every finite bipartite graph can be split into poly(log |E|) subsets so the all the resulting bipartite graphcs are almost regular. The latter means that the ratio between the maximal and minimal non-zero degree of ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint