Hash function constructions from expander graphs

• US 7,382,876 B2
• Filed: 11/01/2005
• Issued: 06/03/2008
• Est. Priority Date: 11/01/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Goren, Eyal Zvi, Lauter, Kristin E., Charles, Denis X
• Primary Examiner(s): Moazzami; Nasser
• Assistant Examiner(s): Traore; Fatoumata
• Application Number:
  US11/263,701
• Publication Number:
  US 20070098150A1
• Time in Patent Office: 945 Days
• Field of Search: 380/28, 380/37, 380/42, 713/179, 713/181
• US Class Current: 380/28
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC

Abstract

Hash function constructions from expander graphs are described. In one aspect, an expander graph is walked to compute a hash function. The expander graph is walked using respective subsets of an input message. A label of a last vertex walked is an output of the hash function.

Claims

1. A computer-implemented method comprising:

walking an expander graph according to input to a hash function, the expander graph being walked using respective subsets of an input message, wherein the input message is divided into segments, wherein for at least a subset of these segments, a path to a next respective vertex in the expander graph is determined based on aspects of a particular segment of a subset, wherein the expander graph comprises a graph of supersingular elliptic curves over a finite field of characteristic p;

determining a label of a last vertex walked; and

outputting the label as a result of the hash function, wherein the hash function is collision resistant.

2. The method of claim 1, wherein the expander graph further comprises a Ramanujan graph.

3. The method of claim 1, wherein the expander graph further comprises a Lubotzky-Phillips-Sarnak expander graph.

4. The method of claim 1, wherein the result is a cryptographic hash.

5. The method of claim 1, wherein finding collisions for the hash function is computationally hard.

6. The method of claim 1, wherein the input message has a certain degree of entropy.

7. The method of claim 1, wherein the expander graph comprises n vertices, wherein the input message has a degree of entropy, and wherein the method further comprises:

assigning a respective label to vertices of the graph;

determining the degree of entropy;

wherein walking further comprises walking the n vertices using the degree of entropy to identify completely random vertex output; and

wherein the output is a respective assigned label of a last vertex of the n vertices walked, whereby the label of the last vertex is a result of a hash function.

8. The method of claim 7, wherein determining the degree of entropy further comprises using an extractor function to determine a degree of randomness associated with the input message.

9. A computer storage media comprising computer-programmed instructions executable by a processor for:

dividing a message into segments;

walking an expander graph according to input to a hash function, the expander graph being walked using respective ones of the segments to determine a path to a next vertex of n vertices in the expander graph, wherein the expander graph is a Lubotzky-Phillips-Sarnak expander graph;

determining a label of a last vertex walked; and

outputting the label as a result of the hash function.

10. The computer storage media of claim 9, wherein the expander graph is a Ramanujan graph.

11. The computer storage media of claim 9, wherein the result is a cryptographic hash.

12. The computer storage media of claim 9, wherein finding collisions for the hash function is computationally hard.

13. The computer storage media of claim 9, wherein the message is divided into the segments based on a degree of entropy extracted from the message.

14. The computer-storage media of claim 9, wherein the expander graph comprises n vertices, wherein the message has a degree of entropy, and wherein the computer-program instructions further comprising structures for:

assigning a respective label to vertices of the graph;

determining the degree of entropy;

wherein walking further comprises walking the n vertices using the degree of entropy to identify completely random vertex output; and

wherein the output is a respective assigned label of a last vertex of the n vertices walked, whereby the label of the last vertex is a result of a hash function.

15. The computer storage media of claim 9, wherein the computer-programmed instructions for determining the degree of entropy further comprises instructions for using an extractor function to determine a degree of randomness associated with the message.

16. A computing device comprising:

a memory coupled to the processor, the memory comprising computer-program instructions executable by the processor for;

assigning a respective label to respective ones of n vertices in an expander graph;

dividing an input message into segments;

walking the expander graph as input to a hash function, the expander graph being walked using respective ones of the segments to determine a path to a next vertex of the n vertices in the expander graph, wherein determining the path to the next vertex in the walk is performed by reading bits from a next segment to determine which edge traversed from the current vertex, wherein the expander graph is selected from a group consisting of a graph of supersingular elliptic curves over a finite field of characteristic p, a Ramanujan graph and a Lubotzky-Phillips-Sarnak expander graph;

determining a label of a last vertex of the vertices walked; and

outputting the label as a result of the hash function.

17. The computing device of claim 16, wherein the result is a cryptographic hash.