Public-key signature methods and systems

Abstract

The invention provides for a cryptographic method for digital signature. A set Sof k polynomial functions P(x, . . . , x, y, . . . , y) are supplied as a public key, where k, v, and n are integers, x, . . . , xare n+v variables of a first type, and y, . . . , yare k variables of a second type, the set Sbeing obtained by applying a secret key operation on a given set Sof k polynomial functions P'(a, . . . , a, y, . . . , y), a, . . . , adesignating n+v variables including a set of n 'oil' and v 'vinegar' variables. A message to be signed is provided and submitted to a hash function to produce a series of k values b, . . . , b. These k values are substituted for the k variables y, . . . . , yof the set Sto produce a set Sof k polynomial functions P″(a, . . . , a), and v values a′, . . . , a′, are selected for the v “vinegar” variables. A set of equations P″(a, . . . , a′)=0 is solved to obtain a solution for a′, . . . , a′and the secret key operation is applied to transform the solution to the digital signature.