Method for the construction of hash functions based on sylvester matrices, balanced incomplete block designs and error-correcting codes

• US 20030053622A1
• Filed: 09/18/2002
• Published: 03/20/2003
• Est. Priority Date: 09/20/2001
• Status: Abandoned Application

• Current Assignee: Non-Elephant Encryption Systems, Inc.
• Original Assignee: Non-Elephant Encryption Systems, Inc.
• Inventors: Forcinito, Mario, Wehlau, David, Bruen, Aiden
• Application Number:
  US10/245,510
• Publication Number:
  US 20030053622A1
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/304 based on error correction codes, e.g. McEliece
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

An apparatus and method for constructing a hash function are provided such that an input string is mapped to an output string, the hash function being based on one of Sylvester matrices, balanced incomplete block designs, and error-correcting codes. The constructed hash function can be used by an apparatus for, among other uses, encrypting messages, determining if strings s and s′ are equal, and for respectively storing and retrieving data into and from a memory.

Claims

1. A method of constructing a hash function H(x), for mapping an input string x=(x₁, x₂, . . . , x_n) of length n>

0 to an output string of length n−

t, 1<

t<

n, of the set of strings H(x)={(h₁(x), h₂(x), . . . , h<sub>n−

t</sub>(x))}, said input and output string being defined over a given finite field F and H(x) being defined as a concatenation of said functions h_i(x), said method comprising the steps of;

a) providing a binary incidence matrix A having n columns and n rows, for a balanced incomplete block design on n points;

b) selecting a set of n-t rows, R₁, R₂, . . . , R<sub>n−

t</sub>, of the rows of A such that said selected n−

t rows are linearly independent over F, wherein no F-linear independent combination of said selected set of n−

t rows is a zero row save for an all-zero linear combination of said selected set of rows;

c) for each said row R_i, obtaining a subset F_i, of a n-set Ω

={1, 2, . . . n}, said subset being positions in which the row R_i has a 1, wherein 1≦

i≦

n−

t.

d) for said input string, setting_h_i(x)=(Σ

_{w in Fi xw}), wherein 1≦

i≦

n−

t; and

e) defining said hash function as an output string created by the concatenation of h_i(x) for 1≦

i≦

n−

t, H(x)=(h₁(x), h₂(x), . . . , h<sub>n−

t</sub>(x))

2. The method of claim 1, further comprising the steps of:

a.1) providing the input string xas a concatenation of 1^st through component strings y₁, y₂, . . . y_s of length v₁, v₂, . . . v_s; and

a.2) conducting steps a) through e) on each of said 1^st through s^th component string y₁, Y₂, . . . y_s, such that H(x) is a concatenation of the hash functions defined by step e) for each of said 1^st through s^th component strings, namely, H₁(y₁), H₂(y₂), . . . , H_s(y_s).

3. The method of claim 1, wherein F=Z₂, the binary field consisting of the elements 0, 1.

4. The method of claim 1, wherein F=Z2 and A is an incidence matrix of Hadamard design on n points with n □

3(mod

     4), obtained from a Sylvester matrix of size (n+1)×

(n+1).

9. A method of verifying with certainty that a first and second cryptographic string K_A and K_B over a finite field F in first and second cryptographic station A and B, respectively, are equal, wherein the Hamming distance between said first and second string K_A and K_B is less than a pre-assigned positive integer d, said method comprising the steps of:

a) choosing a linear code C over F, said linear code C having a minimum distance d;

b) publicly selecting a generator matrix M for said linear code C, said matrix M having a size (n−

t)×

n, rows x columns;

c) in said first cryptographic station A, transmitting H(K_A) to said second station B, wherein H is constructed by the method of claim 1, wherein M is provided as the incidence matrix of step a);

d) in said second cryptographic station B, verifying that H(K_A)=H(K_B), wherein H(K_B) is constructed by the method of claim 1, wherein M is provided as the incidence matrix of step a); and

e) when H(K_A)=H(K_B), concluding with certainty that K_A=K_B.

10. A method of generating an unconditionally secure cryptographic key between a first and second cryptographic station A and B given a binary key K_A in said first station A and a binary key K_B in said second station B having a common length n and such that K_A=K_B=K, wherein at most t Shannon bits of the key K are known to an eavesdropper Eve, said method comprising the steps of:

a) in said first and second station A and B for said given binary key K=K_A=K_B, constructing a hash function H by the method of claim 1;

and

b) in said first station and second station A and B, respectively, calculating an unconditionally secure cryptographic key L=H(K_A) and L=H(K_B).

11. A method of performing a cryptographic digital signature algorithm that utilises a hash function, wherein said hash function is constructed according to the method of claim 1.

13. A method of performing a cryptographic message authentication algorithm (MAC) that utilises a hash function, wherein said hash function is constructed according to the method of claim 1.

15. A memory look-up method for retrieving and storing a data item in a location of a memory which is associated with at least one particular value of an input string x=(x₁, x₂, . . . , x_n) of length n>

0, said method comprising the steps of;

a) receiving said input string x;

b) constructing a hash function H according to the method of claim 1 to map said received input string x to an output string H(x), wherein said output string H(x) indicates a location in said memory at which said data item can be retrieved and stored; and

c) employing said output string H(x) to respectively retrieve and store said data item from and into said location of said memory.

17. A computer apparatus comprising a computer and a memory able to perform the algorithm of claim 1 to construct a beginning memory location as the output value H(K) from an input string x equal to a key K for at least one of storing data associated with said key K starting at said beginning memory location H(K) and retrieving data from said beginning memory location H(K).

19. A first and second computer apparatus comprising a processor at a first and second cryptographic station A and B, wherein each of said first and second computer apparatus is able to perform the algorithm of claim 10 to generate an unconditionally secure cryptographic key from a received input string K, said input string K having at most t Shannon bits of K known to an eavesdropper Eve.

20. A computer apparatus comprising a processor able to perform the algorithm of claim 1 for each of a first and second input string, K_A and K_B, in order to obtain first and second hash functions H(K_A) and H(K_B) and determine that K_A=K_B whenever H(K_A)=H(K_B).

22. A computer apparatus comprising a processor able to perform the algorithm of claim 1 for constructing a hash function as input to performing a cryptographic digital signature algorithm that utilizes said hash function.

24. A computer apparatus comprising a processor able to perform the algorithm of claim 1 for constructing a hash function as input to performing a cryptographic message authentication algorithm (MAC) that utilizes said hash function.

5. A method of constructing a hash function H(x) for mapping an input string x=(x₁, x₂, . . . , x_v) of length n>

0 to an output string H(x)={(h₁(x), h₂(x), . . . , h<sub>n−

t</sub>(x))} of length n−

t, 1<

t<

n, said method comprising the steps of;

a) providing a matrix M having size (n−

t)×

n, rows R_i x columns, and rank n−

t over a given finite field F whereby the Hamming distance between any two distinct vectors obtained from a distinct linear combination of the rows of M, is at least d, where d is some pre-assigned positive integer;

b) for each said row R_i of M, setting h_i(x)=x·

R₁, 1≦

i≦

n−

t where denotes the dot product operation; and

c) defining said hash function H(x) as the function H(x)={(h₁(x), h₂(x), . . . , h<sub>n−

t</sub>(x))}for l<

t□

n.

6. The method of claim 5, wherein F=Z₂, the binary field consisting of the elements 0,1.

7. The method of claim 5, wherein M is a generator matrix for a linear code having a minimum distance d over the field F.

8. The method of claim 5, further comprising the steps of

a.1) providing the input string (x) as a concatenation of 1^st through s^th component string y₁, y₂, . . . y_s_of length v₁, v₂, . . . v_s;

and

a.2) conducting steps a) through c) on each of said 1^st through s^th component strings y₁, y₂, . . . y_s, such that H(x) is a concatenation of the hash functions defined by step c) for each of said 1^st through s^th component strings, namely, H₁(y₁), H₂(y₂) . . . H_s(y_s).

12. A method of performing a cryptographic digital signature algorithm that utilises a hash function, wherein said hash function is constructed according to the method of claim 5.

14. A method of performing a cryptographic message authentication algorithm (MAC) that utilises a hash function, wherein said hash function is constructed according to the method of claim 5.

16. A memory look-up method for retrieving and storing a data item in a location of a memory which is associated with at least one particular value of an input string x=(x₁, x₂, . . . . , x_n) of length n>

0, said method comprising the steps of;

a) receiving said input string x;

b) constructing a hash function H according to the method of claim 5 to map said received input string x to an output string H(x), wherein said output string H(x) indicates a location in said memory at which said data item can be retrieved and stored; and

c) employing said output string H(x) to respectively retrieve and store said data item from and into said memory.

18. A computer apparatus comprising a memory and a processor able to perform the algorithm of claim 5 to construct a beginning memory location as the output value H(K) from an input string x equal to a key K for at least one of storing data associated with said key K starting at said beginning memory location H(K) and retrieving data from said beginning memory location H(K).

21. A computer apparatus comprising a processor able to perform the algorithm of claim 5 for each of a first and second input string, K_A and K_B, in order to obtain first and second hash functions H(K_A) and H(K_B) and determine that K_A=K_B whenever H(K_A)=H(K_B).

23. A computer apparatus comprising a processor able to perform the algorithm of claim 5 for constructing a hash function as input to performing a cryptographic digital signature algorithm that utilizes said hash function.

25. A computer apparatus comprising a processor able to perform the algorithm of claim 5 for constructing a hash function as input to performing a cryptographic message authentication algorithm (MAC) that utilizes said hash function.