Revision #2 Authors: Oded Goldreich, Avi Wigderson

Accepted on: 11th December 1996 00:00

Downloads: 789

Keywords:

We present three explicit constructions of hash functions,

which exhibit a trade-off between the size of the family

(and hence the number of random bits needed to generate a member of the family),

and the quality (or error parameter) of the pseudo-random property it

achieves. Unlike previous constructions, most notably universal hashing,

the size of our families is essentially

independent of the size of the domain on which the functions operate.

The first construction is for the {\em mixing} property --

mapping a proportional part of any subset of the domain

to any other subset. The other

two are for the {\em extraction } property -- mapping any subset

of the domain almost uniformly into a range smaller than it. The second

and third constructions handle (respectively) the extreme situations when

the range is very large or very small.

We provide lower bounds showing our constructions are nearly optimal,

and mention some applications of the new constructions.}

Revision #1 Authors: Oded Goldreich, Avi Wigderson

Accepted on: 22nd January 1996 00:00

Downloads: 858

Keywords:

We present three explicit constructions of hash functions,

which exhibit a trade-off between the size of the family

(and hence the number of random bits needed to generate a member of the family),

and the quality (or error parameter) of the pseudo-random property it

achieves. Unlike previous constructions, most notably universal hashing,

the size of our families is essentially

independent of the size of the domain on which the functions operate.

The first construction is for the {\em mixing} property --

mapping a proportional part of any subset of the domain

to any other subset. The other

two are for the {\em extraction } property -- mapping any subset

of the domain almost uniformly into a range smaller than it. The second

and third constructions handle (respectively) the extreme situations when

the range is very large or very small.

We provide lower bounds showing our constructions are nearly optimal,

and mention some applications of the new constructions.}

TR94-002 Authors: Oded Goldreich, Avi Wigderson

Publication: 12th December 1994 00:00

Downloads: 1096

Keywords:

We present three explicit constructions of hash functions,

which exhibit a trade-off between the size of the family

(and hence the number of random bits needed to generate a member of the family),

and the quality (or error parameter) of the pseudo-random property it

achieves. Unlike previous constructions, most notably universal hashing,

the size of our families is essentially

independent of the size of the domain on which the functions operate.

The first construction is for the {\em mixing} property --

mapping a proportional part of any subset of the domain

to any other subset. The other

two are for the {\em extraction } property -- mapping any subset

of the domain almost uniformly into a range smaller than it. The second

and third constructions handle (respectively) the extreme situations when

the range is very large or very small.

We provide lower bounds showing our constructions are nearly optimal,

and mention some applications of the new constructions.