On Universal Classes of Extremely Random Constant Time Hash Functions and their Time-Space Tradeoff

Abstract

A family of functions F that map [0,n] longmaps to [0,n], is said to be h-wise independent if any h points in [0,n] have an image, for randomly selected f epsilon F, that in uniformly distributed. This paper gives both probabilistic and explicit randomized constructions of n epsilon-wise independent functions, epsilon less than or equal to 1, that can be evaluated in constant time for the standard random access model of computation.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1995
Accession Number
AD1020220

Entities

People

  • Alan Siegel

Organizations

  • Courant Institute of Mathematical Sciences, NYU

Tags

DTIC Thesaurus Topics

  • Computations
  • Construction
  • Standards

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Statistical inference.

Technology Areas

  • Space