Patent ID: 7100051

Claim:
A digital signature cryptographic method, performed by a computing device, the method comprising: supplying a set S 1 of k polynomial functions as a public-key, the set S 1 including the functions P 1 (x 1 , . . . , x n+v , y 1 , . . . , y k ), . . . , P k (x 1 , . . . , x n+v , y 1 , . . . , y k ), where k, v, and n are integers, x 1 , . . . , x n+v are n+v variables of a first type, y 1 , . . . , y k are k variables of a second type, and the set S 1 is obtained by applying a secret key operation on a set S 2 of k polynomial functions P′ 1 (a 1 , . . . , a n+v , y 1 , . . . , y k ), . . . , P′ k (a 1 , . . . , a n+v , y 1 , . . . , y k ) where a 1 , . . . , a n+v are n+v variables which include a set of n “oil” variables a 1 , . . . , a n , and a set of v “vinegar” variables an a n+1 , . . . , a n+v , the supplying comprising selecting the number v of “vinegar” variables to be greater than the number n of “oil” variables; providing a message to be signed; applying a hash function on the message to produce a series of k values b 1 , . . . , b k ; substituting the series of k values b 1 , . . . , b k for the variables y 1 , . . . , y k of the set S 2 respectively to produce a set S 3 of k polynomial functions P″ k (a 1 , . . . a n+v ), . . . , P″ k (a 1 , . . . , a n+v ); selecting v values a′ n+1 , . . . , a n+v for the v “vinegar” variables a n+1 , . . . a n+v ; solving a set of equations P″ 1 (a 1 , . . . , a n , a′ n+1 , . . . , a′ n+v )=0, . . . , P″ k (a 1 , . . . , a n , a′ n+1 , . . . , a′ n+v )=0 to obtain a solution for a′ 1 , . . . , a′ n ; applying the secret key operation to transform a′ 1 , . . . , a′ n+v to a digital signature e 1 , . . . , e n+v ; and assigning e 1 , . . . , e n+v as the digital signature of the message.