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.

Description:
RELATED APPLICATIONS  
       [0001]    This application relates to our corresponding application Ser. No. ______ (Attorney Docket No. TPP31464) filed on the same date and entitled “A Key Agreement Protocol Based On Network Dynamics” naming Aiden BRUEN, David WEHLAU and Mario FORCINITO as the inventors. 
     
    
     
       BACKGROUND OF THE INVENTION  
         [0002]    1. Field of the Invention  
           [0003]    The present invention relates to hash functions for mapping a set of input values S to a set of output T. More particularly, the present invention relates to hash functions for mapping a set of keys S to a set of target values T, which hash functions can be used to detect if two elements s, s′εS are in fact the same element and to respectively store and retrieve data into an from a memory.  
           [0004]    2. Discussion of the Related Art  
           [0005]    Hash functions are transformations that map from larger domains to smaller ranges. In many applications, such as digital signatures, it is necessary to have an irreversible function which takes an input string and returns a bit string of fixed length. Such one-way functions are referred to as one-way hash functions.  
           [0006]    Hashing also may be viewed as a way to assign an abbreviation to a name. In this case the property of giving different results for different inputs is a desirable one. In practice, this property is required to be true “most of the time.” That is, there should be a very low probability of getting the same result whenever the inputs are different. Hash functions having this property are usually referred to as “collision free” [10].  
           [0007]    Hash functions commonly used in encryption systems include message digest (MD5), secure hashing algorithm (SHA) and secure hashing standard (SHS) and are based on subjecting the input(s) to several rounds of certain modular arithmetic operations and taking appropriate sub-strings from the results. Other techniques involve the use of substitution boxes (S-boxes) or even the use of encryption algorithms, such as data encryption standard (DES) and advanced encryption standard (AES) since encryption algorithms can be considered as particular cases of hash functions.  
           [0008]    Yet another and more general approach is to choose (randomly or not) one or more hash functions from a large set of such functions such that the resulting hash is some combination of the results of the application of these hash functions to the same input.  
         SUMMARY OF THE INVENTION  
         [0009]    The present invention provides a hash function H such that for two strings s and s′ the condition s≠s′ can be detected by applying this hash function H to each string and checking that H(s)≠H(s′). Conversely, by using the present invention, evidence for the equality of s and s′ can be obtained by verifying that H(s)=H(s′) for many different hash functions H.  
           [0010]    Consider the case where S consists of a subset of the vector space of dimension n over the finite field having only two elements, 0 and 1. That is to say, assume that S is a set of strings s of binary bits, each string having length n.  
           [0011]    Similarly, assume that T is a subset of the vector space of dimension m over the same finite field. That is to say, assume that T is a set of strings of binary bits, each string having length m.  
           [0012]    Suppose further that it is desired to map S to T using a hash function H. The values of a hash function H may be written as a combination, such as a concatenation, of functions H(s)=(h 1 (s), h 2 (s), . . . , h m (s)) where each function h 1 (s)ε{0,1}. The function H is completely determined by the projected functions h 1 , h 2 , . . . , h m . Therefore it suffices to consider hash functions which take their values in the finite field, {0, 1}. In summary, hash functions mapping a set of binary n-vectors to the set {0, 1} are constructed by the present invention.  
           [0013]    The present invention provides a method and apparatus for constructing a hash function H that maps strings s of S to strings H(s) of T, wherein H(s)=(hi(s), h 2 (s), . . . , h m (s)) such that each h i (s) ε{0, 1}, all h i (s) being based on one of Sylvester matrices, balanced incomplete block designs, and error-correcting codes.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]    [0014]FIG. 1 illustrates construction of a hash function according to an embodiment of the present invention employing block designs.  
         [0015]    [0015]FIG. 2 illustrates construction of a hash function according to an embodiment of the present invention employing algebraic codes.  
         [0016]    [0016]FIG. 3 illustrates construction of a hash function according to the present invention for an input key corresponding to data to be stored/retrieved in/from a memory by a computer apparatus.  
         [0017]    [0017]FIG. 4 illustrates a computer apparatus at cryptographic station A and B that employs a hash function constructed according to the present invention to obtain an unconditionally secure cryptographic key from the keys received at each station.  
         [0018]    [0018]FIG. 5 illustrates determining equality of tow input strings by a computer apparatus at station A and B using a hash function H constructed according to the present invention.  
         [0019]    [0019]FIG. 6 illustrates a computer apparatus obtaining a cryptographic digital signature from an algorithm that uses a hash function, the has function being constructed according to the present invention.  
         [0020]    [0020]FIG. 7 illustrates a computer apparatus constructing a hash function according to the present invention for a given input string and then using this hash function to perform cryptographic message authentication. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0021]    The present invention provides a method for obtaining a hash function H=(h 1 (s), h 2 (s), . . . , h m (s)) over a given finite field using Sylvester matrices, block designs or algebraic codes.  
         [0022]    Hash Functions Using Block Designs  
         [0023]    Referring now to FIG. 1, a suitable hash function H(s)=(h 1 (s), h 2 (s), . . . , h n−t (s)) can be obtained in the following way. Let s={S 1 , S 2 , . . . , s n } 10 be a binary vector of length n. In one preferred embodiment, a set of n−t functions {h 1 (s), h 2 (s), . . . , h n−t (s)}, where t&gt;0, is obtained as follows.  
         [0024]    (1) Choose a family F of n−t linearly independent (with respect to symmetric difference) subsets of an n-set Ω={1, 2, 3 . . . , n}.  
         [0025]    (2) Write F={F 1 , F 2 , . . . , F n−t }, e.g., as the first n−t rows of an n×n matrix 20.  
         [0026]    (3) Then define h 1 , h 2 , . . . , h n−t  by h j (s)=(Σ w in Fj  s w )(mod 2), wherein 1≦j≦n−t. These functions are described in [1] and [2]. Of course any such family F may suffice.  
         [0027]    (4) Set H(s)=(h 1 (s), h 2 (s), . . . , h n−t (s)).  
         [0028]    However, in a preferred embodiment, when H is employed to encrypt S in order to maximize the difficulty of eavesdropping, F is constructed so that it has regularity properties. That is, it is required that the subset in F be “well spread out.” Ideally the family F has the property that any two elements in Ω lie in a constant number of subsets in F. Further, it is desirable also that each subset in F has the same cardinality and that two different subsets in F intersect in a constant number of elements. Indeed these are the criteria that motivated the design of experiments in statistics [3], [4] leading to the combinatorial study of block-designs (see [5] and [6]) In cryptography a condition known as the Avalanche Criterion (AC) is used in the analysis of S-boxes or substitution boxes (see for example [7], [8]), in which each S-box takes a 6-bit input and produces a 4-bit output such that bits of a ciphertext depend on bits of a plaintext and bits of a key used to encrypt the plaintext to produce the ciphertext. The present invention adapts this criterion to hash functions such that, given a set of hash functions with values in {0, 1}, if one bit of the input string is changed then the Avalanche Criterion requires that about half of the hash functions should change their output values.  
         [0029]    In a preferred embodiment of the present invention, block designs are employed to construct a family of hash functions that satisfies all of these desirable criteria. A particular kind of block design arises from Sylvester matrices, the so-called Hadamard designs. Let H denote a 4t×4t Hadamard matrix. This means that every entry in H is a 1 or −1 and that HH t =4t I 4t t. Assume that such a matrix exists. There is a long standing open conjecture that at least one 4t×4t Hadamard matrix exists for every t. This conjecture has been verified for all t≦117. Furthermore, for infinitely many larger values of t, it is known that a 4t×4t Hadamard matrices does exist.  
         [0030]    Suppose that H has been normalized so that its first row and first column consist entirely of 1&#39;s. A new a 4t−1×4t−1 matrix {overscore (H)} is constructed, all of whose entries are either 0 or 1, as follows. The first row and first column (consisting of all 1&#39;s) are deleted from H and then every −1 in the remaining matrix is changed to 0. The resulting matrix is H. This matrix is the incidence matrix  20  of a block design with v=4t, k=2t−1 and λ=t−1. This design is called a Hadamard 2-design.  
         [0031]    For each row, r, of {overscore (H)} define a linear hash function h r  which maps a 4t−1-vector into its dot product with the row r. These 4t−1 different hash functions satisfy the Avalanche Criterion as well as the other desirable conditions listed above.  
         [0032]    If t is odd then these 4t−1 linear hash functions are linearly independent. This fails if t is even. However, in this case, a large subset to the 4t−1 hash functions are linearly independent.  
         [0033]    Suppose that n ≠3 (mod 4). Then a Hadamard design of size n cannot be constructed. In this case, a preferred embodiment of the present invention requires the use of the least integer n′&gt;n where n′≡3 (mod 4) and the extension of input strings to length n′ by padding on the right with (at most 3) zeroes. This results in n′ hash functions which are linearly dependent.  
         [0034]    Hash Functions Using Algebraic Codes  
         [0035]    Traditionally in cryptography binary codes are used as follows (see [9]). A string x is embedded in a code-word {tilde over (x)} belonging to some code C where {tilde over (x)} is obtained from x by adjoining to x parity bits corresponding to C. Traditional approaches, on the assumption of few errors, attempt to decode {tilde over (x)} from x. Here a new approach is provided by the present invention.  
         [0036]    Recall that the hash function H is constructed to help decide whether two elements s and s′ of S are equal. Consider the special situation where it is known (or known with high probability) that the Hamming distance between s and s′ is less than some small integer d. In other words it is known that the number of bits where s and s′ differ is less than d.  
         [0037]    Referring now to FIG. 2, consider an r×n matrix K  30  which is the parity check matrix of a code of minimum distance at least d. This means that the subspace of vectors perpendicular to every row of K  30  contains only one vector of Hamming weight less than or equal to d, namely, the zero vector. For each row r of K  30  define a function h r  by taking h r (s) to be the dot product of row r and vector s. Thus, given vectors s and s′ such that h r (s)=h r (s′) for all rows r of K  30  then s+s′ is an element of the code of minimum distance d. Therefore either s=s′ or else the Hamming distance between s and s′ is at least d (s differs from s′ by at least d bits) and the desired hash function is H(s)=h 1 (s), . . . , h r (s).  
       EXAMPLE  
       [0038]    Suppose that n is some integer with 64&lt;n≦128 and that A and B are two binary vectors of length n. An 8×128 parity check matrix K  30  is constructed. First, a 7×128 matrix {overscore (K)} is constructed. Consider the 128 columns of {overscore (K)}. All 128 columns of {overscore (K)} should be distinct (different). Take the first 8 columns of {overscore (K)} to be:  
         (         0       1       0       0       0       0       0       0           0       0       1       0       0       0       0       0           0       0       0       1       0       0       0       0           0       0       0       0       1       0       0       0           0       0       0       0       0       1       0       0           0       0       0       0       0       0       1       0           0       0       0       0       0       0       0       1         )                               
 
         [0039]    The remaining 120 distinct columns of {overscore (K)} may be arranged in any order, say in lexicographic order.  
         [0040]    Next, K  30  is obtained from {overscore (K)} by adding a row consisting entirely of 1&#39;s to the top of K. Then K  30  is the parity check matrix for a code of minimum distance 4. There are 8 hash functions h 1 , h 2 , . . . , h 8  obtained by defining h i  to be the dot product 40 with row i of K  30 . Now if n&lt;128, A and B are extended to new binary strings A′ and B′ of length 128 by adding 0&#39;s to the right of A and B. (Equivalently, the last 128−n columns may be truncated from K  30 .) Now if h i (A′)=h i (B′) for all i=1, 2, . . . , 8 then either A′=B′ or else the Hamming distance from A′ to B′ is at least 4. Thus, clearly, either A=B or the Hamming distance from A to B is at least 4. The desired has function is  
           H ( A )= h   1 ( A ), . . . ,  h   8 ( A ).  
         [0041]    Security  
         [0042]    Finally, consider the extra possibility that it is desired to conceal the values of A and B from some eavesdropper, Eve, who has learned the values h 1 (A), h 1 (B), . . . , h 8 (A), h 8 (B). In this case the first 8 bits may be deleted from A and B leaving binary strings {overscore (A)} and {overscore (B)} of length n−8. Although 8 bits have been lost from A and B this is compensated for by the fact that Eve&#39;s knowledge of the values h i (A) and h i (B) provides her with no information about {overscore (A)} and {overscore (B)}.  
         [0043]    Apparatus  
         [0044]    In a preferred embodiment, as illustrated in FIG. 3, a computer apparatus  60 , preferably comprising at least one processor and at least one memory, is able to employ a hash function H(K)  70  constructed according to the present invention in order to obtain a memory location corresponding to a received input key K associated with a data item  50  and then the same or another computer apparatus  80 , preferably comprising at least one processor and at least one memory, is able to retrieve and store, beginning at location H(K), the received data item associated with the received input key K.  
         [0045]    In FIGS.  4 - 7  the computer apparatus similarly comprises at least one memory and/or at least one processor.  
         [0046]    Similarly, FIG. 4 illustrates a computer apparatus  100  at cryptographic stations A and B that is able to employ the hash function constructed according to the present invention  100 , to obtain and output  110  of an unconditionally secure cryptographic key from the respective received key K A , K B  wherein K A =K B    90 .  
         [0047]    And, as shown in FIG. 5, determination of the equality of two input strings K A  and K B    120  can be accomplished by a computer apparatus  130  employed by station A and B that is able to construct a hash function H and obtain H(K A ) and H(K B ), with station A transmitting H(K A ) to station B  140  such that station B is able to verify that H(K A )=H(K B ) and thereby conclude that K A =K B    150 .  
         [0048]    [0048]FIG. 6 illustrates a computer apparatus  170  that is able to obtain a cryptographic digital signature for a received input string  160  and then output the obtained cryptographic digital signature  180 .  
         [0049]    [0049]FIG. 7 illustrates a computer apparatus  200  that is able to receive an input string  190  and from this received string is then able to construct a hash function according to the present invention and perform cryptographic message authentication using this hash function, finally outputting the result of the authentication  210 .  
         [0050]    It will be understand by those skilled in the art that the above-described embodiments are but examples from which it is possible to deviate without departing from the scope of the invention as defined by the appended claims.  
       REFERENCES AND BIBLIOGRAPHY  
       [0051]    The following references as well as any reference mentioned elsewhere in this specification are hereby incorporated by reference as in fully set forth herein.  
         [0052]    [1] Charles Bennett, François Bessette, Gilles Brassard, Louis Salvail, and John Smolin,  Experimental quantum cryptography,  EUROPCRYPT &#39;90 (Arhus, Denmark), 1990, pp. 253-265.  
         [0053]    [2] Samuel J. Lomonaco,  A quick glance at quantum cryptography,  Cryptologia 23 (1999), no. 1, 1-41.  
         [0054]    [3] R. A. Fisher and F. Yates.  Statistical Tables for Biological, Agricultural and Medical Research.  Oliver-and-Boyd Ltd., third edition, 1948.  
         [0055]    [4] D. Rhaghabarao.  Constructions and Combinatorial Problems in the Design of Experiments.  John Wiley &amp; Sons, 1971.  
         [0056]    [5] H. Lenz Thomas Beth, D. Jungnickel.  Design Theory.  Cambridge University Press, 1986.  
         [0057]    [6] P. J. Cameron and G. E. van Lint.  Designs, Graphs, Codes and their Lenghts.  Cambridge University Press, 1991. London Math Soc. Student Text vol 22.  
         [0058]    [7] Richard A. Mollin.  An Introduction to Cryptography.  Chapman &amp; Hall/CRC Press, 2000.  
         [0059]    [8] R K Nichols, editor.  ICSA Guide to Cryptography.  Mc Craw Hill, 1999.  
         [0060]    [9] Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert,  Privacy Amplification by Public Discussion, Siam J. of Computing,  17, no.2 (1988), 210-229.