A new bound for t−wise almost universal hash functions
Using the pigeon-hole principle, we derive a new bound for the key length in a t-wise almost universal hash function where the multicollision or t-collision probability is bounded above by epsilon in the range [0,1]. The important features of this bound are (1) it decreases very slowly as t increase...
| Main Authors: | , |
|---|---|
| Format: | Report |
| Published: |
OUCL
2010
|
| _version_ | 1797069226640408576 |
|---|---|
| author | Nguyen, L Roscoe, A |
| author_facet | Nguyen, L Roscoe, A |
| author_sort | Nguyen, L |
| collection | OXFORD |
| description | Using the pigeon-hole principle, we derive a new bound for the key length in a t-wise almost universal hash function where the multicollision or t-collision probability is bounded above by epsilon in the range [0,1]. The important features of this bound are (1) it decreases very slowly as t increases, and (2) the key length grows at least linearly with the logarithm of the message length. To our knowledge, this is the first almost universal hash bound for any integer t > 1. This work arises from the use of t-wise almost universal hash functions in manual authentication protocols. |
| first_indexed | 2024-03-06T22:21:20Z |
| format | Report |
| id | oxford-uuid:5528100b-95d9-47d3-bc7c-85067d885562 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T22:21:20Z |
| publishDate | 2010 |
| publisher | OUCL |
| record_format | dspace |
| spelling | oxford-uuid:5528100b-95d9-47d3-bc7c-85067d8855622022-03-26T16:42:16ZA new bound for t−wise almost universal hash functionsReporthttp://purl.org/coar/resource_type/c_93fcuuid:5528100b-95d9-47d3-bc7c-85067d885562Department of Computer ScienceOUCL2010Nguyen, LRoscoe, AUsing the pigeon-hole principle, we derive a new bound for the key length in a t-wise almost universal hash function where the multicollision or t-collision probability is bounded above by epsilon in the range [0,1]. The important features of this bound are (1) it decreases very slowly as t increases, and (2) the key length grows at least linearly with the logarithm of the message length. To our knowledge, this is the first almost universal hash bound for any integer t > 1. This work arises from the use of t-wise almost universal hash functions in manual authentication protocols. |
| spellingShingle | Nguyen, L Roscoe, A A new bound for t−wise almost universal hash functions |
| title | A new bound for t−wise almost universal hash functions |
| title_full | A new bound for t−wise almost universal hash functions |
| title_fullStr | A new bound for t−wise almost universal hash functions |
| title_full_unstemmed | A new bound for t−wise almost universal hash functions |
| title_short | A new bound for t−wise almost universal hash functions |
| title_sort | new bound for t wise almost universal hash functions |
| work_keys_str_mv | AT nguyenl anewboundfortwisealmostuniversalhashfunctions AT roscoea anewboundfortwisealmostuniversalhashfunctions AT nguyenl newboundfortwisealmostuniversalhashfunctions AT roscoea newboundfortwisealmostuniversalhashfunctions |