Patent ID: 8150030

Claim:
A method, executed by a processor, of cryptographically hashing a message M, comprising the steps of: forming, by the processor, a sequence (M 1 , . . . , Mi, . . . , Mc) of data m-tuples M 1 =(a 1,1 , . . . , a 1,m ), . . . , Mi=(a i,1 , . . . , a i,m ), . . . , Mc=a c,1 , . . . , a c,m ), where m is a strictly positive integer, from said message M; iteratively calculating, by the processor, successive output p-tuples (V 1 , . . . , V i , . . . , V c ), where p is a strictly positive integer, corresponding to said sequence (M 1 , . . . , Mi, . . . , Mc) of data m-tuples as a function of at least one set of multivariate polynomials defined over a finite field, said iterative calculation of the successive output p-tuples (V 1 , . . . , V i , . . . V c ) including the steps of: defining, by the processor, an initialization input p-tuple E 0 =(e 01 , . . . , e 0p ) in the finite field; applying, by the processor, said initialization input p-tuple E 0 and a first data m-tuple M 1 to said at least one set of multivariate polynomials to calculate a first output p-tuple V 1 corresponding to said first data m-tuple M 1 ; in each new current iteration i, defining a current input p-tuple E i =(e i1 , . . . , e ip ) in the finite field that is a function at least of one of the output p-tuples (V 1 , . . . , V i-1 ) calculated in the preceding iterations, and applying said current input p-tuple E i and a current data m-tuple Mi to said at least one set of multivariate polynomials to calculate a current output p-tuple V i corresponding to said current data m-tuple Mi; and determining, by the processor, a hashing value of said message M as a function of the last output p-tuple V c .