Browse Prior Art Database

Method of Extending Hash Functions for Long Keys

IP.com Disclosure Number: IPCOM000088344D
Original Publication Date: 1977-May-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Carter, JL: AUTHOR [+2]

Abstract

Some hash functions only work easily on inputs up to a certain length (e. g., one computer word). A method is disclosed herein for extending such functions to longer inputs which preserves an important property of the original functions.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 98% of the total text.

Page 1 of 1

Method of Extending Hash Functions for Long Keys

Some hash functions only work easily on inputs up to a certain length (e. g., one computer word). A method is disclosed herein for extending such functions to longer inputs which preserves an important property of the original functions.

Let A(F) = {0,1,...,a(F) - 1}, A(G) = {0,1,...,a(G) - 1}, and B = {0,1,...,b-1}, where b is a power of two. Given two collections F,G of hash functions from A(F) to B and A(G) to B, we will define a collection of hash functions from A(F) x A(G) to B.

(Image Omitted)

If classes F and G are strongly pairwise random, then class H, formed as above, is also. Strongly pairwise random implies pairwise random. The two classes of hash functions discussed in the preceding two articles are strongly pairwise random. Thus, if this technique is used for extending them, all the advantages claimed for them are preserved.

The extension is particularly useful in the multiplication technique. Suppose an input space is too large for its indices to be multiplied in a single word operation. Its indices can be split into twc or more sections. The sections are individually hashed and then the results combined by exclusive ORs.

While the exclusive OR operation is commonly used in hashing long keys as a means to shorten them before hashing, the present method first hashes the sections and then exclusive OR's the results. This new technique is necessary to preserve the strongly pairwise random property of cl...