## Abstract

We show that a randomly chosen linear map over a finite field gives a good hash function in the l8 sense. More concretely, consider a set S ? Fqn and a randomly chosen linear L: Fqn Fqt with qt taken to be sufficiently smaller than |S|. Let US denote a random variable distributed uniformly on S. Our main theorem shows that, with high probability over the choice of L, the random variable L(US) is close to uniform in the l8 norm. In other words, every element in the range Fqt has about the same number of elements in S mapped to it. This complements the widely-used Leftover Hash Lemma (LHL) which proves the analog statement under the statistical, or l1, distance (for a richer class of functions) as well as prior work on the expected largest 'bucket size' in linear hash functions [1]. By known bounds from the load balancing literature [2], our results are tight and show that linear functions hash as well as truly random function up to a constant factor in the entropy loss. Our proof leverages a connection between linear hashing and the finite field Kakeya problem and extends some of the tools developed in this area, in particular the polynomial method.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022 |

Publisher | IEEE Computer Society |

Pages | 419-428 |

Number of pages | 10 |

ISBN (Electronic) | 9781665455190 |

DOIs | |

State | Published - 2022 |

Externally published | Yes |

Event | 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 - Denver, United States Duration: Oct 31 2022 → Nov 3 2022 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2022-October |

ISSN (Print) | 0272-5428 |

### Conference

Conference | 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 |
---|---|

Country/Territory | United States |

City | Denver |

Period | 10/31/22 → 11/3/22 |

## All Science Journal Classification (ASJC) codes

- General Computer Science

## Keywords

- Hashing
- Kakeya
- Leftover Hash Lemma
- Polynomial Method

## Fingerprint

Dive into the research topics of 'Linear Hashing with l_{8}guarantees and two-sided Kakeya bounds'. Together they form a unique fingerprint.