ECCC-Report TR94-002https://eccc.weizmann.ac.il/report/1994/002Comments and Revisions published for TR94-002en-usWed, 11 Dec 1996 00:00:00 +0200
Revision 2
| Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing |
Oded Goldreich,
Avi Wigderson
https://eccc.weizmann.ac.il/report/1994/002#revision2
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.}
Wed, 11 Dec 1996 00:00:00 +0200https://eccc.weizmann.ac.il/report/1994/002#revision2
Revision 1
| Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing |
Oded Goldreich,
Avi Wigderson
https://eccc.weizmann.ac.il/report/1994/002#revision1
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.}
Mon, 22 Jan 1996 00:00:00 +0200https://eccc.weizmann.ac.il/report/1994/002#revision1
Paper TR94-002
| Tiny Families of Functions with Random Properties: A Quality--Size Trade--off for Hashing |
Oded Goldreich,
Avi Wigderson
https://eccc.weizmann.ac.il/report/1994/002We 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.
Mon, 12 Dec 1994 00:00:00 +0200https://eccc.weizmann.ac.il/report/1994/002