A cryptographic method, comprising: selecting a first multivariate polynomial mapping, which comprises first multivariate polynomial equations over first variables in a finite field, the first multivariate polynomial equations comprising a trapdoor; 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, wherein the second multivariate polynomial equations are Unbalanced Oil and Vinegar equations, which contain products of the first and second variables but do not contain products of the second variables with one another; 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, characterised in that the set of linear equations includes equations arising from the UOV equations and one or more additional equations, wherein the second values are chosen so that a predefined group of elements of the vector will be zero, and the one or more additional equations are chosen so that when the second values satisfy the one or more additional equations, the elements of the vector in the predefined group are guaranteed to be zero. selecting a first multivariate polynomial mapping, which comprises first multivariate polynomial equations over first variables in a finite field, the first multivariate polynomial equations comprising a trapdoor; 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, wherein the second multivariate polynomial equations are Unbalanced Oil and Vinegar equations, which contain products of the first and second variables but do not contain products of the second variables with one another; 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, characterised in that the set of linear equations includes equations arising from the UOV equations and one or more additional equations, wherein the second values are chosen so that a predefined group of elements of the vector will be zero, and the one or more additional equations are chosen so that when the second values satisfy the one or more additional equations, the elements of the vector in the predefined group are guaranteed to be zero. 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, characterised in that the set of linear equations includes equations arising from the UOV equations and one or more additional equations, wherein the second values are chosen so that a predefined group of elements of the vector will be zero, and the one or more additional equations are chosen so that when the second values satisfy the one or more additional equations, the elements of the vector in the predefined group are guaranteed to be zero.