Efficient cryptographic hash functions and methods for amplifying the security of hash functions and pseudo-random functions

Claim 3

The method as recited in claim 1 wherein the processing by the butterfly generator generates 2n outgoing bits from 2n incoming bits partitioned into a first incoming set of n bits and a second incoming set of n bits, the butterfly generator utilizing eight n-bit pseudo-random function generators G(1), G(2), . . . , G(8), each of the generators having a corresponding input key, of length k, obtained from a corresponding one of the new set of keys, the method further comprising the steps of identifying the 2n incoming bits with the exclusively-ORed bits, inputing the first incoming set to the generators G(1) and G(2), inputing the second incoming set to the generators G(3) and G(4), generating a first intermediate set of n bits as the exclusive-OR of the outputs of the generators G(1) and G(3), generating a second intermediate set of n bits as the exclusive-OR of the outputs of the generators G(2) and G(4), inputing the first intermediate set to the generators G(5) and G(6), inputing the second intermediate set to the generators G(7) and G(8), generating the first n outgoing bits as the exclusive-OR of the outputs of the generators G(5) and G(7), and generating the second n outgoing bits as the exclusive-OR of the outputs of the generators G(6) and G(8), wherein the 2n outgoing bits equate to the current hash function.

Claim 4

The method as recited in claim 1 wherein the processing by the butterfly generator generates 2n outgoing bits from 2n incoming bits partitioned into a first incoming set of n bits and a second incoming set of n bits, the butterfly generator utilizing eight n-bit universal hash function or pseudo-random function generators G(1), G(2), . . . , G(8), each of the generators having a corresponding input key, of length k, obtained from a corresponding one of the new set of keys, the method further comprising the steps of identifying the 2n incoming bits with the exclusively-ORed bits, inputing the first incoming set to the generators G(1) and G(2), inputing the second incoming set to the generators G(3) and G(4), generating a first intermediate set of n bits as the exclusive-OR of the outputs of the generators G(1) and G(3), generating a second intermediate set of n bits as the exclusive-OR of the outputs of the generators G(2) and G(4), inputing the first intermediate set to the generators G(5) and G(6), inputing the second intermediate set to the generators G(7) and G(8), generating the first n outgoing bits as the exclusive-OR of the outputs of the generators G(5) and G(7), and generating the second n outgoing bits as the exclusive-OR of the outputs of the generators G(6) and G(8), wherein the 2n outgoing bits equate to the current hash function.

Claim 5

The method as recited in claim 1 wherein the universal hash function generator arrangement is a finite field subset-sum generator arrangement and wherein the step of processing by the universal hash function generator arrangement includes the step of processing by the finite field subset-sum generator arrangement to generate the set of keys identified by k 1 , k 2 , . . . , k 8 , each of length k, the finite field subset-sum generator arrangement being composed of a eight finite field subset-sum generators, each of the generators utilizing b random bit tables T 1 , T 2 , . . . , T b with each table having 2 m rows and k columns, and wherein the step of partitioning includes the step of partitioning the input bits into eight blocks of 8mb bits to produce the new blocks, the eight blocks being designated β 1 , β 2 , . . . , β 8 , with each of the blocks having b m-bit groups c i (j) such that {c 1 (1), c 2 (1), . . . , c b (1)} corresponds to β 1 , {c 1 (2), c 2 (2), . . . , c b (2)} corresponds to β 1 , . . . , and {c 1 (8), c 2 (8), . . . , c b (8)} corresponds to β 8 , and wherein the step of processing by the universal hash function generator arrangement includes the steps, for each j, j=1,2, . . . ,8, of selecting a row from each table T i in correspondence to each group c i (j), i=1, 2, . . . , b, and of evaluating the bitwise exclusive-OR of said b selected rows to generate the corresponding key k j .

Claim 8

The method as recited in claim 5 wherein the processing by the butterfly generator generates 2n outgoing bits from 2n incoming bits partitioned into a first incoming set of n bits and a second incoming set of n bits, the butterfly generator utilizing eight n-bit pseudo-random function generators G(1), G(2), . . . , G(8), each of the generators having a corresponding input key, of length k, obtained from a corresponding one of the new set of keys, the method further comprising the steps of identifying the 2n incoming bits with the exclusively-ORed bits, inputing the first incoming set to the generators G(1) and G(2), inputing the second incoming set to the generators G(3) and G(4), generating a first intermediate set of n bits as the exclusive-OR of the outputs of the generators G(1) and G(3), generating a second intermediate set of n bits as the exclusive-OR of the outputs of the generators G(2) and G(4), inputing the first intermediate set to the generators G(5) and G(6), inputing the second intermediate set to the generators G(7) and G(8), generating the first n outgoing bits as the exclusive-OR of the outputs of the generators 0(5) and G(7), and generating the second n outgoing bits as the exclusive-OR of the outputs of the generators G(6)and G(8), wherein the 2n outgoing bits equate to the current hash function.

Claim 9

The method as recited in claim 5 wherein the processing by the butterfly generator generates 2n outgoing bits from 2n incoming bits partitioned into a first incoming set of n bits and a second incoming set of n bits, the butterfly generator utilizing eight n-bit universal hash function or pseudo-random function generators G(1), G(2), . . . , G(8), each of the generators having a corresponding input key, of length k, obtained from a corresponding one of the new set of keys, the method further comprising the steps of identifying the 2n incoming bits with the exclusively-ORed bits, inputing the first incoming set to the generators G(1) and G(2), inputing the second incoming set to the generators G(3) and G(4), generating a first intermediate set of n bits as the exclusive-OR of the outputs of the generators G(1) and G(3), generating a second intermediate set of n bits as the exclusive-OR of the outputs of the generators G(2) and G(4), inputing the first intermediate set to the generators G(5) and G(6), inputing the second intermediate set to the generators G(7) and G(8), generating the first n outgoing bits as the exclusive-OR of the outputs of the generators G(5)and C(7), and generating the second n outgoing bits as the exclusive-OR of the outputs of the generators C(6) and C(8), wherein the 2n outgoing bits equate to the current hash function.

Claim 10

The method as recited in claim 5 wherein the universal hash function generator arrangement is a finite field subset-sum generator arrangement and wherein the step of processing by the universal hash function generator arrangement includes the step of processing by the finite field subset sum generator arrangement to generate the set of keys identified by k 1 , k 2 , . . . , k 8 , each of length k, the finite field subset-sum generator arrangement being composed of a eight finite field subset-sum generators, each of the generators utilizing b random bit tables T 1 , T 2 , . . . , T b with each table having 2 m rows and k columns, and wherein the step of partitioning includes the step of partitioning the input bits into eight blocks of 8mb bits to produce the new blocks, the eight blocks being designated β 1 , β 2 , . . . , β 8 , with each of the blocks having b m-bit groups c i (j) such that {c 1 (1), c 2 (1), . . . , c b (1)} corresponds to β 1 , {c 1 (2), c 2 (2), . . . , c b (2)} corresponds to β 1 , . . . , and {c 1 (8), c 2 (8), . . . , c b (8)} corresponds to β 8 , and wherein the step of processing by the universal hash function generator arrangement includes the steps, for each j, j=1,2, . . . ,8, of selecting a row from each table T i in correspondence to each group c i (j), i=1, 2, . . . , b, and of evaluating the bitwise exclusive-OR of said b selected rows to generate the corresponding key k j .

Claim 19

Circuitry for generating output bits corresponding to a cryptographic hash function of input bits, the circuitry utilizing eight n-bit pseudo-random function generators G(1), G(2), . . . , G(8), each of the generators having a corresponding input key k 1 , k 2 , . . . , k 8 of length k, the circuitry further utilizing b random bit tables T 1 , T 2 , . . . , T b with each table having 2 m rows and k columns, the circuitry comprising (a) means, responsive to the input bits, for partitioning the initial 8mb bits of the input bits into eight blocks, designated β 1 , β 2 , . . . , β 8 , with each of the blocks having b m-bit groups c i (j) as the current input groups such that {c 1 (1), c 2 (1), . . . , c b (1)} corresponds to β 1 , {c 1 (2), c 2 (2), . . . , c b (2)} corresponds to β 1 , . . . , and {c 1 (8), c 2 (8), . . . , c b (8)} corresponds to β 8 , and proceeding to step (c), (b) means, responsive to the input bits, for partitioning the next 8mb bits of the input bits into eight blocks, designated β 1 , β 2 , . . . , β 8 , with each of the blocks having b m-bit groups c i (j) as the current input groups wherein {c 1 (1), c 2 (1), . . . , c b (1)} corresponds to β 1 , {c 1 (2), c 2 (2), . . . , c b (2)} corresponds to β 1 , . . . , and {c 1 (8), c 2 (8), . . . , c b (8)} corresponds to β 8 , (c) means, responsive to each means for partitioning for selecting for each j, j=1,2, . . . ,8, a row from each table T i in correspondence to each current group c i (j), i=1, 2, . . . , b, and for evaluating the bitwise exclusive-OR of said b selected rows to generate a corresponding key k j , (d) means, responsive to the means for generating and for evaluating, for generating 2n pseudo-random bits partitioned into a first pseudo-random set of n bits and a second pseudo-random set of n bits, (e) means for inputing the first pseudo-random set and the respective keys k 1 and k 2 to the generators G(1) and G(2), (f) means for inputing the second pseudo-random set and the respective keys k 3 and k 4 to the generators G(3) and G(4). (g) means for generating a first intermediate set of n bits as the bitwise exclusive-OR of the outputs of the generators G(1) and G(3), (h) means for generating a second intermediate set of n bits as the bitwise exclusive-OR of the outputs of the generators G(2) and G(4), (i) means for inputing the first intermediate set and the respective keys k 5 and k 6 to the generators C(5) and C(6), (j) means for inputing the second intermediate set and the respective keys k 7 and k 8 to the generators G(7) and G(8), (k) means for generating the first n bits of the current output bits as the bitwise exclusive-OR of the outputs of the generators G(5) and G(7), (l) means for generating the second n bits of the current output bits as the bitwise exclusive-OR of the outputs of the generators G(6) and G(8), (m) means for forming the output bits corresponding to the hash function as the bitwise exclusive-OR of the current output bits generated sequentially by steps (k) and (l), and (n) means for returning to step (b) if more input bits can be partitioned.

Claim 20

Circuitry for generating output bits corresponding to a cryptographic hash function of input bits, the circuitry utilizing eight n-bit pseudo-random function generators G(1), G(2), . . . , G(8), each of the generators having a corresponding input key k 1 , k 2 , . . . , k 8 of length k, the circuitry further utilizing b random bit tables T 1 , T 2 , . . . , T b with each table having 2 m rows and k columns, the circuitry comprising (a) means, responsive to the input bits, for partitioning the initial 8mb bits of the input bits into eight blocks, designated β 1 , β 2 , . . . , β 8 , with each of the blocks having b m-bit groups c i (j) as the current input groups such that {c 1 (1), c 2 (1), . . . , c b (1)} corresponds to β 1 , {c 1 (2), c 2 (2), . . . , c b (2)} corresponds to β 1 , . . . , and {c 1 (8), c 2 (8), . . . , c b (8)} corresponds to β 8 , and proceeding to step (c), (b) means, responsive to the input bits, for partitioning the next 8mb bits of the input bits into eight blocks, designated β 1 , β 2 , . . . , β 8 , with each of the blocks having b m-bit groups c i (j) as the current input groups wherein {c 1 (1), c 2 (1), . . . , c b (1)} corresponds to β 1 , {c 1 (2), c 2 (2), . . . , c b (2)} corresponds to β 1 , . . . , and {c 1 (8), c 2 (8), . . . , c b (8)} corresponds to β 8 , (c) means, responsive to each means for partitioning for selecting for each j, j=1,2, . . . ,8, a row from each table T i in correspondence to each current group c i (j), i=1, 2, . . . , b, and for evaluating the bitwise exclusive-OR of said b selected rows to generate a corresponding key k j , (d) means, responsive to the means for generating and for evaluating, for generating 2n pseudo-random bits partitioned into a first pseudo-random set of n bits and a second pseudo-random set of n bits, (e) means for inputing the first pseudo-random set and the respective keys k 1 and k 2 to the generators G(1) and G(2), (f) means for inputing the second pseudo-random set and the respective keys k 3 and k 4 to the generators G(3) and G(4). (g) means for generating a first intermediate set of n bits as the bitwise exclusive-OR of the outputs of the generators G(1) and G(3), (h) means for generating a second intermediate set of n bits as the bitwise exclusive-OR of the outputs of the generators G(2) and G(4), (i) means for inputing the first intermediate set and the respective keys k 5 and k 6 to the generators C(5) and C(6), (j) means for inputing the second intermediate set and the respective keys k 7 and k 8 to the generators G(7) and G(8), (k) means for generating the first n bits of the current output bits as the bitwise exclusive-OR of the outputs of the generators G(5) and G(7), (l) means for generating the second n bits of the current output bits as the bitwise exclusive-OR of the outputs of the generators G(6) and G(8), (m) means for forming the output bits corresponding to the hash function as the bitwise exclusive-OR of the current output bits generated sequentially by steps (k) and (l), and (n) means for returning to step (b) if more input bits can be partitioned.