Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with statistical zero-knowldge:
TR10-160 | 28th October 2010
Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

On Approximating the Entropy of Polynomial Mappings

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA):
Given a low-degree polynomial mapping
$p : F^n\rightarrow F^m$, where $F$ is a finite field, approximate the output entropy
$H(p(U_n))$, where $U_n$ is the uniform distribution on $F^n$ and $H$ may be any of several entropy measures.

... more >>>

TR17-097 | 31st May 2017
Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan

Multi Collision Resistant Hash Functions and their Applications

Revisions: 1

Collision resistant hash functions are functions that shrink their input, but for which it is computationally infeasible to find a collision, namely two strings that hash to the same value (although collisions are abundant).

In this work we study multi-collision resistant hash functions (MCRH) a natural relaxation of collision resistant ... more >>>

ISSN 1433-8092 | Imprint