| 摘要 |
A cryptographic method, apparatus, and system, including selecting a first multivariate polynomial mapping, which includes first multivariate polynomial equations over first variables in a finite field, defining a second multivariate polynomial mapping, which includes at least some of the first multivariate polynomial equations and further includes second multivariate polynomial equations over the first variables together with second variables in the finite field, generating a public key based on the second multivariate polynomial mapping, and digitally signing a message, using a processor, with a digital signature that is verifiable using the public key and is generated by solving the first multivariate polynomial mapping to find respective first values of the first variables, solving a set of linear equations using the first values to find respective second values of the second variables, and applying a transform to the first and second values so as to generate a vector corresponding to the digital signature, wherein the second values are chosen so that a predefined group of elements of the vector will be zero. Related methods, apparatus, and systems are also described. |
| 主权项 |
1. A cryptographic method, comprising:
selecting a first multivariate polynomial mapping, which comprises first multivariate polynomial equations over first variables in a finite field; defining a second multivariate polynomial mapping, which comprises at least some of the first multivariate polynomial equations and further comprises second multivariate polynomial equations over the first variables together with second variables in the finite field; generating a public key based on the second multivariate polynomial mapping; and digitally signing a message, using a processor, with a digital signature that is verifiable using the public key and is generated by:
solving the first multivariate polynomial mapping to find respective first values of the first variables;solving a set of linear equations using the first values to find respective second values of the second variables; andapplying a transform to the first and second values so as to generate a vector corresponding to the digital signature,wherein the second values are chosen so that a predefined group of elements of the vector will be zero, and the set of the linear equations comprises one or more additional equations chosen so that when the second values satisfy the additional equations, the elements of the vector in the predefined group are guaranteed to be zero. |
